On 03/04/2013 03:22 PM, shpavel wrote: > i have a very simple directed graph: > V0 -> V2 > V1 -> V2 > > i use BFS and DFS algorithms starting from V0 and get different results from > `discover_vertex` function: > for BFS it does not discover V1, that is correct - there is no path from V0 > to V1 > but for DFS it does discover V1
This seems to be the default behavior of the depth_first_search()
function in boost. See:
http://www.boost.org/doc/libs/1_53_0/libs/graph/doc/depth_first_search.html
Note that in this function _all_ vertices are eventually visited, not
only the (out-)component from the source! I don't really understand why
it was done like this, since, as you observed, it is inconsistent with
BFS. I have modified the code in graph-tool to use the function
depth_first_visit() instead, where this is avoided, and the expected
behavior is obtained. Just try the current git version.
Thanks for the very simple example.
Cheers,
Tiago
--
Tiago de Paula Peixoto <[email protected]>
signature.asc
Description: OpenPGP digital signature
_______________________________________________ graph-tool mailing list [email protected] http://lists.skewed.de/mailman/listinfo/graph-tool
