src/tsort.c

   1 /* tsort.c -- topological sort for vlock, the VT locking program for linux
   2  *
   3  * This program is copyright (C) 2007 Frank Benkstein, and is free
   4  * software which is freely distributable under the terms of the
   5  * GNU General Public License version 2, included as the file COPYING in this
   6  * distribution.  It is NOT public domain software, and any
   7  * redistribution not permitted by the GNU General Public License is
   8  * expressly forbidden without prior written permission from
   9  * the author.
  10  *
  11  */
  12
  13 #include <stdlib.h>
  14
  15 #include "list.h"
  16
  17 #include "tsort.h"
  18
  19 /* Get the zeros of the graph, i.e. nodes with no incoming edges. */
  20 static struct list *get_zeros(struct list *nodes, struct list *edges)
  21 {
  22   struct list *zeros = list_copy(nodes);
  23
  24   list_for_each(edges, edge_item) {
  25     struct edge *e = edge_item->data;
  26     list_delete(zeros, e->successor);
  27   }
  28
  29   return zeros;
  30 }
  31
  32 /* Check if the given node is a zero. */
  33 static bool is_zero(void *node, struct list *edges)
  34 {
  35   list_for_each(edges, edge_item) {
  36     struct edge *e = edge_item->data;
  37
  38     if (e->successor == node)
  39       return false;
  40   }
  41
  42   return true;
  43 }
  44
  45 /* For the given directed graph, generate a topological sort of the nodes.
  46  *
  47  * Sorts the list and deletes all edges.  If there are circles found in the
  48  * graph or there are edges that have no corresponding nodes the erroneous
  49  * edges are left.
  50  *
  51  * The algorithm is taken from the Wikipedia:
  52  *
  53  * http://en.wikipedia.org/w/index.php?title=Topological_sorting&oldid=153157450#Algorithms
  54  *
  55  */
  56 void tsort(struct list *nodes, struct list *edges)
  57 {
  58   struct list *sorted_nodes = list_new();
  59   /* Retrieve all zeros. */
  60   struct list *zeros = get_zeros(nodes, edges);
  61
  62   /* While the list of zeros is not empty, take the first zero and remove it
  63    * and ...  */
  64   list_delete_for_each(zeros, zero_item) {
  65     void *zero = zero_item->data;
  66     /* ... add it to the list of sorted nodes. */
  67     list_append(sorted_nodes, zero);
  68
  69     /* Then look at each edge ... */
  70     list_for_each_manual(edges, edge_item) {
  71       struct edge *e = edge_item->data;
  72
  73       /* ... that has this zero as its predecessor ... */
  74       if (e->predecessor == zero) {
  75         /* ... and remove it. */
  76         edge_item = list_delete_item(edges, edge_item);
  77
  78         /* If the successor has become a zero now ... */
  79         if (is_zero(e->successor, edges))
  80           /* ... add it to the list of zeros. */
  81           list_append(zeros, e->successor);
  82
  83         free(e);
  84       } else {
  85         edge_item = edge_item->next;
  86       }
  87     }
  88   }
  89
  90   /* If all edges were deleted the algorithm was successful. */
  91   if (list_is_empty(edges)) {
  92     /* Switch the given list of nodes for the list of sorted nodes. */
  93     struct list_item *first = sorted_nodes->first;
  94     struct list_item *last = sorted_nodes->last;
  95
  96     sorted_nodes->first = nodes->first;
  97     sorted_nodes->last = nodes->last;
  98
  99     nodes->first = first;
 100     nodes->last = last;
 101   }
 102
 103   list_free(sorted_nodes);
 104 }