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