Traversing DAGs

Author:	Wojciech Muła
Added on:	2011-04-11

If a DAG has got one component, then the simplest traversing method is depth-first-search, which could be easily implemented recursively (using an implicit stack).

struct DAGNode {
        // user data
        bool    visited;        // after construction = 0
}

void DFS_aux(DAGNode* node, const bool val) {
        if (node->visited != val) {
                // visit node

                node->visited = val;
                for (n in node.connected)
                        DFS_aux(n, val)
        }
}

void DFS(DAGNode node) {
        static val = true;

        DFS_aux(node, val);
        val = not val;
}

On every call of DFS() the variable val is switched, and visited member is marked alternately with true or false.

There is just one problem — what if a traversing method stop execution before visiting all nodes? Of course in such situation we have to visit the DAG twice: on first pass reset (possibly many times) visited member to false, and then visit once each node.

But usually bool have at least 8 bits, so numbers could be used instead of boolean values 0 or 1. On each call of DFS() a reference number is incremented, thanks to that even if previous call stopped in the middle, the procedure will work correctly.

The only moment when visited markers have to be cleared is wrapping a reference numbers to zero. This happen every 256 calls if 8-bit values used; for wider counters (16, 32 bits) max value is greater.

void DFS(DAGNode node) {
        static unsigned int val = 1;
        if (val == 0) {
                // set visited member of all nodes to 0
                val += 1;
        }

        DFS_aux(node, val);
        val += 1;
}