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: Andrew Sutton (andrew.n.sutton_at_[hidden])
Date: 2010-01-05 09:08:16

> 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).

Andrew Sutton
andrew.n.sutton_at_[hidden]