Mastering Algorithms With C - Kyle Loudon [122]
* *
* Locate the adjacency list for the first vertex. *
* *
*****************************************************************************/
for (element = list_head(&graph->adjlists); element != NULL; element =
list_next(element)) {
if (graph->match(data1, ((AdjList *)list_data(element))->vertex))
break;
}
if (element == NULL)
return -1;
/*****************************************************************************
* *
* Remove the second vertex from the adjacency list of the first vertex. *
* *
*****************************************************************************/
if (set_remove(&((AdjList *)list_data(element))->adjacent, data2) != 0)
return -1;
/*****************************************************************************
* *
* Adjust the edge count to account for the removed edge. *
* *
*****************************************************************************/
graph->ecount--;
return 0;
}
/*****************************************************************************
* *
* ----------------------------- graph_adjlist ---------------------------- *
* *
*****************************************************************************/
int graph_adjlist(const Graph *graph, const void *data, AdjList **adjlist) {
ListElmt *element,
*prev;
/*****************************************************************************
* *
* Locate the adjacency list for the vertex. *
* *
*****************************************************************************/
prev = NULL;
for (element = list_head(&graph->adjlists); element != NULL; element =
list_next(element)) {
if (graph->match(data, ((AdjList *)list_data(element))->vertex))
break;
prev = element;
}
/*****************************************************************************
* *
* Return if the vertex was not found. *
* *
*****************************************************************************/
if (element == NULL)
return -1;
/*****************************************************************************
* *
* Pass back the adjacency list for the vertex. *
* *
*****************************************************************************/
*adjlist = list_data(element);
return 0;
}
/*****************************************************************************
* *
* --------------------------- graph_is_adjacent -------------------------- *
* *
*****************************************************************************/
int graph_is_adjacent(const Graph *graph, const void *data1, const void
*data2) {
ListElmt *element,
*prev;
/*****************************************************************************
* *
* Locate the adjacency list of the first vertex. *
* *
*****************************************************************************/
prev = NULL;
for (element = list_head(&graph->adjlists); element != NULL; element =
list_next(element)) {
if (graph->match(data1, ((AdjList *)list_data(element))->vertex))
break;
prev = element;
}
/*****************************************************************************
* *
* Return if the first vertex was not found. *
* *
*****************************************************************************/
if (element == NULL)
return 0;
/*****************************************************************************
* *
* Return whether the second vertex is in the adjacency list of the first. *
* *
*****************************************************************************/
return set_is_member(&((AdjList *)list_data(element))->adjacent, data2);
}
Graph Example: Counting Network Hops
Graphs play an important part in solving many networking problems. One problem, for example, is determining the best way to get from one node to another in an internet, a network of gateways into other networks. One way to model an internet is using an undirected graph in which vertices represent nodes, and edges represent connections between the nodes. With this model, we can use breadth-first