Re: [Boost-Users] BGL: Loops in undirected graph

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2002-08-19 10:30:07

Hi Tarjei,

On 19 Aug 2002, Tarjei Knapstad wrote:
tarjei>
tarjei> Why is this? I'm assuming there's something I missed out on, regarding
tarjei> graph theory and how the basic DFS works, but I cannot see any logic in
tarjei> this. If so, how could I modify my DFS visitor to record the (in my
tarjei> problem domain) "correct" back edges?

Hmmm, yes. What is happening is that there is some ambiguity in the
definition of tree edge and back edge for DFS on an undirected graph. In
fact, all tree edges are also back edges. The typical way to deal with
this is that if there are two ways to classify the edge, the first
classification given to the edge is the one that wins. See page 483 of
Introduction to Algorithms by Cormen, et. all.

It would have required extra data-structure support to put this into the
BGL DFS algorithm, and I'm afraid I never got around to it.

One way to deal with this is to color edges when they are visited, and if
they are visited a second time then ignore them. You can do this in your
visitor for now. I'll look into adding this inside the DFS.

Cheers,
Jeremy

----------------------------------------------------------------------
 Jeremy Siek                          http://php.indiana.edu/~jsiek/
 Ph.D. Student, Indiana Univ. B'ton   email: jsiek_at_[hidden]
 C++ Booster (http://www.boost.org)   office phone: [phone]
----------------------------------------------------------------------