[graph-tool] Why DFS `discoveres` the vertex, that it should not?

Tiago de Paula Peixoto tiago at skewed.de
Mon Mar 4 16:38:11 CET 2013


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 at skewed.de>

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 555 bytes
Desc: OpenPGP digital signature
URL: <https://lists.skewed.de/pipermail/graph-tool/attachments/20130304/58c3426f/attachment.asc>


More information about the graph-tool mailing list