Mastering Algorithms With C - Kyle Loudon [120]
* *
*****************************************************************************/
list_init(&graph->adjlists, NULL);
return;
}
/*****************************************************************************
* *
* ----------------------------- graph_destroy ---------------------------- *
* *
*****************************************************************************/
void graph_destroy(Graph *graph) {
AdjList *adjlist;
/*****************************************************************************
* *
* Remove each adjacency-list structure and destroy its adjacency list. *
* *
*****************************************************************************/
while (list_size(&graph->adjlists) > 0) {
if (list_rem_next(&graph->adjlists, NULL, (void **)&adjlist) == 0) {
set_destroy(&adjlist->adjacent);
if (graph->destroy != NULL)
graph->destroy(adjlist->vertex);
free(adjlist);
}
}
/*****************************************************************************
* *
* Destroy the list of adjacency-list structures, which is now empty. *
* *
*****************************************************************************/
list_destroy(&graph->adjlists);
/*****************************************************************************
* *
* No operations are allowed now, but clear the structure as a precaution. *
* *
*****************************************************************************/
memset(graph, 0, sizeof(Graph));
return;
}
/*****************************************************************************
* *
* --------------------------- graph_ins_vertex --------------------------- *
* *
*****************************************************************************/
int graph_ins_vertex(Graph *graph, const void *data) {
ListElmt *element;
AdjList *adjlist;
int retval;
/*****************************************************************************
* *
* Do not allow the insertion of duplicate vertices. *
* *
*****************************************************************************/
for (element = list_head(&graph->adjlists); element != NULL; element =
list_next(element)) {
if (graph->match(data, ((AdjList *)list_data(element))->vertex))
return 1;
}
/*****************************************************************************
* *
* Insert the vertex. *
* *
*****************************************************************************/
if ((adjlist = (AdjList *)malloc(sizeof(AdjList))) == NULL)
return -1;
adjlist->vertex = (void *)data;
set_init(&adjlist->adjacent, graph->match, NULL);
if ((retval = list_ins_next(&graph->adjlists, list_tail(&graph->adjlists),
adjlist)) != 0) {
return retval;
}
/*****************************************************************************
* *
* Adjust the vertex count to account for the inserted vertex. *
* *
*****************************************************************************/
graph->vcount++;
return 0;
}
/*****************************************************************************
* *
* ---------------------------- graph_ins_edge ---------------------------- *
* *
*****************************************************************************/
int graph_ins_edge(Graph *graph, const void *data1, const void *data2) {
ListElmt *element;
int retval;
/*****************************************************************************
* *
* Do not allow insertion of an edge without both its vertices in the graph. *
* *
*****************************************************************************/
for (element = list_head(&graph->adjlists); element != NULL; element =
list_next(element)) {
if (graph->match(data2, ((AdjList *)list_data(element))->vertex))
break;
}
if (element == NULL)
return -1;
for (element = list_head(&graph->adjlists); element != NULL; element =
list_next(element)) {
if (graph->match(data1, ((AdjList *)list_data(element))->vertex))
break;
}