1
/* tsort.c -- topological sort for vlock, the VT locking program for linux
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
21
/* Get the zeros of the graph, i.e. nodes with no incoming edges. */
22
static struct list *get_zeros(struct list *nodes, struct list *edges)
24
struct list *zeros = list_copy(nodes);
29
list_for_each(edges, edge_item) {
30
struct edge *e = edge_item->data;
31
list_delete(zeros, e->successor);
37
/* Check if the given node is a zero. */
38
static bool is_zero(void *node, struct list *edges)
40
list_for_each(edges, edge_item) {
41
struct edge *e = edge_item->data;
43
if (e->successor == node)
50
/* For the given directed graph, generate a topological sort of the nodes.
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
56
* The algorithm is taken from the Wikipedia:
58
* http://en.wikipedia.org/w/index.php?title=Topological_sorting&oldid=153157450#Algorithms
61
struct list *tsort(struct list *nodes, struct list *edges)
63
struct list *sorted_nodes = list_new();
64
/* Retrieve all zeros. */
67
if (sorted_nodes == NULL)
70
zeros = get_zeros(nodes, edges);
73
GUARD_ERRNO(list_free(sorted_nodes));
77
/* While the list of zeros is not empty, take the first zero and remove it
79
list_delete_for_each(zeros, zero_item) {
80
void *zero = zero_item->data;
81
/* ... add it to the list of sorted nodes. */
82
if (!list_append(sorted_nodes, zero))
85
/* Then look at each edge ... */
86
list_for_each_manual(edges, edge_item) {
87
struct edge *e = edge_item->data;
89
/* ... that has this zero as its predecessor ... */
90
if (e->predecessor == zero) {
91
/* ... and remove it. */
92
edge_item = list_delete_item(edges, edge_item);
94
/* If the successor has become a zero now ... */
95
if (is_zero(e->successor, edges))
96
/* ... add it to the list of zeros. */
97
if (!list_append(zeros, e->successor))
102
edge_item = edge_item->next;
107
/* If all edges were deleted the algorithm was successful. */
108
if (!list_is_empty(edges)) {
109
list_free(sorted_nodes);
116
return sorted_nodes;;
121
list_free(sorted_nodes);