Jeremy Siek wrote:

Hi Erik,

On Mon, 5 Aug 2002, Erik Arner wrote: yg-boo> yg-boo> Is there a fast way, with or without preprocessing of the graph, for yg-boo> checking if two non-adjacent vertices in a DAG have one or more common yg-boo> children? Any pointers to components of the BGL that implement, or can yg-boo> be used to implement, this task would be much appreciated.

If you use a bidirectional graph (with both in and out edges), then you can do the following in average O(V*E) time.

for each vertex c for each in-edge e1 of c for each in-edge e2 of c { p1 = source(e1); p2 = source(e2); if (!(is_adjacent(p1, p2) || is_adjacent(p2, p1))) parents_with_common_children.push_back(make_pair(p1,p2)); }

OK thanks, I now realize I formulated the question wrongly. What I really was looking for is a fast method for determining whether two vertices have common *descendants*, not necessarily children... I might have to perform this task many times during the run of the program, so it really needs to be fast. Any thoughts? Maybe this is really stupid, but consider the following: if the graph was undirected, I could preprocess (potentially time consuming, I admit) by performing johnson_all_pairs_shortest_paths and store the result. Then I would have constant time lookup of whether two vertices are connected in some way just by checking for a non-infinity value of the shortest path between them. But my graph is, alas, directed so this doesn't seem feasible unless there is some way to (temporarily) regard the graph as undirected. Any ideas would be much appreciated. Please excuse my uneducated ramblings on this subject - I am a newbie at graph theory, and I ordered the BGL book but it hasn't arrived yet and my deadline is in a week... :-\ Thanks Erik

Jeremy Siek wrote:

Yeah, what you want is the transitive closure of the reverse graph. This adds edges such that all descendants become children.

Well well well... This is exactly what I'm looking for! Thanks! /Erik