|
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