Mastering Algorithms With C - Kyle Loudon [116]
void (*destroy)(void *data));
Return Value
None.
Description
Initializes the graph specified by graph. This operation must be called for a graph before the graph can be used with any other operation. The match argument is a function used by various graph operations to determine if two vertices match. It should return 1 if key1 is equal to key2, and otherwise. The destroy argument provides a way to free dynamically allocated data when graph_destroy is called. For example, if the graph contains data dynamically allocated using malloc, destroy should be set to free to free the data as the graph is destroyed. For structured data containing several dynamically allocated members, destroy should be set to a user-defined function that calls free for each dynamically allocated member as well as for the structure itself. For a graph containing data that should not be freed, destroy should be set to NULL.
Complexity
O (1)
Name
graph_destroy
Synopsis
void graph_destroy(Graph *graph);
Return Value
None.
Description
Destroys the graph specified by graph. No other operations are permitted after calling graph_destroy unless graph_init is called again. The graph_destroy operation removes all vertices and edges from a graph and calls the function passed as destroy to graph_init once for each vertex or edge as it is removed, provided destroy was not set to NULL.
Complexity
O (V +E ), where V is the number of vertices in the graph and E is the number of edges.
Name
graph_ins_vertex
Synopsis
int graph_ins_vertex(Graph *graph, const void *data);
Return Value
0if inserting the vertex is successful, 1 if the vertex already exists, or -1 otherwise.
Description
Inserts a vertex into the graph specified by graph. The new vertex contains a pointer to data, so the memory referenced by data should remain valid as long as the vertex remains in the graph. It is the responsibility of the caller to manage the storage associated with data.
Complexity
O (V ) , where V is the number of vertices in the graph.
Name
graph_ins_edge
Synopsis
int graph_ins_edge(Graph *graph, const void *data1, const void *data2);
Return Value
0if inserting the edge is successful, 1 if the edge already exists, or -1 otherwise.
Description
Inserts an edge from the vertex specified by data1 to the vertex specified by data2 in the graph specified by graph. Both vertices must have been inserted previously using graph_ins_vertex. The new edge is represented with a pointer to data2 in the adjacency list of the vertex specified by data1, so the memory referenced by data2 should remain valid as long as the edge remains in the graph. It is the responsibility of the caller to manage the storage associated with data2. To enter an edge (u, v) in an undirected graph, call this operation twice: once to insert an edge from u to v, and again to insert the implied edge from v to u. This type of representation is common for undirected graphs.
Complexity
O (V ), where V is the number of vertices in the graph.
Name
graph_rem_vertex
Synopsis
int graph_rem_vertex(Graph *graph, void **data);
Return Value
0if removing the vertex is successful, or -1 otherwise.
Description
Removes the vertex matching data from the graph specified by graph. All edges incident to and from the vertex must have been removed previously using graph_rem_edge. Upon return, data points to the data stored in the vertex that was removed. It is the responsibility of the caller to manage the storage associated with the data.
Complexity
O (V + E ), where V is the number of vertices in the graph and E is the number of edges.
Name
graph_rem_edge
Synopsis
int graph_rem_edge(Graph *graph, const void *data1, void **data2);
Return Value
0if removing the edge is successful, or -1 otherwise.
Description
Removes the edge from data1 to data2 in the graph specified by graph . Upon return, data2 points to the data stored in the adjacency list of the vertex specified by data1. It is the responsibility of the caller to manage the storage associated