On Fri, Nov 16, 2012 at 7:57 AM, Jeremiah Willcock <jewillco@osl.iu.edu> wrote:
Hopefully I am far enough along to ask some reasonable questions now.  
 
Does that mean that you are only adding dependencies, not removing them?


I may rarely remove, rarely enough that I can do something less efficient in those case.
 
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:

I'm not 100% sure I understand about the level map.  I can see that if I just mark all vertices white, and then mark black as vertices are completed, common subpaths will not be traversed when BFSing from multiple vertices.  What is the level map, and how is it computed?  Are the levels similar to the dependency levels given by a topological sort?
 
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.

How are the levels initialized in the first place?  And once I had performed the multi-source BFS, would these levels correspond to dependency levels given by the topo sort?
 

 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.

What I was thinking I would do (since I don't quite grok the level map idea) was to use the multi-source BFS to simply grab out the nodes that need to be operated on (with the edges that exist between those nodes, haven't considered yet how to do this).  Once I had that list, I was thinking that I could build a smaller graph and topo sort that graph.

However, it seems that I would need a re-mapping table from vertices in one graph to vertices in the other, which might be a pain.

I much prefer the idea of your solution, assuming that the levels correspond to independent sets, but I don't quite get all the details.  

Thanks for your help,
  Brian