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:
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.