blob: ca9f32adea90f4c1a5ce5cf1c5b2319041bbf848 (
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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
|
/**
* @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,
* enabling efficient navigation in both directions.
*/
#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. The array is
* dynamically allocated and should be freed by the caller
* when the graph is no longer needed.
*/
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.
* If NULL, this function does nothing.
*/
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
|