Graphserver

The open-source multi-modal trip planner.

Code Repository

http://github.com/graphserver/graphserver/tree/master

Mailing List

Direct questions and comments to the Graphserver Google Group.

Download

 $ wget http://github.com/graphserver/graphserver/tarball/14102010

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

 $ git clone git://github.com/graphserver/graphserver.git 

Install

Cold Start

You'll need a computer running linux. The following setup was tested and checked on Amazon EC2 small instance running Fedora, built from an image with id "ami-48aa4921", at a cost of $0.20/hour.

You'll need to get git:

On Ubuntu:

 $ sudo apt-get install git-core 

On Fedora:

 $ yum install git-core

Get The Prerequisites

You're about to compile C code against python development libraries. You need to prepare for that.

On Ubuntu:

$ sudo apt-get install python-setuptools
$ sudo apt-get install build-essential
$ sudo apt-get install python-dev

On Fedora:

$ yum install python-setuptools-devel
$ yum install gcc
$ yum install gcc-c++
$ easy_install simplejson

One-step Install

Get a copy of Graphserver

$ git clone git://github.com/graphserver/graphserver.git

This will download and compile the core, download and install package dependencies, and install the python wrappers in one go.

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

Install RTree

If you want to load OSM Data (and you probably do), you have to laboriously install RTree

 $ wget http://download.osgeo.org/libspatialindex/spatialindex-src-1.6.0.tar.gz
 $ gunzip spatialindex-1.6.0.tar.gz
 $ tar -xvf spatialindex-1.6.0.tar
 $ cd spatialindex-1.6.0
 $ ./configure --prefix=/usr
 $ make
 $ make install
 $ easy_install RTree

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
<Street name='2' length=50.000000 rise=0.000000 fall=0.000000 way=0> 
>>> 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()

Compiling Graphs

Loading OpenStreetMap Data

Grab some OSM data. Here, we download an area around of Redding, CA, US from the OpenStreetMap HTTP API.

 $ wget http://api.openstreetmap.org/api/0.6/map?bbox=-122.4624,40.5505,-122.2876,40.6334 -O redding.osm

Compile the OSM file into an OSMDB file, and then load that OSMDB file into a graph.

 $ gs_osmdb_compile redding.osm redding.osmdb
 $ gs_import_osm redding.gdb redding.osmdb

Take a look at your new graph. This prints every vertex label in the graph:

 $ gs_gdb_inspect redding.gdb

Pick one and see all edges outgoing from that vertex:

 $ gs_gdb_inspect redding.gdb osm-92080455

Prints:

osm-92080455 -> osm-91938757
	<Street name='10585937-1' length=136.119463 rise=0.000000 fall=0.000000 way=849>
osm-92080455 -> osm-92080457
	<Street name='10585937-2' length=139.452776 rise=0.000000 fall=0.000000 way=849>
osm-92080455 -> osm-92601143
	<Street name='10596654-0' length=126.551782 rise=0.000000 fall=0.000000 way=1809>
osm-92080455 -> osm-92080381
	<Street name='10596654-1' length=6.382770 rise=0.000000 fall=0.000000 way=1809>

Loading Public Transit Data

Grab the GTFS file for your favorite transit agency. Here, we grab the GTFS for the transit system in Redding, CA:

 $ wget http://trilliumtransit.com/transit_feeds/redding/google_transit.zip -O redding_gtfs.zip

Compile the GTFS into a GTFSDB, and then compile that GTFSDB into a graph

 $ gs_gtfsdb_build redding_gtfs.zip redding.gtfsdb
 $ gs_import_gtfs redding.gdb redding.gtfsdb

Use gs_gdb_inspect to check that your new transit graph is in good shape

 $ gs_gdb_inspect redding.gdb sta-3622

should print

sta-3622 -> psv-0-000-004-105A166 
	<TripBoard int_sid=0 sid=105A166 agency=0 calendar=165157760 timezone=164034504 boardings=[('1572A105B166', 23964), ('1598A105B166', 27564), ('1602A105B166', 31164), ('1607A105B166', 34764), ('1600A105B166', 38364), ('1605A105B166', 41964), ('1603A105B166', 45564), ('1608A105B166', 49164), ('1601A105B166', 52764), ('1606A105B166', 56364), ('1599A105B166', 59964), ('1604A105B166', 63564), ('1609A105B166', 67164)]>
sta-3622 -> psv-0-000-004-106A166 
	<TripBoard int_sid=1 sid=106A166 agency=0 calendar=165157760 timezone=164034504 boardings=[('2459A106B166', 34764), ('1635A106B166', 38364), ('1640A106B166', 41964), ('1638A106B166', 45564), ('1643A106B166', 49164), ('1636A106B166', 52764), ('1641A106B166', 56364), ('1634A106B166', 59964), ('1639A106B166', 63564), ('1637A106B166', 67164)]>

Intermingling Public Transit and Street Data

You can load both OSM and GTFS data into the same graph, then run a command to link them.

 $ gs_link_osm_gtfs redding.gdb redding.osmdb redding.gtfsdb

Inspect:

 $ gs_gdb_inspect redding.gdb sta-3622

prints:

sta-3622 -> osm-92366549
	<graphserver.core.Link object at 0x9a0b20c>
sta-3622 -> psv-0-000-004-105A166
	<TripBoard int_sid=0 sid=105A166 agency=0 calendar=163855912 timezone=161122808 boardings=[('1572A105B166', 23964), ('1598A105B166', 27564), ('1602A105B166', 31164), ('1607A105B166', 34764), ('1600A105B166', 38364), ('1605A105B166', 41964), ('1603A105B166', 45564), ('1608A105B166', 49164), ('1601A105B166', 52764), ('1606A105B166', 56364), ('1599A105B166', 59964), ('1604A105B166', 63564), ('1609A105B166', 67164)]>
sta-3622 -> psv-0-000-004-105A166
	<TripBoard int_sid=1 sid=106A166 agency=0 calendar=163855912 timezone=161122808 boardings=[('2459A106B166', 34764), ('1635A106B166', 38364), ('1640A106B166', 41964), ('1638A106B166', 45564), ('1643A106B166', 49164), ('1636A106B166', 52764), ('1641A106B166', 56364), ('1634A106B166', 59964), ('1639A106B166', 63564), ('1637A106B166', 67164)]>

Inspecting the graph with gs_crawl

Start gs_crawl, a little graph inspection web service

 $ gs_crawl redding.gdb 80

Then steer your web browser to the appropriate location.

If you're using Amazon EC2, using your own public DNS:

http://YOUR-EC2-ADDRESS.compute-1.amazonaws.com/

Or if you're simply running on your local machine:

http://localhost:80/

Look a list of all vertices

http://HOSTNAME/vertices

Check out the incoming and outgoing edges from a particlar vertex

http://HOSTNAME/vertex?label="sta-3594"

Getting routes with gs_routeserver

First, you'll need PyYAML

 $ sudo easy_install pyyaml

The routeserver finds a path, and then uses a series of handlers to convert that path into a human-readable format. Those handlers are enumerated and set up by a configuration file called handlers.yaml. Graphserver comes with an example handlers.yaml which you can use to get started

 $ cp /path/to/graphserver/pygs/graphserver/ext/routeserver/handlers.yaml .

This handlers.yaml file is filled with "CHANGEME" stubs. Replace every "CHANGEME.gtfsdb" with "redding.gtfsdb" and every "CHANGEME.osmdb" with "redding.osmdb"

Fire up a routeserver on the compiled graph

 $ gs_routeserver redding.gdb handlers.yaml -p 80

Get a list of all vertices in the system

http://YOUR_DOMAIN_NAME/vertices

Get a route narrative

http://YOUR_DOMAIN_NAME/path?origin="osm-92011649"&dest="sta-3803"&currtime=1260839444

or

http://YOUR_DOMAIN_NAME/path_raw?origin="osm-92011649"&dest="sta-3803"&currtime=1260839444

What about a really big city?

First, get Java 1.6. Or Java6. I think they're the same thing. Get the JDK, but not the JVM, the JRE, SDK, SDN, or the JCE. Note Java SE comes with Jave EE, which is apparently at version 5, and may or may not have anything to do with J2EE. I don't know what those have to do with anything. Google it or something. I don't know. They don't make it particularly easy for you. It's like, they've got more money than god and nothing pleases them better than pouring all that expertise into baffling the hell out of you. Honestly, I can't stand Java, but you need it to run Osmosis.

Then, get Osmosis

 $ wget http://gweb.bretth.com/osmosis-latest.zip
 $ unzip osmosis-latest.zip
 $ chmod a+x ./osmosis-0.30/bin/osmosis

Download a biggie GTFS file. Here's the one for the Seattle area:

 $ wget http://www.gtfs-data-exchange.com/gtfs/badhill_20091208_1910.zip

Compile it into a GTFSDB. This will take a few minutes

 $ gs_gtfsdb_build badhill_20091208_1910.zip kingco.gtfsdb

Check the bounds of the GTFSDB

 $ sqlite3 kingco.gtfsdb "select min(stop_lon),min(stop_lat),max(stop_lon),max(stop_lat) from stops"

returns:

-122.506729|47.1553345|-121.78244|47.9323654

This will come in handy soon.

Get a huge chunk of OSM data from the CloudMade state files. Here's Washington State:

 $ wget http://downloads.cloudmade.com/north_america/united_states/washington/washington.osm.highway.bz2
 $ bunzip2 washington.osm.highway.bz2

Then, use the bounding box coordinates we just got to cut down the OSM file to the area surrounding the agency. Check it:

 $ /path/to/osmosis-0.30/bin/osmosis --read-xml washington.osm.highway --bounding-box left=-122.506729 bottom=47.1553345 right=-121.78244 top=47.9323654 --write-xml kingco.osm

Then, compile and set it up like normal. It's a trip-planning bonanza.