Re: [Boost-users] [BGL] simple problem: how to detect connections in a dag?

Subject: Re: [Boost-users] [BGL] simple problem: how to detect connections in a dag?
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2010-01-05 11:42:16

On Tue, 5 Jan 2010, Andrew Sutton wrote:

>
>       we have a rather simple problem here for which we however couldn't find a simple solution in the BGL. Probably because we aren't graph experts.
>       We have a dag and two vertices in this dag. Now we just want to know if these vertices are connected (acrtually we don't need the path), that is if one vertex is
>       in a parent chain of the other.
> 
> 
> You could use a function called edge(u, v, g) with u, v being vertex descriptors and g a graph. In a directed graph if u has v as the opposite end of an out edge, then this
> function will return the pair (e, true) with e being an edge descriptor. If v is not at the end of an out edge, then the function returns (x, false) with x being an invalid
> edge descriptor.
> 
> Performance varies depending on the type of g. For adjacency lists, the operation completes in O(deg(u)), for adjacency matrices it's O(1).

I think the question was asking for a path of arbitrary length; in that 
case, breadth_first_search or depth_first_search would find the path.  You 
can either check the color map or predecessor map to determine if a 
particular vertex was reached from your particular source vertex.

-- Jeremiah Willcock