Graphserver

The open-source multi-modal trip planner.

Download

$ svn co http://graphserver.svn.sourceforge.net/svnroot/graphserver/tags/072808 graphserver

Or, for the stout of heart, get a copy of the current working branch

$ svn co http://graphserver.svn.sourceforge.net/svnroot/graphserver/trunk graphserver

Install

Install core libraries

$ cd graphserver
$ cd core
$ make
$ sudo make install
$ cd ..

Install Python wrappers

Install dependencies

$ easy_install transitfeed
$ easy_install pyproj
$ easy_install pytz

Install wrappers

$ cd pygs
$ sudo python setup.py install
$ cd ..

There are also a set of Ruby wrappers

$ cd rbgs
$ ruby extconf.rb
$ make

There is presently no installer for the ruby wrappers

Using Graphserver via Python Wrappers

A Quick Tour of the Basics

$ python
>>> from graphserver.core import Graph, Street, State
>>> gg = Graph()
>>> gg.add_vertex("A")
<graphserver.core.Vertex object at 0xb7d9608c>
>>> gg.add_vertex("B")
<graphserver.core.Vertex object at 0xb7c397cc>
>>> gg.add_edge( "A", "B", Street("1", 100) )
<graphserver.core.Edge object at 0xb7c4a92c>
>>> gg.add_edge( "A", "B", Street("2", 50 ) )
<graphserver.core.Edge object at 0xb7da708c>
>>> gg.size   #the graph is quite small
2
>>> gg.get_vertex("A").outgoing                      # the graph is directional
[<graphserver.core.Edge object at 0xb7b9accc>, <graphserver.core.Edge object at 0xb7b9acac>]
>>> gg.get_vertex("A").incoming
[]
>>> spt = gg.shortest_path_tree( "A", "B", State(1,0) )
>>> spt
<graphserver.core.ShortestPathTree object at 0xb7c45b8c>
>>> spt.get_vertex("A")                              # the shortest path tree is a partial copy of the graph
<graphserver.core.Vertex object at 0xb7c4a92c>
>>> spt.get_vertex("A").outgoing                     # which only contains the shortest paths to all points closer than 'B' 
[<graphserver.core.Edge object at 0xb7b9adec>]
>>> vertices, edges = spt.path("B")                  # you can get the path 'A' to 'B' from the shortest path tree
>>> vertices                                         # a list of references to the SPT vertices along the shortest path
[<graphserver.core.Vertex object at 0xb7b9ae4c>, <graphserver.core.Vertex object at 0xb7b9adec>]
>>> edges                                            # a list of references to the SPT edges along the shortest path
[<graphserver.core.Edge object at 0xb7b9accc>]
>>> edges[0].payload                                 # the edge payload contains information about the edge
<graphserver.core.Street object at 0xb7b9ad8c>
>>> edges[0].payload.name                            # apparently, Street "2" is the shortest path between "A" and "B"
'2'
>>> vertices[-1].payload                             # the payload of the final vertex has useful information
<graphserver.core.State object at 0xb7c4a92c>
>>> vertices[-1].payload.time                        # it takes 58 seconds to get from "A" to "B"
58
>>> spt.destroy()                                    # these functions are thin wrappers around C functions
>>> gg.destroy()                                     # so we have to perform garbage collection explicitly
>>> exit()

Loading OpenStreetMap Data

$ cd /path/to/graphserver/pygs/examples/osm
$ python
>>> from graphserver.ext.osm import OSM
>>> osm = OSM("sf.osm")
>>> len(osm.nodes)
39406
>>> from graphserver.core import Graph, State
>>> from graphserver.ext.osm import OSMLoadable
>>> from pyproj import Proj
>>> class OSMGraph(Graph, OSMLoadable):               # add the load_osm() function to the graph with a mixin
...   pass
... 
>>> gg = OSMGraph()
>>> gg.load_osm(osm, Proj(init='epsg:26910'))         # specify projection to convert OSM data to meters
>>> gg.size
39406
>>> fortmason = "osm65298435"                         # a location near Fort Mason in San Francisco, California
>>> hollypark = "osm65297473"                         # a location near Holly Park in San Francisco
>>> spt=gg.shortest_path_tree(fortmason,hollypark,State(1,0)) # this took about 0.05 seconds
>>> vertices, edges = spt.path(hollypark)
>>> len(vertices), len(edges)                         # the shortet path has 96 edge segments
(97, 96)
>>> edges[0].payload.name                             # the first of which has this id
'8920043-48'
>>> vertices[-1].payload.time                         # it takes a little over two and a half hours to walk that far
9192
>>> spt.destroy()                                     # remember to explicitly clean up
>>> gg.destroy()
>>> quit()

Converting the raw IDs returned by Graphserver into a human-readable message is left as an exercise to the reader.

Loading Public Transit Data

Graphserver has built-in edge types to handle scheduled public transit. Public transit data is loaded into the graph via Google Transit Feed Specification (GTFS) files. Several transit agencies publicly release schedule data in the GTFS format.

$ mkdir bart
$ cd bart
$ wget http://www.bart.gov/schedules/developers/latest_open.aspx
$ unzip google_transit.zip
$ cd ..
$ python
>>> from graphserver.core import Graph, Link, State
>>> from graphserver.ext.gtfs import GTFSLoadable
>>> class GTFSGraph(Graph, GTFSLoadable):
...   pass
...
>>> gg = GTFSGraph()
>>> gg.load_gtfs( './bart' )
>>> [v.label for v in gg.vertices]
['gtfsROCK', 'gtfsBALB', 'gtfsDELN', 'gtfsSANL', 'gtfsPLZA', 'gtfsLAFY', 'gtfs16TH', 'gtfsCAST', 'gtfs
24TH', 'gtfs12TH', 'gtfsNBRK', 'gtfsDUBL', 'gtfsDALY', 'gtfsMCAR', 'gtfsORIN', 'gtfsFRMT', 'gtfsSHAY',
'gtfsDBRK', 'gtfsSFIA', 'gtfsCONC', 'gtfsMONT', 'gtfsNCON', 'gtfsASBY', 'gtfsPHIL', 'gtfsBAYF', 'gtfsP
ITT', 'gtfsOAK', 'gtfsLAKE', 'gtfsHAYW', 'gtfsRICH', 'gtfsMLBR', 'gtfsUCTY', 'gtfsSBRN', 'gtfs12TH_N',
'gtfsGLEN', 'gtfsMCAR_S', 'gtfsSSAN', 'gtfsWOAK', 'gtfsCIVC', 'gtfs19TH', 'gtfsFTVL', 'gtfsWCRK', 'gtf
sCOLM', 'gtfsPOWL', 'gtfsCOLS', 'gtfsEMBR']
>>> gg.add_edge("gtfs12TH", "gtfs12TH_N", Link())            # explicitly link adjacent stations
<graphserver.core.Edge object at 0x85dee6c>
>>> gg.add_edge("gtfs12TH_N", "gtfs12TH", Link())
<graphserver.core.Edge object at 0x85dedcc>
>>> gg.add_edge("gtfsMCAR", "gtfsMCAR_S", Link())
<graphserver.core.Edge object at 0x85ded0c>
>>> gg.add_edge("gtfsMCAR_S", "gtfsMCAR", Link())
<graphserver.core.Edge object at 0x85dee6c>
>>> twothirtysix = 1217367385                                # unix time for about 2:36PM July 29, 2008 UTC-0700
>>> spt = gg.shortest_path_tree( "gtfsCIVC", "gtfsPITT", State(1,twothirtysix)) # civic center to pittsburg starting at 2:36PM on a weekday
>>> spt.get_vertex("gtfsCIVC").outgoing
[<graphserver.core.Edge object at 0x85decac>, <graphserver.core.Edge object at 0x85de1ec>]
>>> spt.get_vertex("gtfsPITT").incoming
[<graphserver.core.Edge object at 0x85de1cc>]
>>> vertices, edges = spt.path("gtfsPITT")
>>> [v.label for v in vertices]                              # take a look at all vertex labels on the shortest path
['gtfsCIVC', 'gtfsPOWL', 'gtfsMONT', 'gtfsEMBR', 'gtfsWOAK', 'gtfs12TH', 'gtfs19TH', 'gtfsMCAR', 'gtfsR
OCK', 'gtfsORIN', 'gtfsLAFY', 'gtfsWCRK', 'gtfsPHIL', 'gtfsCONC', 'gtfsNCON', 'gtfsPITT']
>>> [e.payload.arrive for e in edges]                        # take a look at the departure of each hop on the shortest path
[52980, 53100, 53220, 53640, 54120, 54180, 54420, 54900, 55200, 55500, 55740, 55920, 56220, 56460, 56820]
>>> spt.destroy()
>>> gg.destroy()
>>> quit()

Intermingling Public Transit and Street Data

Unlike the above working examples, this is more of an illustrative outline.

$ python
>>> from graphserver.core import Graph, Like, State
>>> from graphserver.ext.osm import OSMLoadable
>>> from graphserver.ext.gtfs import GTFSLoadable
>>> class MultimodalGraph(Graph, OSMLoadable, GTFSLoadable):
...   pass
...
>>> gg = MultimodalGraph()
>>> gg.load_osm( "./path/to/osm.osm" )
>>> gg.load_gtfs( "./path/to/gtfsdir" )
>>> gg.add_edge( "aBusStopLabel", "aStreetIntersectionLabel", Link() ) # explicitly link transit vertices to nearby street vertices
>>> gg.add_egge( "aStreetIntersectionLabel, "aBusStopLabel", Link() )
>>> spt = gg.shortest_path_tree( "someStreetLabel", "otherStreetLabel", State(1, unixtime) )
>>> vertices, edges = spt.path( "otherStreetLabel" )
>>> # Convert vertices, edges into human-readable format
>>> spt.destroy()
>>> gg.destroy()