Re: Extended use of BGL File Dependency Example

From: David Abrahams (dave_at_[hidden])
Date: 2002-12-01 21:13:28

Tom Matelich <tmatelich_at_[hidden]> writes:

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

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_at_[hidden] * http://www.boost-consulting.com
Boost support, enhancements, training, and commercial distribution