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; }