Newer
Older
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
#ifndef BARRUST_GRAPH_H__
#define BARRUST_GRAPH_H__
/*******************************************************************************
***
*** Author: Tyler Barrus
*** email: barrust@gmail.com
***
*** Version: 0.2.0
*** Purpose: Directed graph library
***
*** License: MIT 2020
***
*** URL: https://github.com/barrust/c-utils
***
*** Usage:
*** graph_t g = g_init();
*** g_vertex_add(g, "a");
*** g_vertex_add(g, "b");
***
*** g_edge_add(g, 0, 1, "test");
***
*** unsigned int i;
*** vertex_t v;
*** g_iterate_vertices(g, v, i) {
*** printf("vertex id: %d\tmetadata: %s\n", g_vertex_id(v), (char*)g_vertex_metadata(v));
*** }
*** g_free(g);
*******************************************************************************/
#ifdef __cplusplus
extern "C" {
#endif
typedef struct __graph* graph_t;
typedef struct __vertex_node* vertex_t;
typedef struct __edge_node* edge_t;
/* Initialize the graph either using the default start size or based on the
passed in size parameter */
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
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
graph_t g_init_alt(unsigned int size);
/* Free the graph and all edges & vertices; defaults to free'ing the metadata
property for both. Use the g_free_alt version if the metadata is not
malloc'd memory */
void g_free(graph_t g);
void g_free_alt(graph_t g, bool free_metadata);
/* Return the number of vertices currently in the graph */
unsigned int g_num_vertices(graph_t g);
/* Return the total number of vertices ever inserted into the graph
NOTE: likely only needed if writing ones own iteration loop */
unsigned int g_vertices_inserted(graph_t g);
/* Return the number of edges in the graph */
unsigned int g_num_edges(graph_t g);
/* Insert a new vertex into the graph with the provided metadata; the
vertex will be assigned an id (based on the order it is added) that can be
used to quickly retrieve it */
vertex_t g_vertex_add(graph_t g, void* metadata);
/* Insert a new vertex into the graph by id with the provieded metadata; the
vertex will be assigned to the provided id that can be used to quickly
retrieve it;
NOTE: if id already has a vertex with that id, then NULL will be returned
NOTE: it is NOT recommended to mix using g_vertex_add and g_vertex_add_alt
NOTE: if possible, initialize the graph to hold the largest known id */
vertex_t g_vertex_add_alt(graph_t g, unsigned int id, void* metadata);
/* Remove the vertex from the graph, returning it
NOTE: It is up to the caller to free the memory using g_vertex_free()
NOTE: Default is to free all memory of those edges attached; use the
alt version if the memory is not alloc'd */
vertex_t g_vertex_remove(graph_t g, unsigned int id);
vertex_t g_vertex_remove_alt(graph_t g, unsigned int id, bool free_edge_metadata);
/* Retrieve a vertex based on it's assigned identifier */
vertex_t g_vertex_get(graph_t g, unsigned int id);
/* Add an edge between the source (src) vertex to the destination vertex
(dest) with the provided metadata. The edge is assigned an id for quick
retrieval */
edge_t g_edge_add(graph_t g, unsigned int src, unsigned int dest, void* metadata);
/* Remove an edge from the graph based on it's assigned identifier */
edge_t g_edge_remove(graph_t g, unsigned int id);
/* Retrieve an edge based on it's assigned identifier */
edge_t g_edge_get(graph_t g, unsigned int id);
/*******************************************************************************
* Vertex Properties / Functions
*******************************************************************************/
/* Get the id of the provided vertex */
unsigned int g_vertex_id(vertex_t v);
/* Get the number of edges into the provided vertex */
unsigned int g_vertex_num_edges_in(vertex_t v);
/* Get the number of edges out of the provided vertex */
unsigned int g_vertex_num_edges_out(vertex_t v);
/* Get the number metadata of the provided vertex */
void* g_vertex_metadata(vertex_t v);
/* Update the metadata for the vertex with the passed in data;
NOTE: it is up to the caller to free the original metadata, if necessary */
void g_vertex_metadata_update(vertex_t v, void* metadata);
/* Free the provided vertex; defaults to calling free on the metadata; use
the g_vertex_free_alt() and set free_metadata to false to not */
void g_vertex_free(vertex_t v);
void g_vertex_free_alt(vertex_t v, bool free_metadata);
/* Get edge idx from for the provided vertex; this is useful when one needs
to iterate over the edges that have the vertex as its source */
edge_t g_vertex_edge(vertex_t v, unsigned int idx);
/*******************************************************************************
* Edge Properties / Functions
*******************************************************************************/
/* Get the assigned id for the provided edge */
unsigned int g_edge_id(edge_t e);
/* Get the source vertex id for the provided edge */
unsigned int g_edge_src(edge_t e);
/* Get the destination vertex id for the provided edge */
unsigned int g_edge_dest(edge_t e);
/* Get the metadata for the provided edge */
void* g_edge_metadata(edge_t e);
/* Update the metadata for the edge with the passed in data;
NOTE: it is up to the caller to free the original metadata, if necessary */
void g_edge_metadata_update(edge_t e, void* metadata);
/* Free the provided edge; defaults to calling free on the metadata; use
the g_edge_free_alt() and set free_metadata to false to not */
void g_edge_free(edge_t e);
void g_edge_free_alt(edge_t e, bool free_metadata);
/*******************************************************************************
* Iterators - Iterate over the vertices and edges of a vertex easily
*******************************************************************************/
/* Macro to easily iterate over all the vertices in the graph
NOTE:
g - The graph
v - A vertex_t pointer that will hold the next vertex
i - An unsigned int that will be modified for the loop */
#define g_iterate_vertices(g, v, i) for (i = 0; i < g_vertices_inserted(g); i++) if ((v = g_vertex_get(g, i)) != NULL)
/* Macro to easily iterate over the edges from a vertex
NOTE:
v - The vertex
e - An edge_t pointer that will hold the edges in the loop
i - An unsigned int that will be modified during the loop */
#define g_iterate_edges(v, e, i) for (i = 0; i < g_vertex_num_edges_out(v); i++) if ((e = g_vertex_edge(v, i)) != NULL)
/* Return an array with a listing of the vertices in breadth first fashion;
this is useful for finding what order one should traverse the list starting
at vertex v in a bredth first fashion.
NOTE: Up to the caller to free the corresponding memory.
NOTE: size is set to the number of elements in the unsigned int array
NOTE: The returned array contains the vertex ids of each vertex, in order */
unsigned int* g_breadth_first_traverse(graph_t g, vertex_t v, unsigned int* size);
/* Return an array with a listing of the vertices in depth first fashion;
this is useful for finding what order one should traverse the graph
starting at vertex v in a depth first fashion.
NOTE: Up to the caller to free the corresponding memory
NOTE: size is set to the number of elements in the unsigned int array
NOTE: The returned array contains the vertex ids of each vertex, in order */
unsigned int* g_depth_first_traverse(graph_t g, vertex_t v, unsigned int* size);
#ifdef __cplusplus
} // extern "C"
#endif
#endif /* BARRUST_GRAPH_H__ */