[BGL] Preconditioned color maps?
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
Why not, just erasing temporary the vertice (c,d) and applying DFS directly ? Tarjei Knapstad <tarjeik@chemcon.no> 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 --------------------------------- Do You Yahoo!? -- Une adresse @yahoo.fr gratuite et en français ! Testez le nouveau Yahoo! Mail [Non-text portions of this message have been removed]
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 <tarjeik@chemcon.no> 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
----- Original Message ----- From: Tarjei Knapstad <tarjeik@chemcon.no> To: Boost-users <Boost-Users@yahoogroups.com> Sent: Monday, 03 March, 2003 5:51 PM Subject: [Boost-Users] [BGL] Preconditioned color maps?
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.
Doesn't it invoke dfs_visitor::initialize_vertex(u,g) on every vertex before the start of the search?
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; } }
If so, you could do something similar in there? Although I can't find in the documentation that it's invoked after the colours have been set (but it is if you look in depth_first_search.hpp). Failing that, dfs_visitor::start_vertex(s,g) is invoked on the source vertex once before the start of the search, so you could look for 'd' in there. Hmm, it doesn't say that dfs_visitor::start_vertex(s,g) is called after the colours have been set (at least I can't find it in the docs), but it doesn't seem sensible to do it the other way round. Louis.
On Tue, 2003-03-04 at 21:44, Louis Lavery wrote: [I'm cross posting this to the main list as it contains some discussion wrt. BGL in general as well] I've got it sorted now after having another look at the BGL code, and having made my own version of undirected_dfs...
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.
Doesn't it invoke dfs_visitor::initialize_vertex(u,g) on every vertex before the start of the search?
Yes.
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; } }
If so, you could do something similar in there?
Although I can't find in the documentation that it's invoked after the colours have been set (but it is if you look in depth_first_search.hpp).
Failing that, dfs_visitor::start_vertex(s,g) is invoked on the source vertex once before the start of the search, so you could look for 'd' in there.
Hmm, it doesn't say that dfs_visitor::start_vertex(s,g) is called after the colours have been set (at least I can't find it in the docs), but it doesn't seem sensible to do it the other way round.
Yes, the colours are set before any of the vistor events are invoked and this is now part of my solution after first having overlooked start_vertex (initialize_vertex is called first on all vertices, then start_vertex, and then the DFS proceeds with discover_vertex etc.) My visitor now has two constructors, one for non-restrictive operation which just takes an output iterator where I store the wanted results, and one which also takes a reference to a vertex descriptor and the vector containing the vertex colors. I've got pointers in the visitor to both a vertex descriptor and a vector of vertex colours which are initialized to NULL in the first, non-restrictive version so that I can block 'd' if wanted. To outline (a bit pseudo-codish again): template <class OutputIterator, class GraphType> class my_recorder : public boost::default_dfs_visitor { public: my_recorder(OutputIterator out) : aOut(out), apVertex(NULL), apColorMap(NULL) {} my_recorder(OutputIterator out, vertex_descriptor& v, ColorMap& v_colors) : aOut(out), apVertex(&v), apColorMap(&v_colors) {} template <class Vertex, class Graph> void start_vertex(Vertex u, const Graph& g) { if (apVertex) { (*apColorMap)[*apVertex] = Color::black(); } } private: OutputIterator aOut; vertex_descriptor* apVertex; ColorMap* apColorMap; }; The second problem however is a property of the DFS algorithm where a starting vertex is given that I had overlooked. After the DFS has discovered all the vertices reachable from the starting vertex, it will continue using any yet undiscovered (white) vertices and use those as starting vertices for another search. That means that if I block 'd' in my example graph, undirected_dfs will first do the job I intend it to starting from 'c', but will then select either 'e' or 'f' as a next starting vertice and do a DFS from there until all vertices have been discovered. And that was exactly what I was trying to avoid :) This leaves two choices: 1. Color _all_ the vertices I don't want to visit black, i.e. 'e' and 'f' as well in the example. This alone requires almost as much analysis as I want to do in the first place. 2. Make a "constrained" DFS that will disregard any undiscovered vertices after all has been discovered from the starting vertex. This is an easy and efficient solution. I've implemented an algorithm called constrained_undirected_dfs which is a carbon copy of the undirected_dfs algorithm, except that the last loop which goes through any whites left has been removed. I don't know if it's a thing to consider incorporating into BGL (it could also be accomplished by just adding a boolean flag to the DFS algos of course), or if I'm just going about things the wrong way here. Does this sort of restricted DFS make any sense as a general purpose tool? If you have large graphs and for instance want to do DFS/BFS on just a small branch of it, this seems to be impractical the way things are. A possibility (as have recently been discussed IIRC) is to break off the DFS by throwing an exception the second time start_vertex is invoked in the visitor. I'm not too fond of that solution though, allthough I must admit that my visitor implementation above is not exactly "a beaut"... Any opinions/views? Regards, -- Tarjei Knapstad
----- Original Message ----- From: Tarjei Knapstad <tarjeik@chemcon.no> To: Boost-users <Boost-Users@yahoogroups.com>; Boost-dev <boost@lists.boost.org> Sent: Tuesday, 04 March, 2003 10:42 PM Subject: (from: [Boost-Users]) [BGL] Preconditioned color maps? [snip]
A possibility (as have recently been discussed IIRC) is to break off the DFS by throwing an exception the second time start_vertex is invoked in the visitor. I'm not too fond of that solution though, allthough I must admit that my visitor implementation above is not exactly "a beaut"...
A less drastic alternative is to, on the second call, just set all vertex colours to black. But I agree with you that a one_shot_depth_first_search that starts from a given vertex and then gets out is called for. In fact I find it difficult to understand why anyone would want to start at a given vertex, do a dfs from there and then go on to start another dfs from any unvisited vertices. Perhaps I lack imagination - anyone got an example of its use? Louis.
On Wed, 2003-03-05 at 08:50, Louis Lavery wrote:
[snip]
A possibility (as have recently been discussed IIRC) is to break off the DFS by throwing an exception the second time start_vertex is invoked in the visitor. I'm not too fond of that solution though, allthough I must admit that my visitor implementation above is not exactly "a beaut"...
A less drastic alternative is to, on the second call, just set all vertex colours to black.
Less drastic yes, but (possibly severly) inefficient in large graphs. In undirected_dfs, after the starting vertex has been DFS visited, the algorithm checks all vertices to see if there are any white left in the graph, so the "colour all black" approach involves first setting say 100,000 vertex colors to black, and then checking the same 100,000 vertex colors to see if any are white.
But I agree with you that a one_shot_depth_first_search that starts from a given vertex and then gets out is called for.
Yes, like I said to Vladimir today, my "constrained_undirected_dfs" is really nothing more than "undirected_dfs_visit". If I could have used depth_first_visit I would be in the clear as it only discovers the vertices which belong to the same connected component as the starting vertex. Pre-colouring a vertex black effectively divides a fully connected graph into two connected components (with the exception that both components actually share the black vertex, but that becomes unimportant).
In fact I find it difficult to understand why anyone would want to start at a given vertex, do a dfs from there and then go on to start another dfs from any unvisited vertices. Perhaps I lack imagination - anyone got an example of its use?
I'm not too heavily into graph theory and all it's applications either, but there's probably scenarios where you've got several connected components and need to start off with one of them based on some criterion/-a. Regards, -- Tarjei
Hi Tarjei, I can't claim to be really familiar with the graphs so this suggestion may be a non starter. ISTR that there is an adaptor/filter/view of some kind that you can place on top of your base graph to allow just a subset of vertices to be available. Could you apply your DFS to the filtered view? If so would that be the standard solution? Best - Richard ----- Original Message ----- From: "Tarjei Knapstad" <tarjeik@chemcon.no> To: "Boost-users" <Boost-Users@yahoogroups.com>; "Boost-dev" <boost@lists.boost.org> Sent: Tuesday, March 04, 2003 10:42 PM Subject: (from: [Boost-Users]) [BGL] Preconditioned color maps?
On Tue, 2003-03-04 at 21:44, Louis Lavery wrote:
[I'm cross posting this to the main list as it contains some discussion wrt. BGL in general as well]
I've got it sorted now after having another look at the BGL code, and having made my own version of undirected_dfs...
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.
Doesn't it invoke dfs_visitor::initialize_vertex(u,g) on every vertex before the start of the search?
Yes.
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; } }
If so, you could do something similar in there?
Although I can't find in the documentation that it's invoked after the colours have been set (but it is if you look in depth_first_search.hpp).
Failing that, dfs_visitor::start_vertex(s,g) is invoked on the source vertex once before the start of the search, so you could look for 'd' in there.
Hmm, it doesn't say that dfs_visitor::start_vertex(s,g) is called after the colours have been set (at least I can't find it in the docs), but it doesn't seem sensible to do it the other way round.
Yes, the colours are set before any of the vistor events are invoked and this is now part of my solution after first having overlooked start_vertex (initialize_vertex is called first on all vertices, then start_vertex, and then the DFS proceeds with discover_vertex etc.)
My visitor now has two constructors, one for non-restrictive operation which just takes an output iterator where I store the wanted results, and one which also takes a reference to a vertex descriptor and the vector containing the vertex colors. I've got pointers in the visitor to both a vertex descriptor and a vector of vertex colours which are initialized to NULL in the first, non-restrictive version so that I can block 'd' if wanted. To outline (a bit pseudo-codish again):
template <class OutputIterator, class GraphType> class my_recorder : public boost::default_dfs_visitor { public: my_recorder(OutputIterator out) : aOut(out), apVertex(NULL), apColorMap(NULL) {}
my_recorder(OutputIterator out, vertex_descriptor& v, ColorMap& v_colors) : aOut(out), apVertex(&v), apColorMap(&v_colors) {}
template <class Vertex, class Graph> void start_vertex(Vertex u, const Graph& g) { if (apVertex) { (*apColorMap)[*apVertex] = Color::black(); } }
private: OutputIterator aOut; vertex_descriptor* apVertex; ColorMap* apColorMap; };
The second problem however is a property of the DFS algorithm where a starting vertex is given that I had overlooked. After the DFS has discovered all the vertices reachable from the starting vertex, it will continue using any yet undiscovered (white) vertices and use those as starting vertices for another search. That means that if I block 'd' in my example graph, undirected_dfs will first do the job I intend it to starting from 'c', but will then select either 'e' or 'f' as a next starting vertice and do a DFS from there until all vertices have been discovered. And that was exactly what I was trying to avoid :)
This leaves two choices: 1. Color _all_ the vertices I don't want to visit black, i.e. 'e' and 'f' as well in the example. This alone requires almost as much analysis as I want to do in the first place.
2. Make a "constrained" DFS that will disregard any undiscovered vertices after all has been discovered from the starting vertex. This is an easy and efficient solution. I've implemented an algorithm called constrained_undirected_dfs which is a carbon copy of the undirected_dfs algorithm, except that the last loop which goes through any whites left has been removed.
I don't know if it's a thing to consider incorporating into BGL (it could also be accomplished by just adding a boolean flag to the DFS algos of course), or if I'm just going about things the wrong way here.
Does this sort of restricted DFS make any sense as a general purpose tool? If you have large graphs and for instance want to do DFS/BFS on just a small branch of it, this seems to be impractical the way things are.
A possibility (as have recently been discussed IIRC) is to break off the DFS by throwing an exception the second time start_vertex is invoked in the visitor. I'm not too fond of that solution though, allthough I must admit that my visitor implementation above is not exactly "a beaut"...
Any opinions/views?
Regards, -- Tarjei Knapstad
Info: <http://www.boost.org> Wiki: <http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl> Unsubscribe: <mailto:boost-users-unsubscribe@yahoogroups.com>
Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
On Wed, 2003-03-05 at 09:20, Richard Howells wrote:
Hi Tarjei,
I can't claim to be really familiar with the graphs so this suggestion may be a non starter. ISTR that there is an adaptor/filter/view of some kind that you can place on top of your base graph to allow just a subset of vertices to be available. Could you apply your DFS to the filtered view? If so would that be the standard solution?
There is one major problem with the subgraph adaptor: to create a subgraph you need to specify all the vertices from the original graph, and the adapator then recreates the edges as they are found in the original graph. Those vertices are exactly what I'm trying to discover through my "blocked DFS" though, so the adapter solution leaves me at square one so to speak as I would still need my "constrained" DFS to create the subgraph adapter. <snip> Regards, -- Tarjei
----- Original Message ----- From: Tarjei Knapstad <tarjeik@chemcon.no> To: Boost-users <Boost-Users@yahoogroups.com> Sent: Wednesday, 05 March, 2003 9:39 AM Subject: Re: (from: [Boost-Users]) [BGL] Preconditioned color maps?
On Wed, 2003-03-05 at 09:20, Richard Howells wrote:
Hi Tarjei,
I can't claim to be really familiar with the graphs so this suggestion may be a non starter. ISTR that there is an adaptor/filter/view of some kind that you can place on top of your base graph to allow just a subset of vertices to be available. Could you apply your DFS to the filtered view? If so would that be the standard solution?
There is one major problem with the subgraph adaptor: to create a subgraph you need to specify all the vertices from the original graph, and the adapator then recreates the edges as they are found in the original graph. Those vertices are exactly what I'm trying to discover through my "blocked DFS" though, so the adapter solution leaves me at square one so to speak as I would still need my "constrained" DFS to create the subgraph adapter.
Not sure, but you seem to be saying you want to form a filtered view with d and its subgraph effectively removed? If so, then starting from... d-e-f / a-b-c w-x-y \ g-h-i ...use connected_components() and the labels it creates to create a filtered view of the component containing vertex c... d-e-f / a-b-c \ g-h-i ...now filer the above to remove edge (c,d)... d-e-f a-b-c \ g-h-i ...finally, use connected_components() and the labels it creates to create a filtered view of the component containing vertex c... a-b-c \ g-h-i Is that any use? Louis.
On Wed, 2003-03-05 at 13:41, Louis Lavery wrote: <snip>
On Wed, 2003-03-05 at 09:20, Richard Howells wrote:
Hi Tarjei,
I can't claim to be really familiar with the graphs so this suggestion may be a non starter. ISTR that there is an adaptor/filter/view of some kind that you can place on top of your base graph to allow just a subset of vertices to be available. Could you apply your DFS to the filtered view? If so would that be the standard solution?
There is one major problem with the subgraph adaptor: to create a subgraph you need to specify all the vertices from the original graph, and the adapator then recreates the edges as they are found in the original graph. Those vertices are exactly what I'm trying to discover through my "blocked DFS" though, so the adapter solution leaves me at square one so to speak as I would still need my "constrained" DFS to create the subgraph adapter.
Not sure, but you seem to be saying you want to form a filtered view with d and its subgraph effectively removed?
Yes that is the case. Some kind people over at the main boost list pointed me to the undocumented undirected_depth_first_visit algorithm which does exactly what I need in a more efficient way than filtered_graph. It does not perform the "color all white" step initially, so I can just set up my colormaps whichever way I want and thus very efficiently eliminate the connected component where I want the DFS to roam.
If so, then starting from...
d-e-f / a-b-c w-x-y \ g-h-i
...use connected_components() and the labels it creates to create a filtered view of the component containing vertex c...
d-e-f / a-b-c \ g-h-i
...now filer the above to remove edge (c,d)...
d-e-f
a-b-c \ g-h-i
...finally, use connected_components() and the labels it creates to create a filtered view of the component containing vertex c...
a-b-c \ g-h-i
Is that any use?
It could have been, but like I said the undirected DFS visit algorithm is a lot quicker. (Also I could skip you first step as I am certain that my graph is fully connected.) You did teach me about filtered_graph though, which is good and will probably come to use later :) Thanks for your help, -- Tarjei
participants (4)
-
Alexandre Carsac -
Louis Lavery -
Richard Howells -
Tarjei Knapstad