Re: Extended use of BGL File Dependency Example

From: David Abrahams (dave_at_[hidden])
Date: 2002-12-01 08:57:38

Tom Matelich <tmatelich_at_[hidden]> writes:

>> I was excited to get to use the graph library for a 
>> dependency tracking tool
>> we needed, now I have a feature that I don't know how to do.  This is
>> mapping library/executable dependencies and we have a lot of apps with
>> common sub-libraries.  I'd like to extract a full-rebuild 
>> order for only
>> certain nodes, i.e. what libs do I need to build for apps A 
>> and B?  Since
>> its a DAG, I thought something about reachability, perhaps?  
>> I'm not too
>> familiar with graph theory :(
>
> Okay, so I solved that one with using a "depends on" relationship rather
> than "used by", then used a breadth_first_search.
>
> Now I have a tougher question, maybe I'll get an answer this time :).  I'm
> 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

-Dave
-- 
                       David Abrahams
   dave_at_[hidden] * http://www.boost-consulting.com
Boost support, enhancements, training, and commercial distribution