Is there any "standard best way" of detecting loops in an undirected graph? I had a look at chapter 4.2 in the book (which does an implementation for bidirectional graphs), and tried to adapt this implementation, but with no particular luck :) The graph I've set up in my test suite looks like this (I hope my mail prog. doesn't screw up the formatting) H15 | H8 C2 \ / \ H9-C0-C1 C3-O7-H14 / | | H10 C6 C4 / \ / \ H11 C5 H13 | H12 I'm working with molecules, so the letters denote the type of atom, but that's of no importance here. The numbers are the vertex descriptors. What I'm trying to create is an algorithm that will return the set of vertices [1, 2, 3, 4, 5, 6] defining. Now, my first step is (exactly like in the book) to record every back edge in the graph. As my graph is undirected, and there is allways a path from any one vertex to any other vertex, I thought I could just do a DFS from the first vertex in any such graph and record the back edges. In the above example, starting from 'C0', I'd expect the set of back edges obtained from a DFS to be 1-2, 2-3, 3-4, 4-5, 5-6 and 6-1, a total of 6 edges. The actual result obtained however also includes the following edges: 1-0, 11-6, 12-5, 13-4, 7-3, 14-7, 15-2, 8-0, 9-0 and 10-0. Why is this? I'm assuming there's something I missed out on, regarding graph theory and how the basic DFS works, but I cannot see any logic in this. If so, how could I modify my DFS visitor to record the (in my problem domain) "correct" back edges? This problem also gives me further trouble when trying to detect which vertices are part of each cycle. Does any of you have any suggestion for an effective implementation of the "find vertices that are part of each cycle" part of the algorithm? Any help appreciated. Cheers, -- Tarjei Knapstad
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 ----------------------------------------------------------------------
I just noticed that the online docs for DFS mention the tree edge/back edge ambiguity, though it looks like that didn't get into the BGL book. http://www.boost.org/libs/graph/doc/depth_first_search.html BTW, the solution suggested in the online docs (recording predecessors) only words for graphs without parallel edges. A more general approach is to mark the edges themselves as I suggested in the previous email. Regards, 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 ----------------------------------------------------------------------
I've added a new function, undirected_dfs, that treats tree and back edgess properly. The function takes one more parameter than the depth_first_search function: an edge color map. 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 ----------------------------------------------------------------------
On Mon, 2002-08-19 at 19:02, Jeremy Siek wrote:
I've added a new function, undirected_dfs, that treats tree and back edgess properly. The function takes one more parameter than the depth_first_search function: an edge color map.
Just about done implementing it myself in accordance with your initial suggestion :) Thanks (once again) for helping a graph novice out Jeremy. -- Tarjei Knapstad
participants (2)
-
Jeremy Siek
-
Tarjei Knapstad