[boost] Re: graph_search

From: jsiek_at_[hidden]
Date: 2000-01-12 22:22:35

Dave Abrahams writes:
 > > But such a search algorithm will only hit the *reachable* nodes of the
 > > graph from the starting vertex, so it would not be appropriate for
 > > copying some graphs...
 > 
 > Sure. My graphs are connected lattices.
 > 
 > > In any case, I'm working on it :)
 > 
 > Great!

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);
}

...

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". This means some edges will not get copied, as in the
following example. Note that the outgoing edges of f did not get
copied.

  Starting graph:
  a(32767): c d 
  c(32767): f 
  d(32767): e f 
  f(32767): e g 
  e(32767): b g 
  g(32767): 
  b(32767): 
  
  Result:
  a(0): c d 
  c(3): f 
  d(4): e f 
  f(9): 
  e(4): b g 
  b(14): 
  g(7): 

I'll see if there is a way around this...

Cheers,

Jeremy