Interpolate stop times for non timing point stops
[bus.git] / origin-src / graphserver.html









































































































































































































































1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
<html> 
  <head> 
    <link rel="stylesheet" href="main.css" type="text/css"> 
    <title>Graphserver - The Open-Source Multi-Modal Trip Planner</title> 
  </head> 
 
<body> 
<div id='container'> 
<a href="gallery.html"><img src="img/graphbanner.png"></a> 
<h1>Graphserver</h1> 
The open-source multi-modal trip planner.
 
<h2>Code Repository</h2> 
<a href="http://github.com/bmander/graphserver/tree/master">http://github.com/bmander/graphserver/tree/master</a> 
 
<h2>Mailing List</h2> 
 
Direct questions and comments to the <a href="http://groups.google.com/group/graphserver">Graphserver Google Group</a>.
 
<h2>Download</h2> 
 
<pre style="background-color:#F5F5F5"> $ wget http://github.com/bmander/graphserver/zipball/08132009</pre> 
 
Or, for the stout of heart, get a copy of the current working branch
 
<pre style="background-color:#F5F5F5"> $ git clone git://github.com/bmander/graphserver.git </pre>
 
<h2>Install</h2>
 
<h3>Cold Start</h3>
<p>You'll need a computer running linux. The following setup was tested and checked on <a href="http://aws.amazon.com/console/">Amazon EC2</a> small instance running Fedora, built from an image with id "ami-48aa4921", at a cost of $0.20/hour.<p>
<p>You'll need to get git:</p>
<p>On Ubuntu:</p>
<pre style="background-color:#F5F5F5"> $ sudo apt-get install git-core </pre>
<p>On Fedora:</p>
<pre style="background-color:#F5F5F5"> $ yum install git-core</pre>
 
<h3>Get The Prerequisites</h3>
 
<p>You're about to compile C code against python development libraries. You need to prepare for that.</p>
 
On Ubuntu:
<pre style="background-color:#F5F5F5">$ sudo apt-get install python-setuptools
$ sudo apt-get install build-essential
$ sudo apt-get install python-dev
</pre>
 
On Fedora:
<pre style="background-color:#F5F5F5">
$ yum install python-setuptools-devel
$ yum install gcc
$ yum install gcc-c++
$ yum install python-devel
$ easy_install simplejson
</pre>
 
<h3>One-step Install</h3>
<p>Get a copy of Graphserver</p>
<pre style="background-color:#F5F5F5">$ git clone git://github.com/bmander/graphserver.git</pre> 
 
This will download and compile the core, download and install package dependencies, and install the python wrappers in one go.
 
<pre style="background-color:#F5F5F5">$ cd graphserver/pygs
$ sudo python setup.py install
</pre> 
 
<h3>Install RTree</h3>
<p>If you want to load OSM Data (and you probably do), you have to laboriously install RTree</p>
<pre style="background-color:#F5F5F5"> $ wget http://download.osgeo.org/libspatialindex/spatialindex-1.4.0.tar.gz
 $ gunzip spatialindex-1.4.0.tar.gz
 $ tar -xvf spatialindex-1.4.0.tar
 $ cd spatialindex-1.4.0
 $ ./configure --prefix=/usr
 $ make
 $ make install
 $ easy_install RTree
 $ cp /usr/lib/python2.5/site-packages/Rtree-0.5.0-py2.5-linux-i686.egg/libsidx.so /usr/lib
</pre>
 
<h2>A Quick Tour of the Basics</h2> 
 
<pre style="background-color:#F5F5F5"> 
$ python
&gt;&gt;&gt; from graphserver.core import Graph, Street, State
&gt;&gt;&gt; gg = Graph()
&gt;&gt;&gt; gg.add_vertex("A")
<span class="computeroutput">&lt;graphserver.core.Vertex object at 0xb7d9608c&gt;</span> 
&gt;&gt;&gt; gg.add_vertex("B")
<span class="computeroutput">&lt;graphserver.core.Vertex object at 0xb7c397cc&gt;</span> 
&gt;&gt;&gt; gg.add_edge( "A", "B", Street("1", 100) )
<span class="computeroutput">&lt;graphserver.core.Edge object at 0xb7c4a92c&gt;</span> 
&gt;&gt;&gt; gg.add_edge( "A", "B", Street("2", 50 ) )
<span class="computeroutput">&lt;graphserver.core.Edge object at 0xb7da708c&gt;</span> 
&gt;&gt;&gt; gg.size   #the graph is quite small
<span class="computeroutput">2</span> 
&gt;&gt;&gt; gg.get_vertex("A").outgoing                      <span class="pycomment"># the graph is directional</span> 
<span class="computeroutput">[&lt;graphserver.core.Edge object at 0xb7b9accc&gt;, &lt;graphserver.core.Edge object at 0xb7b9acac&gt;]</span> 
&gt;&gt;&gt; gg.get_vertex("A").incoming
<span class="computeroutput">[]</span> 
&gt;&gt;&gt; spt = gg.shortest_path_tree( "A", "B", State(1,0) )
&gt;&gt;&gt; spt
<span class="computeroutput">&lt;graphserver.core.ShortestPathTree object at 0xb7c45b8c&gt;</span> 
&gt;&gt;&gt; spt.get_vertex("A")                              <span class="pycomment"># the shortest path tree is a partial copy of the graph</span> 
<span class="computeroutput">&lt;graphserver.core.Vertex object at 0xb7c4a92c&gt;</span> 
&gt;&gt;&gt; spt.get_vertex("A").outgoing                     <span class="pycomment"># which only contains the shortest paths to all points closer than 'B' </span> 
<span class="computeroutput">[&lt;graphserver.core.Edge object at 0xb7b9adec&gt;]</span> 
&gt;&gt;&gt; vertices, edges = spt.path("B")                  <span class="pycomment"># you can get the path 'A' to 'B' from the shortest path tree</span> 
&gt;&gt;&gt; vertices                                         <span class="pycomment"># a list of references to the SPT vertices along the shortest path</span> 
<span class="computeroutput">[&lt;graphserver.core.Vertex object at 0xb7b9ae4c&gt;, &lt;graphserver.core.Vertex object at 0xb7b9adec&gt;]</span> 
&gt;&gt;&gt; edges                                            <span class="pycomment"># a list of references to the SPT edges along the shortest path</span> 
<span class="computeroutput">[&lt;graphserver.core.Edge object at 0xb7b9accc&gt;]</span> 
&gt;&gt;&gt; edges[0].payload                                 <span class="pycomment"># the edge payload contains information about the edge</span>
<span class="computeroutput">&lt;Street name='2' length=50.000000 rise=0.000000 fall=0.000000 way=0&gt;</span> 
&gt;&gt;&gt; vertices[-1].payload                             <span class="pycomment"># the payload of the final vertex has useful information</span> 
<span class="computeroutput">&lt;graphserver.core.State object at 0xb7c4a92c&gt;</span> 
&gt;&gt;&gt; vertices[-1].payload.time                        <span class="pycomment"># it takes 58 seconds to get from "A" to "B"</span> 
<span class="computeroutput">58</span> 
&gt;&gt;&gt; spt.destroy()                                    <span class="pycomment"># these functions are thin wrappers around C functions</span> 
&gt;&gt;&gt; gg.destroy()                                     <span class="pycomment"># so we have to perform garbage collection explicitly</span> 
&gt;&gt;&gt; exit()
</pre>
<h2>Compiling Graphs</h2>
<h3>Loading OpenStreetMap Data</h3>
 
Grab some OSM data. Here, we download an area around of Redding, CA, US from the OpenStreetMap HTTP API.
<pre style="background-color:#F5F5F5"> $ wget http://api.openstreetmap.org/api/0.6/map?bbox=-122.4624,40.5505,-122.2876,40.6334 -O map.osm
</pre>
<p>Compile the OSM file into an OSMDB file, and then load that OSMDB file into a graph.</p>
<pre style="background-color:#F5F5F5"> $ gs_osmdb_compile map.osm map.osmdb
 $ gs_import_osm map.gdb map.osmdb
</pre>
<p>Take a look at your new graph. This prints every vertex label in the graph:</p>
<pre style="background-color:#F5F5F5"> $ gs_gdb_inspect map.gdb</pre>
<p>Pick one and see all edges outgoing from that vertex:</p>
<pre style="background-color:#F5F5F5"> $ gs_gdb_inspect map.gdb osm-92080455</pre>
Prints:
<pre style="background-color:#F5F5F5">osm-92080455 -> osm-91938757
        &lt;Street name='10585937-1' length=136.119463 rise=0.000000 fall=0.000000 way=849&gt;
osm-92080455 -> osm-92080457
        &lt;Street name='10585937-2' length=139.452776 rise=0.000000 fall=0.000000 way=849&gt;
osm-92080455 -> osm-92601143
        &lt;Street name='10596654-0' length=126.551782 rise=0.000000 fall=0.000000 way=1809&gt;
osm-92080455 -> osm-92080381
        &lt;Street name='10596654-1' length=6.382770 rise=0.000000 fall=0.000000 way=1809&gt;</pre>
 
<h3>Loading Public Transit Data</h3> 
 
Grab the GTFS file for your favorite transit agency. Here, we grab the GTFS for the transit system in Redding, CA:
<pre style="background-color:#F5F5F5"> $ wget http://trilliumtransit.com/transit_feeds/redding/google_transit.zip -O redding_gtfs.zip</pre>
<p>Compile the GTFS into a GTFSDB, and then compile that GTFSDB into a graph<p>
<pre style="background-color:#F5F5F5"> $ gs_gtfsdb_build redding_gtfs.zip redding.gtfsdb
 $ gs_import_gtfs redding.gdb redding.gtfsdb</pre>
<p>Use gs_gdb_inspect to check that your new transit graph is in good shape</p>
<pre style="background-color:#F5F5F5"> $ gs_gdb_inspect redding.gdb sta-3622</pre>
should print
<pre style="background-color:#F5F5F5">sta-3622 -> psv-0-000-004
        &lt;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)]&gt;
sta-3622 -> psv-0-000-004
        &lt;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)]&gt;
</pre>
 
<h3>Intermingling Public Transit and Street Data</h3> 
<p>You can load both OSM and GTFS data into the same graph, then run a command to link them.</p>
<pre style="background-color:#F5F5F5"> $ gs_import_gtfs redding_all.gdb redding.gtfsdb
 $ gs_import_osm redding_all.gdb map.osmdb
 $ gs_link_osm_gtfs redding_all.gdb map.osmdb redding.gtfsdb</pre>
<p>Inspect:</p>
<pre style="background-color:#F5F5F5"> $ gs_gdb_inspect redding.gdb sta-3622</pre>
<p>prints:</p>
<pre style="background-color:#F5F5F5">sta-3622 -> osm-92366549
        &lt;graphserver.core.Link object at 0x9a0b20c&gt;
sta-3622 -> psv-0-000-004
        &lt;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)]&gt;
sta-3622 -> psv-0-000-004
        &lt;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)]&gt;</pre>
 
<h3>Inspecting the graph with gs_crawl</h3>
<p>Start gs_crawl, a little graph inspection web service</p>
<pre style="background-color:#F5F5F5"> $ gs_crawl redding.gdb 80</pre>
<p>Then steer your web browser to the appropriate location.<p>
<p>If you're using Amazon EC2, using your own public DNS:</p>
<pre style="background-color:#F5F5F5">http://YOUR-EC2-ADDRESS.compute-1.amazonaws.com/</pre>
<p>Or if you're simply running on your local machine:</p>
<pre style="background-color:#F5F5F5">http://localhost:80/</pre>
 
<h3 id="routeserver">Getting routes with gs_routeserver</h3>
<p>First, you'll need PyYAML</p>
<pre style="background-color:#F5F5F5"> $ sudo easy_install pyyaml</pre>
<p>The routeserver finds a path, and then uses a series of "handlers" to convert that path into a human-readable format. Those handlers are enumearted and set up by a configuration file called handlers.yaml. Graphserver comes with an example handlers.yaml which you can use to get started</p>
<pre style="background-color:#F5F5F5"> $ cp /path/to/graphserver/pygs/graphserver/ext/routeserver/handlers.yaml .</pre>
<p>This handlers.yaml file is filled with "CHANGEME" stubs. Replace every "CHANGEME.gtfsdb" with "redding.gtfsdb" and every "CHANGEME.osmdb" with "redding.osmdb"</p>
<p>Fire up a routeserver on the compiled graph</p>
<pre style="background-color:#F5F5F5"> $ gs_routeserver redding.gdb handlers.yaml -p 80</pre>
<p>Get a list of all vertices in the system</p>
<pre style="background-color:#F5F5F5">http://YOUR_DOMAIN_NAME/vertices</pre>
<p>Get a route narrative</p>
<pre style="background-color:#F5F5F5">http://YOUR_DOMAIN_NAME/path?origin="osm-92011649"&amp;dest="sta-3803"&amp;currtime=1260839444</pre>
<p>or</p>
<pre style="background-color:#F5F5F5">http://YOUR_DOMAIN_NAME/path_raw?origin="osm-92011649"&amp;dest="sta-3803"&amp;currtime=1260839444</pre>
 
<h3>What about a really big city?</h3>
<p>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.</p>
<p>Then, get Osmosis</p>
<pre style="background-color:#F5F5F5"> $ wget http://gweb.bretth.com/osmosis-latest.zip
 $ unzip osmosis-latest.zip
 $ chmod a+x ./osmosis-0.30/bin/osmosis</pre>
<p>Download a biggie GTFS file. Here's the one for the Seattle area:</p>
<pre style="background-color:#F5F5F5"> $ wget http://www.gtfs-data-exchange.com/gtfs/badhill_20091208_1910.zip</pre>
<p>Compile it into a GTFSDB. This will take a few minutes</p>
<pre style="background-color:#F5F5F5"> $ gs_gtfsdb_build badhill_20091208_1910.zip kingco.gtfsdb</pre>
<p>Check the bounds of the GTFSDB</p>
<pre style="background-color:#F5F5F5"> $ sqlite3 kingco.gtfsdb "select min(stop_lon),min(stop_lat),max(stop_lon),max(stop_lat) from stops"</pre>
returns:
<pre style="background-color:#F5F5F5">-122.506729|47.1553345|-121.78244|47.9323654</pre>
This will come in handy soon.
<p>Get a huge chunk of OSM data from the CloudMade state files. Here's Washington State:</p>
<pre style="background-color:#F5F5F5"> $ wget http://downloads.cloudmade.com/north_america/united_states/washington/washington.osm.highway.bz2
 $ bunzip2 washington.osm.highway.bz2</pre>
<