## 23 March 2005

### Topological sort

This entry is still in the spirit of: "let's do some low level processing" inspired by reading SGB. I'll say again that I consider this type of programming "fun" but too risky for real programming. However the main difference is not that big as it might appear at first sight. In a real program I would use std::list to handle adjacency list but otherwise the code would be pretty similar.

The problem I try to solve is a slightly modified topological sort. We are given a graph in an adjacency list representation.

   6:struct Node;
7:
8:struct Transition {
9:    Transition* next;
10:    Node* dest;
11:};
12:
13:struct Node {
14:    ~Node() {
15:        Transition *p, *t = transitions;
16:        while (p = t->next) {
17:            delete t;
18:            t = p;
19:        }
20:    }
21:
22:    string name;
23:
24:    Node* rs; // right in stage list
25:    Node* ls; // left in stage list
26:    Node* next; // next in graph
27:    int tag;
28:    Transition* transitions;
29:};
30:
31:struct Graph {
32:    Graph() {
33:        nodes = new Node;
34:        nodes->ls = nodes->rs = nodes;
35:    }
36:
37:    ~Graph() {
38:        Node *p, *t = nodes;
39:        while (p = t->next) {
40:            delete t;
41:            t = p;
42:        }
43:    }
44:
45:    Node* nodes; // this is a dummy node
46:};
47:
48:struct Stage {
49:    Stage* next;
50:    Node*  n;
51:};


We want to partition the nodes of the graph in a list of "stages". Each stage is a list of nodes. We want that (1) if the graph contains an edge from s to d then stage[s] comes before stage[d] in the stage list and (2) the stage list is as short as possible. We can use a greedy approach. Why that works is a good exercise. The (untested :( ) code follows

  57:    Stage *r = new Stage, *pr = r; // r is a dummy
58:
59:    // Reset tags and construct initial list
60:    Node *n, *d;
61:    for (n = g.nodes->next; n; n = n->next) {
62:        n->tag = 0;
63:        (n->ls = g.nodes->ls)->rs = n;
64:        (n->rs = g.nodes)->ls = n;
65:    }
66:
67:    // Count inbound edges
68:    Transition* t;
69:    for (n = g.nodes->next; n; n = n->next) {
70:        for (t = n->transitions; t; t = t->next) {
71:            d = t->dest;
72:            ++(d->tag);
73:            d->ls->rs = d->rs;
74:            d->rs->ls = d->ls;
75:            d->ls = d->rs = d;
76:        }
77:    }
78:
79:    // NOTE: if there are cycles and there is no topological sort this
80:    // function will return an incomplete result
81:    while (g.nodes->ls != g.nodes) {
82:        // Remember the current stage
83:        pr->next = new Stage;
84:        pr = pr->next;
85:        pr->n = g.nodes->ls;
86:        g.nodes->ls->rs = g.nodes->rs;
87:        g.nodes->rs->ls = g.nodes->ls;
88:        g.nodes->rs = g.nodes->ls = g.nodes;
89:
90:        // Compute next stage
91:        n = pr->n;
92:        do {
93:            for (t = n->transitions; t; t = t->next) {
94:                d = t->dest;
95:                if (--(d->tag) == 0) {
96:                    (d->ls = g.nodes->ls)->rs = d;
97:                    (d->rs = g.nodes)->ls = d;
98:                }
99:            }
100:            n = n->rs;
101:        } while (n != pr->n);
102:    }
103:
104:    pr->next = NULL; // this is the last stage
105:
106:    // the result is r


#### 1 comment:

Anonymous said...

Your ~Node() doesn't delete the last Transisition in the list, because it only considers a Transition for deletion if its *next* pointer isn't NULL.