Re: [PATCH] DFS fix.

[Michael Matz <matzmich at cs dot tu-berlin dot de>]

Hi Michael,

On Wed, 5 Jul 2000, Michael Hayes wrote:
> 
> If you look at my changes, the algorithm should now assign the dfs
> number of 0 to the node first completed.  Well, at least that is what
> I intended.

It does. But nevertheless this does not indicate, that it is the DFS
number (the order in which the nodes are first visited). The node first
visited has DFS number 0 (because it is first visited), but also "reversed
completion" number 0. The reverse completion number (compnum) is "number
of nodes - compnum", with compnum the order, in which the nodes are
leaved. As the first node visited is the last one leaved, it has compnum
number_of_nodes-1, which, when reversed is 0.

Consider the following graph:
A-->B-->C
\--->D

A dfs search rooted in A, and first following the edge to B leads to the
following numbers (RCN= reverse compnum):
          A  B  C  D
DFSnum    0  1  2  3
compnum   3  1  0  2
RCN       0  2  3  1

So for the first node 0==RCN==DFSnum (every time), but they are still not
the same. The nice property of RCN is, that if an edge goes from a node
with a high RCN to one with a lower RCN, its a back edge, and like this it
is also used in gcc. OTOH the DFSnum is not usable as indicator for
backedges, as the above would also detect cross edges.

This all is also mirrored in your code, you set the number for a node,
when it has no more unvisited children, in other words, when it is
completed.

> If you have any comments or suggestions to improve the code, I'll
> willingly install them.

No no, the code is nice, and does the right thing :) Only that its not the
DFSnum what it is calculating. May be I find time to prepare a patch for
the comments if you want.


Ciao,
Michael.