Re: [BGL] Common children for vertices in DAG

From: Erik Arner (yg-boost-users_at_[hidden])
Date: 2002-08-06 12:02:08

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