/**
 * @file graph.h
 * @brief Directed graph implementation using adjacency lists.
 * @details This module provides a directed graph data structure where each
 *          vertex maintains separate lists of outgoing and incoming neighbors.
 */

#ifndef GRAPH_H
#define GRAPH_H

#include "vector.h"

/**
 * @struct Vertex
 * @brief A single vertex in a directed graph.
 * @details Each vertex is identified by a unique ID and maintains lists of
 *          vertices it points to and vertices that point to it.
 */
typedef struct Vertex Vertex;

/**
 * @struct Graph
 * @brief A directed graph container.
 * @details Maintains an array of all vertices and tracks the total number
 *          of vertices and edges in the graph.
 */
typedef struct Graph Graph;

/**
 * @struct Vertex
 * @brief Represents a single vertex in a directed graph.
 */
struct Vertex {
    /**
     * @brief Unique identifier for this vertex.
     * @details A value in the range [0, num_vertices) where num_vertices
     *          is the total number of vertices in the graph.
     */
    int id;

    /**
     * @brief List of outgoing neighbors (successors).
     * @details A Vector containing pointers to Vertex structures that
     *          this vertex points to (outgoing edges). Each element in the
     *          list is of type (Vertex*).
     */
    Vector *out_neighbours;

    /**
     * @brief List of incoming neighbors (predecessors).
     * @details A Vector containing pointers to Vertex structures that
     *          point to this vertex (incoming edges). Each element in the
     *          list is of type (Vertex*).
     */
    Vector *in_neighbours;
};

/**
 * @struct Graph
 * @brief A directed graph container structure.
 * @details The graph is represented using an adjacency list model where
 *          both incoming and outgoing edges are tracked for each vertex.
 */
struct Graph {
    /**
     * @brief The total number of vertices in the graph.
     * @details Vertices are indexed from 0 to (num_vertices - 1).
     */
    int num_vertices;

    /**
     * @brief The total number of edges in the graph.
     * @details This count includes all directed edges. An edge from vertex
     *          A to vertex B is counted as a single edge.
     */
    int num_edges;

    /**
     * @brief Array of all vertices in the graph.
     * @details An array of size num_vertices containing Vertex structures.
     *          Index i contains the vertex with id = i.
     */
    Vertex *vertices;
};

/**
 * @brief Allocates and constructs a new graph with n vertices.
 *
 * @param n The number of vertices in the graph.
 *
 * @return A pointer to the newly created graph,
 *         or NULL if memory allocation fails.
 *
 * @note The caller is responsible for freeing the returned graph
 *       using graph_delete().
 */
Graph *graph_new(int n);

/**
 * @brief Adds a directed edge from vertex i to vertex j.
 *
 * @param g Pointer to the graph.
 * @param i The source vertex (0-indexed).
 * @param j The destination vertex (0-indexed).
 */
void graph_add_edge(Graph *g, int i, int j);

/**
 * @brief Removes the directed edge from vertex i to vertex j.
 *
 * @param g Pointer to the graph.
 * @param i The source vertex (0-indexed).
 * @param j The destination vertex (0-indexed).
 */
void graph_remove_edge(Graph *g, int i, int j);

/**
 * @brief Reads a graph from a file and constructs a Graph object.
 *
 * @param filename The path to the file containing the graph data.
 * @return A pointer to the newly constructed graph,
 *         or NULL if the file cannot be read or memory allocation fails.
 *
 * @note The caller is responsible for freeing the returned graph
 *       using graph_delete().
 */
Graph *graph_read(const char *filename);

/**
 * @brief Deallocates the given graph and all its associated memory.
 *
 * @param g Pointer to the graph to delete.
 */
void graph_delete(Graph *g);

/**
 * @brief Prints information about the given graph to standard output.
 *
 * @param g Pointer to the graph to print.
 */
void graph_print(Graph *g);

#endif // !GRAPH_H