[Boost-users] BGL python: dijkstra_shortest_paths

From: John Reid (j.reid_at_[hidden])
Date: 2007-04-13 12:09:03

Hi,

I can't seem to use dijkstra_shortest_paths as I think I should via the 
python bindings. It works fine when I pass a weight_map and 
predecessor_map. What I want to do is to pass a predecessor_map and a 
distance_map. Unfortunately boost.python can't convert the arguments.

I'm using a bgl that says bgl.__version__ = '1.0' although I haven't 
updated it from SVN recently.

This works:
import boost.graph as bgl
graph = bgl.Graph()
a = graph.add_vertex()
b = graph.add_vertex()
e = graph.add_edge(a, b)
weights = graph.add_edge_property('integer')
weights[e] = 5
predecessors = graph.add_vertex_property('vertex')
bgl.dijkstra_shortest_paths(
         graph,
         a,
         predecessor_map = predecessors,
         weight_map = weights
)

This doesn't work:
import boost.graph as bgl
graph = bgl.Graph()
a = graph.add_vertex()
b = graph.add_vertex()
e = graph.add_edge(a, b)
distances = graph.add_edge_property('float')
predecessors = graph.add_vertex_property('vertex')
bgl.dijkstra_shortest_paths(
         graph,
         a,
         predecessor_map = predecessors,
         distance_map = distances
)

This is the error I get:
<class 'Boost.Python.ArgumentError'>: Python argument types in
     boost.graph._graph.dijkstra_shortest_paths(Graph, Vertex)
did not match C++ signature:
     dijkstra_shortest_paths(class 
boost::graph::python::basic_graph<struct boost
::bidirectionalS> graph, struct 
boost::graph::python::basic_descriptor<void *,st
ruct boost::bidirectionalS> root_vertex, class 
boost::vector_property_map<struct
  boost::graph::python::basic_descriptor<void *,struct 
boost::bidirectionalS>,str
uct boost::graph::python::basic_index_map<struct 
boost::graph::python::basic_des
criptor<void *,struct boost::bidirectionalS>,struct 
boost::adj_list_vertex_prope
rty_map<class boost::adjacency_list<struct boost::listS,struct 
boost::listS,stru
ct boost::bidirectionalS,struct boost::property<enum 
boost::vertex_index_t,unsig
ned int,struct boost::no_property>,struct boost::property<enum 
boost::edge_index
_t,unsigned int,struct boost::no_property>,struct 
boost::no_property,struct boos
t::listS>,unsigned int,unsigned int const &,enum boost::vertex_index_t> 
 > > * pr
edecessor_map=None, class boost::vector_property_map<float,struct 
boost::graph::
python::basic_index_map<struct 
boost::graph::python::basic_descriptor<void *,str
uct boost::bidirectionalS>,struct 
boost::adj_list_vertex_property_map<class boos
t::adjacency_list<struct boost::listS,struct boost::listS,struct 
boost::bidirect
ionalS,struct boost::property<enum boost::vertex_index_t,unsigned 
int,struct boo
st::no_property>,struct boost::property<enum 
boost::edge_index_t,unsigned int,st
ruct boost::no_property>,struct boost::no_property,struct 
boost::listS>,unsigned
  int,unsigned int const &,enum boost::vertex_index_t> > > * 
distance_map=None, c
lass boost::vector_property_map<float,struct 
boost::graph::python::basic_index_m
ap<struct boost::graph::python::basic_descriptor<class 
boost::detail::edge_desc_
impl<struct boost::bidirectional_tag,void *>,struct 
boost::bidirectionalS>,struc
t boost::adj_list_edge_property_map<struct 
boost::bidirectional_tag,unsigned int
,unsigned int const &,void *,struct boost::property<enum 
boost::edge_index_t,uns
igned int,struct boost::no_property> const ,enum boost::edge_index_t> > 
 > {lvalu
e} weight_map, class boost::python::api::object visitor=None, class 
boost::vecto
r_property_map<enum boost::default_color_type,struct 
boost::graph::python::basic
_index_map<struct boost::graph::python::basic_descriptor<void *,struct 
boost::bi
directionalS>,struct boost::adj_list_vertex_property_map<class 
boost::adjacency_
list<struct boost::listS,struct boost::listS,struct 
boost::bidirectionalS,struct
  boost::property<enum boost::vertex_index_t,unsigned int,struct 
boost::no_proper
ty>,struct boost::property<enum boost::edge_index_t,unsigned int,struct 
boost::n
o_property>,struct boost::no_property,struct boost::listS>,unsigned 
int,unsigned
  int const &,enum boost::vertex_index_t> > > * color_map=None)
     dijkstra_shortest_paths(class 
boost::graph::python::basic_graph<struct boost
::undirectedS> graph, struct boost::graph::python::basic_descriptor<void 
*,struc
t boost::undirectedS> root_vertex, class 
boost::vector_property_map<struct boost
::graph::python::basic_descriptor<void *,struct 
boost::undirectedS>,struct boost
::graph::python::basic_index_map<struct 
boost::graph::python::basic_descriptor<v
oid *,struct boost::undirectedS>,struct 
boost::adj_list_vertex_property_map<clas
s boost::adjacency_list<struct boost::listS,struct boost::listS,struct 
boost::un
directedS,struct boost::property<enum boost::vertex_index_t,unsigned 
int,struct
boost::no_property>,struct boost::property<enum 
boost::edge_index_t,unsigned int
,struct boost::no_property>,struct boost::no_property,struct 
boost::listS>,unsig
ned int,unsigned int const &,enum boost::vertex_index_t> > > * 
predecessor_map=N
one, class boost::vector_property_map<float,struct 
boost::graph::python::basic_i
ndex_map<struct boost::graph::python::basic_descriptor<void *,struct 
boost::undi
rectedS>,struct boost::adj_list_vertex_property_map<class 
boost::adjacency_list<
struct boost::listS,struct boost::listS,struct boost::undirectedS,struct 
boost::
property<enum boost::vertex_index_t,unsigned int,struct 
boost::no_property>,stru
ct boost::property<enum boost::edge_index_t,unsigned int,struct 
boost::no_proper
ty>,struct boost::no_property,struct boost::listS>,unsigned int,unsigned 
int con
st &,enum boost::vertex_index_t> > > * distance_map=None, class 
boost::vector_pr
operty_map<float,struct boost::graph::python::basic_index_map<struct 
boost::grap
h::python::basic_descriptor<class boost::detail::edge_desc_impl<struct 
boost::un
directed_tag,void *>,struct boost::undirectedS>,struct 
boost::adj_list_edge_prop
erty_map<struct boost::undirected_tag,unsigned int,unsigned int const 
&,void *,s
truct boost::property<enum boost::edge_index_t,unsigned int,struct 
boost::no_pro
perty> const ,enum boost::edge_index_t> > > {lvalue} weight_map, class 
boost::py
thon::api::object visitor=None, class boost::vector_property_map<enum 
boost::def
ault_color_type,struct boost::graph::python::basic_index_map<struct 
boost::graph
::python::basic_descriptor<void *,struct boost::undirectedS>,struct 
boost::adj_l
ist_vertex_property_map<class boost::adjacency_list<struct 
boost::listS,struct b
oost::listS,struct boost::undirectedS,struct boost::property<enum 
boost::vertex_
index_t,unsigned int,struct boost::no_property>,struct 
boost::property<enum boos
t::edge_index_t,unsigned int,struct boost::no_property>,struct 
boost::no_propert
y,struct boost::listS>,unsigned int,unsigned int const &,enum 
boost::vertex_inde
x_t> > > * color_map=None)

For reference here is the docstring bgl gives me:
Type:           function
Base Class:     <type 'builtin_function_or_method'>
String Form:    <Boost.Python.function object at 0x04AEE940>
Namespace:      Interactive
Docstring:
     dijkstra_shortest_paths(graph, root_vertex, predecessor_map = None,
                         distance_map = None, weight_map = None,
                         visitor = None)

Computes the shortest paths from the root vertex to every other vertex
in a graph.

Parameters:
   graph            the graph on which to compute shortest paths will
                    run. It may be either a directed or undirected graph.

   root_vertex      the starting vertex for the shortest-path search.

   predecessor_map  a vertex -> vertex map that stores the predecessor of
                    each vertex in the shortest paths tree. From a given
                    vertex, one can follow the predecessor_map back to
                    the root_vertex to reconstruct the shortest path.

   distance_map     a vertex -> float map that stores the distance from
                    the root_vertex to each vertex in the tree. A
                    distance of infinity in this property map indicates
                    that the vertex is unreachable from the root_vertex.

   weight_map       an edge -> float map that stores the weight of each
                    edge in the graph. Negative edge weights are not
                    permitted. If no weight map is provided, each edge
                    will be assumed to have a weight of 1.0.

   visitor          a visitor that will receive events as the
                    shortest-paths computation progresses. Typically this
                    visitor should be derived from
                    boost.graph.dijkstra_visitor.

See also:
   bellman_ford_shortest_paths
   dag_shortest_paths
   dijkstra_visitor

Complete C++ documentation is available at:
   http://www.boost.org/libs/graph/doc/dijkstra_shortest_paths.html

Any help appreciated,
John.