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@gmail.com