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-17 12:40:47

Thanks for the ideas Jeremiah.  I'll upgrade to 1.52 and try it out.

  Brian

On Fri, Nov 16, 2012 at 7:57 AM, Jeremiah Willcock <jewillco_at_[hidden]>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.
>>
>
> 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
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>