• Choose a category
• All
• Classic-Fiction

By Root 1555 0

the list of adjacency-list structures. We begin by ensuring that the vertex does not exist in any adjacency list, that the vertex does exist in the list of adjacency-list structures, and that the adjacency list of the vertex is empty. After this, we remove the vertex by calling list_rem_next to remove the appropriate AdjList structure from the list. Last, we update the count of vertices in the graph by decreasing its vcount member of the graph data structure by 1.

The runtime complexity of graph_rem_vertex is O (V + E ), where V is the number of vertices in the graph and E is the number of edges. This is because searching every adjacency list is O (V + E ), searching the list of adjacency-list structures is O (V ), and calling list_rem_next is O (1).

graph_rem_edge

The graph_rem_edge operation removes an edge from a graph (see Example 11.2). Specifically, the call removes the vertex specified by data2 from the adjacency list of data1. We begin by ensuring that the first vertex exists in the graph. Once this has been verified, we remove the edge by calling set_remove to remove the vertex specified by data2 from the adjacency list of data1. The call to set_remove returns an error if data2 is not in the adjacency list of data1. Last, we update the count of edges in the graph by decreasing the ecount member of the graph data structure by 1.

The runtime complexity of graph_rem_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_remove are both O (V ) operations.

graph_adjlist

The graph_adjlist operation returns the AdjList structure containing the set of vertices adjacent to a specified vertex (see Example 11.2). To do this, we search the list of adjacency-list structures until we find the one that contains the specified vertex.

The runtime complexity of graph_adjlist is O (V ), where V is the number of vertices in the graph. This is because searching the list of adjacency-list structures runs in O (V ) time.

graph_is_adjacent

The graph_is_adjacent operation determines whether a specified vertex is adjacent to another (see Example 11.2). To do this, we locate the adjacency-list structure of the vertex specified by data1 and call set_is_member to determine if data2 is in its adjacency list.

The runtime complexity of graph_adjlist 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_is_member are both O (V ) operations.

graph_adjlists, graph_vcount, graph_ecount

These macros implement some of the simpler graph operations (see Example 11.1). Generally, they provide an interface for accessing and testing members of the Graph structure.

The runtime complexity of these operations is O (1) because accessing members of a structure is a simple task that runs in a constant amount of time.

Example 11.2. Implementation of the Graph Abstract Datatype

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

* *

* -------------------------------- graph.c ------------------------------- *

* *

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

#include

#include

#include "graph.h"

#include "list.h"

#include "set.h"

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

* *

* ------------------------------ graph_init ------------------------------ *

* *

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

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

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

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

* *

* Initialize the graph. *

* *

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

graph->vcount = 0;

graph->ecount = 0;

graph->match = match;

graph->destroy = destroy;

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

* *

* Initialize