blob: e5417b9b7cbfcedd0acc3454aed000fb7e69feb2 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
|
/**
* @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 {
/**
* @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;
} 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 {
/**
* @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;
} Graph;
/**
* @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
|