Tom Matelich
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@boost-consulting.com * http://www.boost-consulting.com Boost support, enhancements, training, and commercial distribution