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
|
=== About ===
libroutez is a library written to help plan trips. Currently, its focus is
on providing directions for using public transit, but it could be easily
extended to cover other things (e.g. cycle-path planning). Specifically,
it provides an interface to solving the following problems:
- Finding the closest point in a road/transportation network to a specific
latitude-longitude pair.
- Finding the shortest path between two points in a road/transportation
network.
The design of libroutez is based on the following principles:
- Focus on solving user and developer problems, not data structures or
algorithms. For example, though libroutez uses the astar algorithm internally,
we try to expose the interface to that through a simple method called
"find_path".
- Be extensible, but only in response to demonstrative developer need.
- Be fast. libroutez uses an internal graph representation that, after being
generated, can be loaded very quickly on program startup. Trips on a modest
sized transit network can be generated in a fraction of a second on modern
hardware (and there are plans to speed things up further).
- Minimize memory use. Obviously the scale of public transit systems will
incur some overhead here, but we want to be maximally useful on embedded
systems and virtual servers where such resources may be scarce.
- Minimize dependancies. For example, we don't assume the user wants to use a
PostGRES database to store trip planning data (though they can if the want to).
libroutez itself has no run-time dependancies beyond the C++ standard library.
The libroutez has utility functions for converting Google Transit Feed
(http://code.google.com/p/googletransitdatafeed) and OpenStreetMap
(http://openstreetmap.org) data into its own format. It should be very easy
to add a simple converter for your preferred data type.
=== Setup and use ===
These instructions assume you are on a UNIX-based system (e.g. Linux or
MacOS X).
1. Download and install the following packages:
- Boost
- Probably any recent version should do. We need shared_ptr, unordered_set,
and unordered_map (unordered_map.hpp is included in debian/ubuntu packages
libboost1.37-dev & libboost1.38-dev)
- Google Transit Data Feed (http://code.google.com/p/googletransitdatafeed/)
- As of this writing you need what's in SVN, as it has a fix that I made
to actually handle interpolated stops correctly. The next version after
1.1.9 should have my fix.
- SWIG
- A recentish version is desirable. I used 1.3.36.
Helpful hint: To install a python package in a local prefix, do:
"python setup.py install --home=$HOME --prefix=" when inside the package
You may need to set PYTHONPATH to $HOME/lib/python first.
2. Build the C++ graph module and the bindings.
The usual...
- ./autogen.sh && ./configure && make
For an install into your home directory, try running ./configure like so:
- ./configure --prefix=$HOME --libdir=$HOME/lib
or maybe:
- ./configure --prefix=$HOME --libdir=$HOME/lib64 # (for many 64-bit systems)
3. Set up your language environment.
You can either 'make install' to install the binding source to the library
directory you chose with './configure', or set your library and ruby/python
path to the libroutez source directory of your choice. e.g.:
export LD_LIBRARY_PATH=/path/to/libroutez and
export PYTHONPATH=/path/to/libroutez/python
export RUBYLIB=/path/to/libroutez/ruby
(setting RUBYLIB is only necessary if you want to use ruby, python is used
by the graph creation utility, so you almost certainly do want that in your
path)
4. Build a graph.
To reduce application start up time, libroutez uses a custom graph format
which is created from GTFS and OpenStreetMap data. The creategraph utility
is used to create this.
The invocation is pretty simple. If you want to create a graph file called
'mygraph.routez', simply invoke creategraph.py as follows:
./creategraph.py /path/to/gtfsfeed.zip --osm="/path/to/osmfile.osm" \
mygraph.routez mygraph-gtfsmapping.yml
Want some sample data to play with? You can download the combination of
William Lachance's Halifax GTFS and Geobase data:
- http://wlach.masalalabs.ca/hfxfeed.zip
- http://wlach.masalalabs.ca/greater-hrm-geobase.osm.gz
The Halifax GTFS feed is produced by me, based on information provided
by the city of Halifax. For more information, please see:
http://github.com/wlach/halifax-transit-feed.
The OSM data is derived from the GeoBase dataset provided by the
government of Canada, and is distributed under the following terms:
http://geobase.ca/geobase/en/licence.jsp
5. Starting playing with the library.
Now that you've built a graph, you can start planning trips. Try the
'testgraph' mini program in examples. The following corresponds to
a trip from Cogswell and Maynard to Glengarry Gardens at 9am on Monday,
September 14th 2009 in Halifax, Nova Scotia, Canada:
"testgraph mygraph.routez 44.649942 -63.583457 44.6605 -63.7467 1252933200"
You should get a bunch of directions in "routezspeak" in response. :) Note that
no attempt is currently made to prettify the output, but hopefully this will at
least give you a starting point (perhaps that would be a fun little first
project for someone who wants to contribute?). Correlating the descriptive
information contained within a Google Transit feed with libroutez's internal
data structures will necessitate using the gtfs mapping yaml file generated
by the creategraph utility.
For those who like programming in ruby and python, there are examples of both
in the same directory as 'testgraph'.
=== Contributing ===
Contributions to libroutez are gratefully accepted. The easiest thing to do
is fork my repository on github (http://github.com/wlach/libroutez), apply
your change (make sure to add your name and nature of contribution to
AUTHORS), then either email me (at wrlach@gmail.com) or the libroutez mailing
list (http://groups.google.com/group/libroutez) to let us know about what you
did. Patch files sent directly to wrlach@gmail.com are also welcome.
In order for changes to be committed, they will need to be licensed under the
same terms as the rest of libroutez (the MIT license). Please note that you
consent to this in your git commit message or mail the libroutez mailing list
saying that this (or all) your contributions are released under the MIT
license.
|