Re: [Boost-Users] [BGL] Common children for vertices in DAG

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2002-08-06 11:05:34

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));
    }

Cheers,
Jeremy

----------------------------------------------------------------------
 Jeremy Siek                          http://php.indiana.edu/~jsiek/
 Ph.D. Student, Indiana Univ. B'ton   email: jsiek_at_[hidden]
 C++ Booster (http://www.boost.org)   office phone: [phone]
----------------------------------------------------------------------