Root/tsort.c

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