RE: [Boost-Users] Re: Extended use of BGL File Dependency Example

From: Tom Matelich (tmatelich_at_[hidden])
Date: 2002-12-01 17:39:21

From: David Abrahams [mailto:dave_at_[hidden]]
Sent: Sunday, December 01, 2002 5:58 AM
> 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
> >
> > to:
> >
> > A---B---C
> >
> > of course this is happening on a much larger scale.
> >
> > Thanks for any input you might have,
> 
> That's known as a "topological sort", and can be done easily with a
> depth-first search. I believe the graph library already has one:
> 
>    http://www.boost.org/libs/graph/doc/topological_sort.html
> 

Hmm, its a little more complicated (I think).  I'm using the topological
sort for determining a build order.  Now, I basically want to find a way to
eliminate as many Edges as possible while still showing all dependencies.

    -----B\
A--<       \
    --------C
D----------/

to:

A---B---C
D------/

This eliminated the A-C edge.

Thanks for considering my problem.  

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