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@osl.iu.edu C++ Booster (http://www.boost.org) office phone: (812) 855-3608 ----------------------------------------------------------------------