Re: [Boost-Users] [BGL] Preconditioned color maps?

On Tue, 2003-03-04 at 14:03, Alexandre Carsac wrote:

Why not, just erasing temporary the vertice (c,d) and applying DFS directly ?

Hi Alexandre, There are two reasons why I'd like to avoid this: 1 (minor): My graph has a lot of internal properties, so that would mean that some state saving had to be done. My graph class inherits an undirected adjacency list, so I could allways implement some "HideEdge/RestoreEdge" functionality that would temporarily remove a edge from the graph. 2 (major): This is a read-only operation, and the same graph _might_ also be accesed read-only in another thread. The remove edge solution would mean that I'd have to put a lock on it in this algorithm and lose performance. I could make a copy of the graph, but as it is potentially quite large this could possibly take longer than just doing a full DFS, and eliminate the unwanted results afterwards. I'll consider going with the remove-edge alternative, but I'll have to look a bit more into if I risk losing parallell efficiency.

Tarjei Knapstad wrote:In an algorithm I'm working on I need to do an undirected_dfs using a visitor for analysis. I know my starting vertex, and I also want the DFS to skip one of the starting vertex's adjacent vertices (i.e. don't proceed in the "direction" from the starting vertex). Example:

d-e-f / a-b-c \ g-h-i

Starting vertex is 'c' and I want to eliminate the "d-e-f" branch, so the DFS finds "c-b-a" and "c-g-h-i".

My first idea was to set up a vertex color map, and set the color to black for vertex 'd' in the example above, but that doesn't do much good as the undirected_dfs sets all colors to white initially.

My second thought was to feed the vertex I want to eliminate and the vertex color map to my dfs_visitor implementation, something like:

discover_vertex(u, g) { if (u == blocked) { vertex_colormap[u] = black; } }

Will the latter approach work satisfactory? If not, is there some other way which I can use to precondition the color maps used in the BGL algorithms?

Thanks, -- Tarjei