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

From: vladimir josef sykora (vladimir.sykora_at_[hidden])
Date: 2003-03-05 05:23:29

"Tarjei Knapstad" <tarjeik_at_[hidden]> wrote in message
news:1046817775.2517.58.camel_at_cc-intern01...
> 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
vladimir.sykora_at_[hidden]
http://www.morphochem.de