[Boost-users] [graph] how to find all vertices reachable from one edge of a starting vertex

[Michael Marcin]

How can I find all vertices reachable by following one specified out-edge?

Is there already an algorithm that does this?

If not I think I could do it by:

- marking all vertices white
- mark starting vertex gray
- depth_first_visit the target of the specified edge

Does this work?

_______________________________________________
Boost-users mailing list
Boost...@lists.boost.org
http://lists.boost.org/mailman/listinfo.cgi/boost-users

[Jeremiah Willcock]

>________________________________
> From: Michael Marcin <mike....@gmail.com>
>To: boost...@lists.boost.org
>Sent: Saturday, September 13, 2014 11:12 AM
>Subject: [Boost-users] [graph] how to find all vertices reachable from one edge of a starting vertex

>
>
>How can I find all vertices reachable by following one specified out-edge?
>
>Is there already an algorithm that does this?
>
>If not I think I could do it by:
>
>- marking all vertices white
>- mark starting vertex gray
>- depth_first_visit the target of the specified edge

I may be misunderstanding what you are trying to do, but isn't the set of vertices reachable from the edge the same as the set reachable from its target? In that case, a normal BFS or DFS from the target of the edge would solve your problem directly.

-- Jeremiah Willcock

[Michael Marcin]

On 9/14/2014 11:11 AM, Jeremiah Willcock wrote:
>> ________________________________
>> From: Michael Marcin <mike....@gmail.com>
>> To: boost...@lists.boost.org
>> Sent: Saturday, September 13, 2014 11:12 AM
>> Subject: [Boost-users] [graph] how to find all vertices reachable from one edge of a starting vertex
>>
>>
>> How can I find all vertices reachable by following one specified out-edge?
>>
>> Is there already an algorithm that does this?
>>
>> If not I think I could do it by:
>>
>> - marking all vertices white
>> - mark starting vertex gray
>> - depth_first_visit the target of the specified edge
>
> I may be misunderstanding what you are trying to do, but isn't the set of vertices reachable from the edge the same as the set reachable from its target? In that case, a normal BFS or DFS from the target of the edge would solve your problem directly.
>

Well first if I understand correctly depth_first_search will visit all
vertices in the graph even if I pass it a start.

I could be wrong but if I have an undirected graph
with vertices:
A, B, C, D
with edges:
AB
BC
CD

If I want to select all vertices down the BC edge I want the result
vertex set to be:
BCD

If I depth_first_visit C it will find the edge CB it will see the B is
white and traverse its edges finding BA which is an edge I don't want
followed.