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/