[boost] Re: graph_search

From: jsiek_at_[hidden]
Date: 2000-01-12 23:46:41

Dave Abrahams writes:
 > 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...

Actually, you lost me :)

 > > 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?

Here's the weighted_edge_visitor's process function:

  template <class Weight, class Distance, class Base, class BinOp,
    class Edge, class Graph, class Bag>
  bool process(weighted_edge_visitor<Weight,Distance,Base,BinOp>& vis, 
               Edge e, Graph& g, Bag& bag) {
    if (relax(e, g, vis.w, vis.d, vis.op)) {
      bag.push(target(e,g));
      bag.update(target(e,g));
      (void)process(static_cast<Base&>(vis), e, g, bag);
      return true
    } else
      return false;
  }

So the "inherited" process() was only getting called when a relax
happened. I think it was a mistake to do this. Instead:

  template <class Weight, class Distance, class Base, class BinOp,
    class Edge, class Graph, class Bag>
  bool process(weighted_edge_visitor<Weight,Distance,Base,BinOp>& vis, 
               Edge e, Graph& g, Bag& bag) {
    bool ret;
    if (relax(e, g, vis.w, vis.d, vis.op)) {
      bag.push(target(e,g));
      bag.update(target(e,g));
      ret = true
    } else
      ret = false;
    (void)process(static_cast<Base&>(vis), e, g, bag);
    return ret;
  }

But I just realized that there's a bug in the above code. The
push into the bag should only happen if the the vertex is not
already in it (so it acts like a set). After I fix this I think
everything should work :)

Cheers,

Jeremy