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

Subject: Re: [Boost-users] [graph] File Dependency Example with updates
From: Brian Budge (brian.budge_at_[hidden])
Date: 2012-11-20 17:36:09

On Fri, Nov 16, 2012 at 7:57 AM, Jeremiah Willcock <jewillco_at_[hidden]>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