Re: [Boost-users] BGL python: dijkstra_shortest_paths

From: John Reid (j.reid_at_[hidden])
Date: 2007-04-23 05:22:41

ping

This looks like a bug in the BGL python bindings.

John.

John Reid wrote:
> 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.