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

From: David Abrahams [mailto:dave@boost-consulting.com] Sent: Sunday, December 01, 2002 5:58 AM

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