wlach / libroutez Goto Github PK

=== 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). Windows is not currently supported.

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)
 - Python Rtree and spatial index (http://pypi.python.org/pypi/Rtree/0.5.0)
 - Google Transit Data Feed (http://code.google.com/p/googletransitdatafeed/)
 - 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 [email protected]) or the libroutez mailing 
list (http://groups.google.com/group/libroutez) to let us know about what you 
did. Patch files sent directly to [email protected] 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.