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@osl.iu.edu C++ Booster (http://www.boost.org) office phone: (812) 855-3608 ----------------------------------------------------------------------