graph.c

掌握如何用C来实现各种算法

*  Traverse each adjacency list and the vertices it contains.                *
*                                                                            *
*****************************************************************************/

prev = NULL;
found = 0;

for (element = list_head(&graph->adjlists); element != NULL; element =
   list_next(element)) {

   /**************************************************************************
   *                                                                         *
   *  Do not allow removal of the vertex if it is in an adjacency list.      *
   *                                                                         *
   **************************************************************************/

   if (set_is_member(&((AdjList *)list_data(element))->adjacent, *data))
      return -1;

   /**************************************************************************
   *                                                                         *
   *  Keep a pointer to the vertex to be removed.                            *
   *                                                                         *
   **************************************************************************/

   if (graph->match(*data, ((AdjList *)list_data(element))->vertex)) {
 
      temp = element;
      found = 1;

   }

   /**************************************************************************
   *                                                                         *
   *  Keep a pointer to the vertex before the vertex to be removed.          *
   *                                                                         *
   **************************************************************************/

   if (!found)
      prev = element;

}
 
/*****************************************************************************
*                                                                            *
*  Return if the vertex was not found.                                       *
*                                                                            *
*****************************************************************************/

if (!found)
   return -1;

/*****************************************************************************
*                                                                            *
*  Do not allow removal of the vertex if its adjacency list is not empty.    *
*                                                                            *
*****************************************************************************/

if (set_size(&((AdjList *)list_data(temp))->adjacent) > 0)
   return -1;

/*****************************************************************************
*                                                                            *
*  Remove the vertex.                                                        *
*                                                                            *
*****************************************************************************/

if (list_rem_next(&graph->adjlists, prev, (void **)&adjlist) != 0)
   return -1;

/*****************************************************************************
*                                                                            *
*  Free the storage allocated by the abstract data type.                     *
*                                                                            *
*****************************************************************************/

*data = adjlist->vertex;
free(adjlist);

/*****************************************************************************
*                                                                            *
*  Adjust the vertex count to account for the removed vertex.                *
*                                                                            *
*****************************************************************************/

graph->vcount--;

return 0;

}

/*****************************************************************************
*                                                                            *
*  ---------------------------- graph_rem_edge ----------------------------  *
*                                                                            *
*****************************************************************************/

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

ListElmt           *element;

/*****************************************************************************
*                                                                            *
*  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);

}