[Boost-users] Confused with Depth-First-Search method, forward or cross edge found on a undirected graph ?

24 Jun 2013

      Hi there
I have a problem with the DFS method (Boost 1.53). 
I found when invoking the DFS method on a undirected graph, the "forward_or_cross_edge" was called more than one times. 
But as the document says "In an undirected graph this method is never called".
http://www.boost.org/doc/libs/1_53_0/libs/graph/doc/DFSVisitor.html

I performed the test based on the file_dependencies.cpp example
 (examples/file_dependencies.cpp; http://www.boost.org/doc/libs/1_53_0/libs/graph/doc/file_dependency_example....)
1)
Change the graph type from "bidirectionalS" to "undirected".
2)Implement all the 8 DFS vistor "event methods" (Initialize Vertex, Start Vertex, Discover Vertex, Examine Edge, Tree Edge, Back Edge, Forward or Cross Edge, Finish Vertex)
in the cycle_detector struct to print the vertex names, edge sources and targets.
3)comment out some code at the begining of the example cpp files as the topological_sort method raise exception upon the undirected graph.

The results: the forward_or_cross_edge method was called five times.

initialize_vertex: dax.h
initialize_vertex: yow.h
initialize_vertex: boz.h
initialize_vertex: zow.h
initialize_vertex: foo.cpp
initialize_vertex: foo.o
initialize_vertex: bar.cpp
initialize_vertex: bar.o
initialize_vertex: libfoobar.a
initialize_vertex: zig.cpp
initialize_vertex: zig.o
initialize_vertex: zag.cpp
initialize_vertex: zag.o
initialize_vertex: libzigzag.a
initialize_vertex: killerapp
start_vertex: dax.h
discover_vertex: dax.h
examine_edge: dax.h --> foo.cpp
tree_edge: dax.h --> foo.cpp
discover_vertex: foo.cpp
examine_edge: foo.cpp --> dax.h
back_edge: foo.cpp --> dax.h
examine_edge: foo.cpp --> zow.h
tree_edge: foo.cpp --> zow.h
discover_vertex: zow.h
examine_edge: zow.h --> foo.cpp
back_edge: zow.h --> foo.cpp
finish_vertex: zow.h
examine_edge: foo.cpp --> foo.o
tree_edge: foo.cpp --> foo.o
discover_vertex: foo.o
examine_edge: foo.o --> foo.cpp
back_edge: foo.o --> foo.cpp
examine_edge: foo.o --> libfoobar.a
tree_edge: foo.o --> libfoobar.a
discover_vertex: libfoobar.a
examine_edge: libfoobar.a --> foo.o
back_edge: libfoobar.a --> foo.o
examine_edge: libfoobar.a --> bar.o
tree_edge: libfoobar.a --> bar.o
discover_vertex: bar.o
examine_edge: bar.o --> bar.cpp
tree_edge: bar.o --> bar.cpp
discover_vertex: bar.cpp
examine_edge: bar.cpp --> dax.h
back_edge: bar.cpp --> dax.h
examine_edge: bar.cpp --> yow.h
tree_edge: bar.cpp --> yow.h
discover_vertex: yow.h
examine_edge: yow.h --> dax.h
back_edge: yow.h --> dax.h
examine_edge: yow.h --> bar.cpp
back_edge: yow.h --> bar.cpp
examine_edge: yow.h --> zag.cpp
tree_edge: yow.h --> zag.cpp
discover_vertex: zag.cpp
examine_edge: zag.cpp --> yow.h
back_edge: zag.cpp --> yow.h
examine_edge: zag.cpp --> boz.h
tree_edge: zag.cpp --> boz.h
discover_vertex: boz.h
examine_edge: boz.h --> bar.cpp
back_edge: boz.h --> bar.cpp
examine_edge: boz.h --> zig.cpp
tree_edge: boz.h --> zig.cpp
discover_vertex: zig.cpp
examine_edge: zig.cpp --> boz.h
back_edge: zig.cpp --> boz.h
examine_edge: zig.cpp --> zig.o
tree_edge: zig.cpp --> zig.o
discover_vertex: zig.o
examine_edge: zig.o --> zig.cpp
back_edge: zig.o --> zig.cpp
examine_edge: zig.o --> libzigzag.a
tree_edge: zig.o --> libzigzag.a
discover_vertex: libzigzag.a
examine_edge: libzigzag.a --> libfoobar.a
back_edge: libzigzag.a --> libfoobar.a
examine_edge: libzigzag.a --> zig.o
back_edge: libzigzag.a --> zig.o
examine_edge: libzigzag.a --> zag.o
tree_edge: libzigzag.a --> zag.o
discover_vertex: zag.o
examine_edge: zag.o --> zag.cpp
back_edge: zag.o --> zag.cpp
examine_edge: zag.o --> libzigzag.a
back_edge: zag.o --> libzigzag.a
finish_vertex: zag.o
examine_edge: libzigzag.a --> killerapp
tree_edge: libzigzag.a --> killerapp
discover_vertex: killerapp
examine_edge: killerapp --> libzigzag.a
back_edge: killerapp --> libzigzag.a
finish_vertex: killerapp
finish_vertex: libzigzag.a
finish_vertex: zig.o
finish_vertex: zig.cpp
examine_edge: boz.h --> zag.cpp
back_edge: boz.h --> zag.cpp
finish_vertex: boz.h
examine_edge: zag.cpp --> zag.o
forward_or_cross_edge: zag.cpp --> zag.o            !!!!!!
finish_vertex: zag.cpp
finish_vertex: yow.h
examine_edge: bar.cpp --> boz.h
forward_or_cross_edge: bar.cpp --> boz.h             !!!!!!
examine_edge: bar.cpp --> bar.o
back_edge: bar.cpp --> bar.o
finish_vertex: bar.cpp
examine_edge: bar.o --> libfoobar.a
back_edge: bar.o --> libfoobar.a
finish_vertex: bar.o
examine_edge: libfoobar.a --> libzigzag.a
forward_or_cross_edge: libfoobar.a --> libzigzag.a    !!!!!!
finish_vertex: libfoobar.a
finish_vertex: foo.o
finish_vertex: foo.cpp
examine_edge: dax.h --> bar.cpp 
forward_or_cross_edge: dax.h --> bar.cpp    !!!!!!
examine_edge: dax.h --> yow.h
forward_or_cross_edge: dax.h --> yow.h      !!!!!!
finish_vertex: dax.h

What is the problem?
Thanks.
Zhiyu

2013-06-24 

lizy10b