Re: (from: [Boost-Users]) [BGL] Preconditioned color maps?

From: Tarjei Knapstad (tarjeik_at_[hidden])
Date: 2003-03-05 08:08:11

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