Thanks for the ideas Jeremiah. I'll upgrade to 1.52 and try it out.
On Thu, 15 Nov 2012, Brian Budge wrote:Does that mean that you are only adding dependencies, not removing them?
Hi all -
I am toying around with the file dependency example that is part of the boost graph documentation as a way of
adapting the concepts to my own use cases.
What I want to do is update the graph over time (add more files with more dependencies), and incrementally decide
what needs to be built, and in what order.
It depends on if you think a lot of the BFS levels will be changed by your updates. If you think they will be, just re-do the BFS from scratch. If not, you might want to keep a level map, then stop on any vertices whose level values don't change when running the BFS from the updated sources. What I think will work (not tested) is to:
It makes sense that doing a breadth-first search from a changed node will give me everything that might be affected;
however, if I change many nodes, is there something better?
1. Start with source vertices of newly added edges marked as white and in the list of start vertices (see below); color the other vertices black.
2. In examine_edge, if the target's level is larger than the source's level + 1, set the target's color to white.There are multi-source BFS versions in Boost.Graph now, although they are not documented; the version to use is:
I could imagine that I might mark nodes as they are
encountered so that other BFS from other changed nodes won't traverse those as well. With boost graph, how can I
control the BFS to stop recursion if a vertex has already been visited?
template <class VertexListGraph, class SourceIterator,
class Buffer, class BFSVisitor,
class ColorMap>
void breadth_first_search
(const VertexListGraph& g,
SourceIterator sources_begin, SourceIterator sources_end,
Buffer& Q, BFSVisitor vis, ColorMap color);An efficient incremental topological sort is apparently hard to do; BFS isn't as fast as a specialized algorithm for that, but should work.
I guess then once I have seen all the stale vertices, I can make a smaller graph that only has the stale vertices and their connections, and I can topologically sort the sub-graph to find the parallel build order?
-- Jeremiah Willcock
_______________________________________________
Boost-users mailing list
Boost-users@lists.boost.org
http://lists.boost.org/mailman/listinfo.cgi/boost-users