Tarjei Knapstad wrote: > Yes, depth_first_visit goes through all the vertices in the connected > component which the starting vertex belong to, but depth_first_visit is > for directed graphs so I can't use it - it confuses tree and back edges > when used on undirected graphs. This is why undirected_dfs was made > which correctly handles tree and back edges by using an additional edge > color map.
Oops. I've paid not enough heed to 'undirected' word. BTW, I also don't know why undirected_dfs is completely separate algorithm... there's a lot in common. > On second thought undirected_dfs_visit is exactly what I've implemented > in my constrained_undirected_dfs, as colouring one vertex black > basically "fools" the DFS into believing that the graph consists of two > connected components. Just to clarify: are you talking about "undirected_depth_first_visit" function as found in <boost/graph/undirected_dfs.hpp>? >> >> > 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: >> >> > template <class Vertex, class Graph> >> > void start_vertex(Vertex u, const Graph& g) >> > { >> > if (apVertex) >> > { >> > (*apColorMap)[*apVertex] = Color::black(); >> > } >> > } >> >> Ehhm... how will this work? 'start_vertex' is called immediately >> before calling next depth_first_visit. That function, right in >> the start, colors the starting vertex in gray... >> > Yes, the starting vertex is colored gray. 'apVertex' above however is a > pointer to the vertex which is to be blocked, and this vertex is > adjacent to the starting vertex, so this works (maybe I should've called > it 'apBlockedVertex' or the like). Taking my example graph: Agh.. you color specific vertex in black when starting next dfs_visit. >> If I were to implement the same, I'd try using 'examine_edge' event: when >> edge leads to a blocked vertex, you color that vertex in black. >> > Yes, but this is a lot more work than the above. In my case the vertex I > want to block is allways adjacent to the starting vertex, so the > start_vertex approach works fine, but if you want something more general > where the vertex/vertices to be blocked are not adjacent to your > starting point then this would be a more proper solution of course. OK. And interesting questions is whether blocking some vertices should be supported in BGL. >> Another possibility is to eliminate blocked vertices from the graph, >> using 'subgraph' adapter, but I really don't know how good/efficient this >> idea is. >> > Richard Howells suggested this in Boost-Users as well, but the problem > is that 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. I don't think so. You can write a predicate which will say that specific vertex is not present in the filtered_graph (BTW, this is the right name, not 'subgraph' as I said before). Or you can exclude the edge from starting vertex to the blocked one. Changing color looks faster, in any case. - Volodya _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost