Root/tsort.c

Source at commit bc27b094af74a7c6f8b71ceaa63d1ba80d067cbb created 9 years 4 months ago.
By werner, With a little help from m8cutils and abyss, we now have regression tests for the topological sort. "make test" or "make tests" invokes the regression tests, "make valgrind" runs them under valgrind's watchful eyes.
1/*
2 * tsort.c - Topological sort
3 *
4 * Written 2010 by Werner Almesberger
5 * Copyright 2010 by Werner Almesberger
6 *
7 * This program is free software; you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation; either version 2 of the License, or
10 * (at your option) any later version.
11 */
12
13/*
14 * We use a slight variation of Kahn's algorithm. The difference is that we add
15 * a priority. Edges with the highest priority get selected before edges with
16 * lower priority.
17 *
18 * We maintain the initial list of nodes in the order in which they were added.
19 * Therefore, the first node with inbound edges will always be sorted first.
20 * E.g., the root frame.
21 *
22 * add_node and add_edge can be invoked multiple times with the same
23 * parameters. In the case of add_node, simply the existing node is returned.
24 * In the case of add_edge, the new edge's priority is added to the priority of
25 * the previous edges.
26 *
27 * Priority is accumulated in a node until the node is output. If a node has
28 * the "decay" flag set, it resets the priorities of all other nodes when
29 * output. E.g., when outputting a vector, all priorities accumulated from
30 * previous vectors (towards referencing them with ".") lose their effect.
31 *
32 * Last but not least, the algorithm is stable: a pre-existing order that
33 * conflicts neither with the partial order nor the priorities is preserved.
34 *
35 * Thus, we have the following sorting criteria, in decreasing importance:
36 * - the destination if an edge never precedes its origin
37 * - higher priority comes before lower priority
38 * - earlier add_node comes before later
39 */
40
41
42#include <stdlib.h>
43#include <stdio.h>
44#include <limits.h>
45
46#include "util.h"
47#include "tsort.h"
48
49
50struct edge {
51    struct node *to;
52    int priority; /* edge priority */
53    struct edge *next;
54};
55
56struct node {
57    void *user;
58    struct edge *edges; /* outbound edges */
59    int incoming; /* number of incoming edges */
60    int priority; /* cumulative node priority */
61    int decay; /* all node prio. decay after issuing this */
62    struct node *next;
63};
64
65struct tsort {
66    struct node *nodes;
67    struct node **next_node;
68    int n_nodes;
69};
70
71
72void add_edge(struct node *from, struct node *to, int priority)
73{
74    struct edge **edge;
75
76    for (edge = &from->edges; *edge; edge = &(*edge)->next)
77        if ((*edge)->to == to) {
78            (*edge)->priority += priority;
79            return;
80        }
81    *edge = alloc_type(struct edge);
82    (*edge)->to = to;
83    (*edge)->priority = priority;
84    (*edge)->next = NULL;
85    to->incoming++;
86}
87
88
89struct node *add_node(struct tsort *tsort, void *user, int decay)
90{
91    struct node *node;
92
93    for (node = tsort->nodes; node; node = node->next)
94        if (node->user == user)
95            return node;
96    node = alloc_type(struct node);
97    node->user = user;
98    node->edges = NULL;
99    node->incoming = 0;
100    node->priority = 0;
101    node->decay = decay;
102    node->next = NULL;
103    *tsort->next_node = node;
104    tsort->next_node = &node->next;
105    tsort->n_nodes++;
106    return node;
107}
108
109
110struct tsort *begin_tsort(void)
111{
112    struct tsort *tsort;
113
114    tsort = alloc_type(struct tsort);
115    tsort->nodes = NULL;
116    tsort->next_node = &tsort->nodes;
117    tsort->n_nodes = 0;
118    return tsort;
119}
120
121
122void **end_tsort(struct tsort *tsort)
123{
124    struct node **walk, **first, *node;
125    struct edge *edge;
126    void **res;
127    int n = 0;
128
129    res = alloc_size(sizeof(void *)*(tsort->n_nodes+1));
130    while (1) {
131        first = NULL;
132        for (walk = &tsort->nodes; *walk; walk = &(*walk)->next) {
133            if ((*walk)->incoming)
134                continue;
135            if (!first || (*first)->priority < (*walk)->priority)
136                first = walk;
137        }
138        if (!first)
139            break;
140        if ((*first)->decay)
141            for (node = tsort->nodes; node; node = node->next)
142                node->priority = 0;
143        node = *first;
144        *first = node->next;
145        res[n++] = node->user;
146        while (node->edges) {
147            edge = node->edges;
148            edge->to->incoming--;
149            edge->to->priority += edge->priority;
150            node->edges = edge->next;
151            free(edge);
152        }
153        free(node);
154    }
155    if (tsort->nodes) {
156        fprintf(stderr, "cycle detected in partial order\n");
157        abort();
158    }
159    free(tsort);
160    res[n] = NULL;
161    return res;
162}
163

Archive Download this file

Branches:
master



interactive