On Fri, Nov 16, 2012 at 7:57 AM, Jeremiah Willcock
<jewillco@osl.iu.edu> wrote:
On Thu, 15 Nov 2012, Brian Budge wrote:
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 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?
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:
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.
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?
There are multi-source BFS versions in Boost.Graph now, although they are not documented; the version to use is:
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);
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?
An efficient incremental topological sort is apparently hard to do; BFS isn't as fast as a specialized algorithm for that, but should work.
-- Jeremiah Willcock
_______________________________________________
Boost-users mailing list
Boost-users@lists.boost.org
http://lists.boost.org/mailman/listinfo.cgi/boost-users