|
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 >>> from graphserver.core import Graph, Street, State >>> gg = Graph() >>> gg.add_vertex("A") <span class="computeroutput"><graphserver.core.Vertex object at 0xb7d9608c></span> >>> gg.add_vertex("B") <span class="computeroutput"><graphserver.core.Vertex object at 0xb7c397cc></span> >>> gg.add_edge( "A", "B", Street("1", 100) ) <span class="computeroutput"><graphserver.core.Edge object at 0xb7c4a92c></span> >>> gg.add_edge( "A", "B", Street("2", 50 ) ) <span class="computeroutput"><graphserver.core.Edge object at 0xb7da708c></span> >>> gg.size #the graph is quite small <span class="computeroutput">2</span> >>> gg.get_vertex("A").outgoing <span class="pycomment"># the graph is directional</span> <span class="computeroutput">[<graphserver.core.Edge object at 0xb7b9accc>, <graphserver.core.Edge object at 0xb7b9acac>]</span> >>> gg.get_vertex("A").incoming <span class="computeroutput">[]</span> >>> spt = gg.shortest_path_tree( "A", "B", State(1,0) ) >>> spt <span class="computeroutput"><graphserver.core.ShortestPathTree object at 0xb7c45b8c></span> >>> spt.get_vertex("A") <span class="pycomment"># the shortest path tree is a partial copy of the graph</span> <span class="computeroutput"><graphserver.core.Vertex object at 0xb7c4a92c></span> >>> spt.get_vertex("A").outgoing <span class="pycomment"># which only contains the shortest paths to all points closer than 'B' </span> <span class="computeroutput">[<graphserver.core.Edge object at 0xb7b9adec>]</span> >>> vertices, edges = spt.path("B") <span class="pycomment"># you can get the path 'A' to 'B' from the shortest path tree</span> >>> vertices <span class="pycomment"># a list of references to the SPT vertices along the shortest path</span> <span class="computeroutput">[<graphserver.core.Vertex object at 0xb7b9ae4c>, <graphserver.core.Vertex object at 0xb7b9adec>]</span> >>> edges <span class="pycomment"># a list of references to the SPT edges along the shortest path</span> <span class="computeroutput">[<graphserver.core.Edge object at 0xb7b9accc>]</span> >>> edges[0].payload <span class="pycomment"># the edge payload contains information about the edge</span> <span class="computeroutput"><Street name='2' length=50.000000 rise=0.000000 fall=0.000000 way=0></span> >>> vertices[-1].payload <span class="pycomment"># the payload of the final vertex has useful information</span> <span class="computeroutput"><graphserver.core.State object at 0xb7c4a92c></span> >>> vertices[-1].payload.time <span class="pycomment"># it takes 58 seconds to get from "A" to "B"</span> <span class="computeroutput">58</span> >>> spt.destroy() <span class="pycomment"># these functions are thin wrappers around C functions</span> >>> gg.destroy() <span class="pycomment"># so we have to perform garbage collection explicitly</span> >>> 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 <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></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 <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 <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)]> </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 <graphserver.core.Link object at 0x9a0b20c> sta-3622 -> psv-0-000-004 <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 <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)]></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"&dest="sta-3803"&currtime=1260839444</pre> <p>or</p> <pre style="background-color:#F5F5F5">http://YOUR_DOMAIN_NAME/path_raw?origin="osm-92011649"&dest="sta-3803"&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> < |