Re: [Boost-users] dijkstra_shortest_paths and Python

From: Hugo Ferreira (bytter_at_[hidden])
Date: 2006-11-30 13:52:27

Hi,

I couldn't find the add_vertex_property method. But, I found my way
nonetheless... Here's the code for future reference:

import boost

class PathFind:
    def __init__(self):
        self.graph = boost.Graph()
        self.weights = self.graph.edge_property_map('float')
        self.vertexesid = self.graph.vertex_property_map('integer')
        self.vertexes = {}

    def __addvertex__(self, id):
        if not self.vertexes.has_key(id):
            v = self.graph.add_vertex()
            self.vertexes[id] = v
            self.vertexesid[v] = id
            return v

        return self.vertexes[id]

    def addEdge(self, srcVertex, dstVertex, cost):
        src = self.__addvertex__(srcVertex)
        dst = self.__addvertex__(dstVertex)

        edge = self.graph.add_edge(src, dst)
        self.weights[edge] = cost

    def findPath(self, src, dst):
        p = self.graph.vertex_property_map('vertex')
        boost.dijkstra_shortest_paths(self.graph, self.vertexes[src],
                                      predecessor_map = p,
                                      weight_map = self.weights)

        path = [dst]
        while src != dst:
            dst = self.vertexesid[p[self.vertexes[dst]]]
            path.append(dst)
        path.reverse()

        return path

a = PathFind()
a.addEdge(1, 2, 5)
a.addEdge(2, 3, 3)
a.addEdge(2, 4, 4)
a.addEdge(3, 4, 0.5)

print a.findPath(1, 4)

Cheers!

Hugo Ferreira

On 11/30/06, John Reid <j.reid_at_[hidden]> wrote:
> Hi,
>
> This works for me:
>
> 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
> )
>
> Hope that helps,
> John.
>
>
>
> Hugo Ferreira wrote:
> > HI there,
> >
> > I'm trying to use the BGL bindings for python found here:
> > http://www.osl.iu.edu/~dgregor/bgl-python/
> >
> > The problem is that I can't seem to understand how the
> > dijkstra_shortest_paths() and the corresponding graph works. My code,
> > so far, is like this:
> >
> > ---8<---8<---
> >
> > import boost as bgl
> >
> > graph = bgl.Graph()
> > a = graph.add_vertex()
> > b = graph.add_vertex()
> > e = graph.add_edge(a, b)
> >
> > weights = graph.edge_property_map('integer')
> > weights[e] = 5
> > graph.edge_properties['weight'] = weights
> >
> > boost.dijkstra_shortest_paths(graph, a)
> >
> > ---8<---8<---
> >
> > Which, of course, complains about the dijkstra_shortest_paths function
> > signature. Can anyone please provide me an working example of setting
> > up a graph and calling this function? I basically need the shortest
> > path from vertex A to vertex B.
> >
> > Thanks in advance,
> >
> > Hugo Ferreira
> >
>
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>

-- 
GPG Fingerprint: B0D7 1249 447D F5BB 22C5  5B9B 078C 2615 504B 7B85