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

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2002-08-06 13:01:19

On Tue, 6 Aug 2002, Erik Arner wrote:
yg-boo>
yg-boo> OK thanks, I now realize I formulated the question wrongly. What I
yg-boo> really was looking for is a fast method for determining whether two
yg-boo> vertices have common *descendants*, not necessarily children... I might
yg-boo> have to perform this task many times during the run of the program, so
yg-boo> it really needs to be fast. Any thoughts?

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

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]
----------------------------------------------------------------------