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 #include <errno.h>
  15
  16 #include "util.h"
  17
  18 #include "tsort.h"
  19
  20 /* Get the zeros of the graph, i.e. nodes with no incoming edges. */
  21 static GList *get_zeros(GList *nodes, GList *edges)
  22 {
  23   GList *zeros = g_list_copy(nodes);
  24
  25   for (GList *edge_item = edges;
  26        edge_item != NULL;
  27        edge_item = g_list_next(edge_item)) {
  28     struct edge *e = edge_item->data;
  29     zeros = g_list_remove(zeros, e->successor);
  30   }
  31
  32   return zeros;
  33 }
  34
  35 /* Check if the given node is a zero. */
  36 static bool is_zero(void *node, GList *edges)
  37 {
  38   for (GList *edge_item = edges;
  39        edge_item != NULL;
  40        edge_item = g_list_next(edge_item)) {
  41     struct edge *e = edge_item->data;
  42
  43     if (e->successor == node)
  44       return false;
  45   }
  46
  47   return true;
  48 }
  49
  50 /* For the given directed graph, generate a topological sort of the nodes.
  51  *
  52  * Sorts the list and deletes all edges.  If there are circles found in the
  53  * graph or there are edges that have no corresponding nodes the erroneous
  54  * edges are left.
  55  *
  56  * The algorithm is taken from the Wikipedia:
  57  *
  58  * http://en.wikipedia.org/w/index.php?title=Topological_sorting&oldid=153157450#Algorithms
  59  *
  60  */
  61 GList *tsort(GList *nodes, GList **edges)
  62 {
  63   /* Retrieve all zeros. */
  64   GList *zeros = get_zeros(nodes, *edges);
  65
  66   GList *sorted_nodes = NULL;
  67
  68   /* While the list of zeros is not empty ... */
  69   while (zeros != NULL) {
  70     /* ... take the first zero and remove it and ...*/
  71     void *zero = zeros->data;
  72     zeros = g_list_delete_link(zeros, zeros);
  73
  74     /* ... add it to the list of sorted nodes. */
  75     sorted_nodes = g_list_append(sorted_nodes, zero);
  76
  77     /* Then look at each edge ... */
  78     for (GList *edge_item = *edges;
  79          edge_item != NULL;) {
  80       struct edge *e = edge_item->data;
  81
  82       GList *tmp = g_list_next(edge_item);
  83
  84       /* ... that has this zero as its predecessor ... */
  85       if (e->predecessor == zero) {
  86         /* ... and remove it. */
  87         *edges = g_list_delete_link(*edges, edge_item);
  88
  89         /* If the successor has become a zero now ... */
  90         if (is_zero(e->successor, *edges))
  91           /* ... add it to the list of zeros. */
  92           zeros = g_list_append(zeros, e->successor);
  93
  94         g_free(e);
  95       }
  96
  97       edge_item = tmp;
  98     }
  99   }
 100
 101   /* If all edges were deleted the algorithm was successful. */
 102   if (*edges != NULL) {
 103     g_list_free(sorted_nodes);
 104     sorted_nodes = NULL;
 105   }
 106
 107   g_list_free(zeros);
 108
 109   return sorted_nodes;
 110   ;
 111 }
 112