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.

Post a Comment

Note: (1) You need to have third-party cookies enabled in order to comment on Blogger. (2) Better to copy your comment before hitting publish/preview. Blogger sometimes eats comments on the first try, but the second works. Crazy Blogger.