[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 (tmatelich_at_[hidden])
Date: 2002-12-24 01:38:28

> From: Tom Matelich [mailto:tmatelich_at_[hidden]]
> > From: Tom Matelich [mailto:tmatelich_at_[hidden]]
> > From: David Abrahams [mailto:dave_at_[hidden]]
> > > Tom Matelich <tmatelich_at_[hidden]> writes:
> > > > From: David Abrahams [mailto:dave_at_[hidden]]
> > > >> Tom Matelich <tmatelich_at_[hidden]> 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.
-----------------------------------------------------------------------