• Choose a category
• All
• Classic-Fiction

} Graph;

/*****************************************************************************

* *

* Define colors for vertices in graphs. *

* *

*****************************************************************************/

typedef enum VertexColor_ {white, gray, black} VertexColor;

/*****************************************************************************

* *

* --------------------------- Public Interface --------------------------- *

* *

*****************************************************************************/

void graph_init(Graph *graph, int (*match)(const void *key1, const void

*key2), void (*destroy)(void *data));

void graph_destroy(Graph *graph);

int graph_ins_vertex(Graph *graph, const void *data);

int graph_ins_edge(Graph *graph, const void *data1, const void *data2);

int graph_rem_vertex(Graph *graph, void **data);

int graph_rem_edge(Graph *graph, void *data1, void **data2);

int graph_adjlist(const Graph *graph, const void *data, AdjList **adjlist);

int graph_is_adjacent(const Graph *graph, const void *data1, const void

*data2);

#define graph_adjlists(graph) ((graph)->adjlists)

#define graph_vcount(graph) ((graph)->vcount)

#define graph_ecount(graph) ((graph)->ecount)

#endif

graph_init

The graph_init operation initializes a graph so that it can be used in other operations (see Example 11.2). Initializing a graph is a simple operation in which we set the vcount and ecount members of the graph to 0, encapsulate the match and destroy functions, and initialize the list of adjacency-list structures.

The runtime complexity of graph_init is O (1) because all of the steps in initializing a graph run in a constant amount of time.

graph_destroy

The graph_destroy operation destroys a graph (see Example 11.2). Primarily this means removing each adjacency-list structure, destroying the set of vertices it contains, and freeing the memory allocated to its vertex member by calling the function passed as destroy to graph_init, provided destroy was not set to NULL.

The runtime complexity of graph_destroy is O (V + E ), where V is the number of vertices in the graph and E is the number of edges. This is because we make V calls to the O (1) operation list_rem_next, and the total running time of all calls to set_destroy is O (E ).

graph_ins_vertex

The graph_ins_vertex operation inserts a vertex into a graph (see Example 11.2). Specifically, the call inserts an AdjList structure into the list of adjacency-list structures and sets its vertex member to point to the data passed by the caller. We begin by ensuring that the vertex does not already exist in the list. After this, we insert the vertex by calling list_ins_next to insert the AdjList structure at the tail of the list. Last, we update the count of vertices in the graph by incrementing the vcount member of the graph data structure.

The runtime complexity of graph_ins_vertex is O (V ), where V is the number of vertices in the graph. This is because searching the list of vertices for a duplicate is an O (V ) operation. The call to list_ins_next is O (1).

graph_ins_edge

The graph_ins_edge operation inserts an edge into a graph (see Example 11.2). To insert an edge from the vertex specified by data1 to the vertex specified by data2, we insert data2 into the adjacency list of data1. We begin by ensuring that both vertices exist in the graph. After this, we insert the vertex specified by data2 into the adjacency list of data1 by calling set_insert. The call to set_insert returns an error if the edge already exists. Last, we update the count of edges in the graph by incrementing the ecount member of the graph data structure.

The runtime complexity of graph_ins_edge is O (V ), where V is the number of vertices in the graph. This is because searching the list of adjacency-list structures and calling set_insert are both O (V ) operations.

graph_rem_vertex

The graph_rem_vertex operation removes a vertex from a graph (see Example 11.2). Specifically, the call removes an AdjList structure from