[BGL] Simplest way to implement bool isReachable(Vertex src, Vert ex target, Graph g) was: [Boost-Users] Re: Extended use of BGL File Depen dency Example
From: Tom Matelich [mailto:tmatelich@zetec.com]
From: Tom Matelich [mailto:tmatelich@zetec.com] From: David Abrahams [mailto:dave@boost-consulting.com]
Tom Matelich <tmatelich@zetec.com> writes:
From: David Abrahams [mailto:dave@boost-consulting.com]
Tom Matelich <tmatelich@zetec.com> writes:
trying to make my graphviz representation look nicer and I was wondering if there is an algorithm already for simplifying:
-----B\ A--< \ --------C D----------/
to:
A---B---C D------/
This eliminated the A-C edge.
<snip discussion of minimum spanning tree. It won't work because I require all reachability to be maintained. > so here's my psuedo-algorithm: for each vertex V for each out-edge E for each out-edge E_prime (double loop) if(isReachable(target(E_prime), target(E)) remove_edge(E) In other words if one of V's children can reach the target vertex of a given edge, then that edge can be removed. If someone could let me know how to implement bool isReachable(Vertex src, Vertex target, Graph g); I would really appreciate it. Or if you have a better algorithm, I'd love to hear it. Thanks, Tom ----------------------------------------------------------------------- DISCLAIMER: Information contained in this message and/or attachment(s) may contain confidential information of Zetec, Inc. If you have received this transmission in error, please notify the sender by return email. -----------------------------------------------------------------------
participants (1)
-
Tom Matelich