Tom Matelich <tmatelich@zetec.com> writes:

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

...

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

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.

Maybe you want a minimum spanning tree, where the weight of each edge in the tree is determined by the distance between its vertices in some topological sort? That seems to solve the cases shown above pretty nicely. -- David Abrahams dave@boost-consulting.com * http://www.boost-consulting.com Boost support, enhancements, training, and commercial distribution