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

From: Tarjei Knapstad (tarjeik_at_[hidden])
Date: 2003-03-04 17:42:55

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