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

Subject: [Boost-users] [graph] File Dependency Example with updates
From: Brian Budge (brian.budge_at_[hidden])
Date: 2012-11-15 18:51:34

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?  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?

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?

Sorry, I'm a bit out of practice with my graph algorithms in general, and
I'm very new to the boost graph library, so I hope I haven't said anything
dumb :)  Any design suggestions welcome.

Thanks,
  Brian