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 <tiago@skewed.de>