"Tarjei Knapstad" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED] > On Tue, 2003-03-04 at 21:44, Louis Lavery wrote:
[snip] > > > 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". AFAICS, 'd' is not an adjacent vertex of 'c'. > > > > > > 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. > > > There's the _visit_ version of the algorithm, where this task is left to the user. So you could color your graph as you like, and then call that version. > > > > 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 > > _______________________________________________ > Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost > -- vladimir josef sykora morphochem AG gmunder str. 37-37a 81379 muenchen tel. ++49-89-78005-0 fax ++49-89-78005-555 [EMAIL PROTECTED] http://www.morphochem.de _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost