Re: [Boost-users] [graph] File Dependency Example with updates

Subject: Re: [Boost-users] [graph] File Dependency Example with updates
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2012-11-16 10:57:44

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.

Does that mean that you are only adding dependencies, not removing them?

> 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