[boost] Re: graph_search

From: Dave Abrahams (abrahams_at_[hidden])
Date: 2000-01-12 23:33:06

> A first cut came pretty close with only a few lines of code:
> 
> template <class NewGraph, class Base = null_visitor>
> struct copy_visitor : public Base {
>   copy_visitor(NewGraph& graph) : g(graph) { }
>   copy_visitor(NewGraph& graph, const Base& b) : g(graph), Base(b) { }
>   NewGraph& g;
> };
> template <class NewGraph>
> copy_visitor<NewGraph> visit_copying(NewGraph& g) {
>   return copy_visitor<NewGraph>(g);
> }
> template <class NewGraph, class Base, class Edge, class Graph, class Bag>
> bool process(copy_visitor<NewGraph,Base>& vis, Edge e, Graph& g, Bag& b)
> {
>   add_edge(vis.g, source(e,g), target(e,g));
>   return process(static_cast<Base&>(vis), e, g, b);
> }

Sorry, I don't see how this can work. I don't see anything that will add new
items to the bag (process<null_visitor> doesn't do anything)... Aha, I see
it now. Hmm... I have an idea how visitor composition can maybe work better,
using containment instead of inheritance. The advantage would be that the
creator of new visitors wouldn't have to remember to call special functions
for the base class (and no static_cast<>!). I'm sure you can see this,
too...

> ...
>
> dijkstra_shortest_paths(G, int(a), distance.begin(), weight_on_edge_tag(),
>                         visit_copying(G_copy));
>
>
> There's only one small problem with this, the process() function only
> gets called right now for edges to vertices that need to be
> "relaxed".

Gee, I don't see why that would fail. It looks like every node for which an
incoming edge gets put in the bag has all its outgoing edges processed. What
am I missing?

-Dave