[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

24 Dec 2002

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

Tom Matelich

tags

participants (3)