Boost logo

Boost :

From: Joel Young (jdy_at_[hidden])
Date: 2002-10-30 23:13:09


I am trying to implement a shortest paths algorithm on
a directed graph.

As I have unit edge weights, I would rather use breadth_first_search
rather than dijkstra.

// Is this a good candidate for addition?
template <class Map, class Tag>
struct vertex_marker
  : public boost::base_visitor<vertex_marker<Map,Tag> >
{
  typedef Tag event_filter;
  vertex_marker(Map p_map,int p_val) : m_map(p_map),m_val(p_val) { }
  template <class Vertex, class Graph>
  void operator()(Vertex v,const Graph&) {
    boost::put(m_map,v,m_val);
  }
  Map m_map;
  int m_val;
};

template <class Map, class Tag>
vertex_marker<Map,Tag>
mark_vertices(Map p_map, Tag, int p_v) {
  return vertex_marker<Map,Tag>(p_map,p_v);
}

boost::breadth_first_search(
  mygraph,
  rootnode,
  boost::visitor(boost::make_bfs_visitor(
    std::make_pair(
      boost::record_distances(
        boost::get(boost::vertex_distance,mygraph),
        boost::on_tree_edge())
      ,
      std::make_pair(
        mark_vertices(
          boost::get(boost::vertex_distance,mygraph),
          boost::on_initialize_vertex(),
          std::numeric_limits<int>::max())
        ,
        mark_vertices(
          boost::get(boost::vertex_distance,mygraph),
          boost::on_start_vertex(),
          0)
      )
    )
  ))
);

The problem is that on_start_vertex does not seem to be implemented
for breadth_first_search, but it is for depth_first. For dijkstra,
the start node seems to be automaticly zeroed. I guess I could mod

Am I missing something really obvious here or is there an inconsistency
across the algorithms?

Shouldn't on_start_vertex be used for all of the graph algorithms?

Also, I can't seem to find documentation on neighbor_bfs.hpp

Thanks,

Joel


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk