bmander/graphserver

An open source multimodal trip planning engine

graphserver's Issues

link_nearby_stops() in graph compiler: Improve bounding

The link option currently links each station to all other stations within a hardcoded 0.05 degrees. This can make a huge number of links with lengths farther than most people would walk, enough to exceed physical memory and swap to a grinding halt.

This 0.1 degree 'square' bounding box can be quite large, and is not really square since longitude lines converge toward the poles. A more appropriate goal would be to link to all other stations within a radius of x meters.

Bounding box range could be a command line parameter, or better yet have both a lat and long component derived from a walk radius (itself a command line parameter) and a geographic location (either the centroid of all stops, or at each stop individually). In the iteration over all candidate stops within the bounding box, check if the 'obstructed' distance 'dd' is < x meters before deciding whether to link or not.

The bounding box specified in degrees must be bigger than x meters at the stop's geographic position.

Also:
For a stop A (outer loop) and a candidate stop for linking B (inner loop), this function creates both edges A->B and B->A. However, the outer loop is iterating over all stops, so B->A would be created
anyway. Is this redundant or am I missing something?

Ctypes and 64-bit platforms

Graphserver currently segfaults in 64-bit mode. The fix is to properly declare each CDLL method's restype.

gs_routeserver fails with RTreeError exception

I tried starting gs_routeserver on my graphdb file, and got this

 (graphserver)msoulier@egor:...thway_graphserver$ gs_routeserver vancouver.gdb handlers.yaml -p 8000
 Traceback (most recent call last):
   File "/home/msoulier/envs/graphserver/bin/gs_routeserver", line 8, in 
    load_entry_point('graphserver==0.1', 'console_scripts', 'gs_routeserver')()
   File "/home/msoulier/envs/graphserver/lib/python2.6/site-packages/graphserver-0.1-py2.6.egg/graphserver/ext/routeserver/routeserver.py", line 293, in main
    vertex_events = list(get_handler_instances( handler_definitions, 'vertex_handlers' ) )
   File "/home/msoulier/envs/graphserver/lib/python2.6/site-packages/graphserver-0.1-py2.6.egg/graphserver/ext/routeserver/routeserver.py", line 265, in  get_handler_instances
    handler_instance = handler_class(**handler.get("args", {}))
  File "/home/msoulier/envs/graphserver/lib/python2.6/site-packages/graphserver-0.1-py2.6.egg/graphserver/ext/routeserver/events.py", line 344, in __init__
    self.osmdb = OSMDB( osmdb_filename )
  File "/home/msoulier/envs/graphserver/lib/python2.6/site-packages/graphserver-0.1-py2.6.egg/graphserver/ext/osm/osmdb.py", line 88, in __init__
    self.index = Rtree( dbname )
  File "/home/msoulier/envs/graphserver/lib/python2.6/site-packages/Rtree-0.6.0-py2.6.egg/rtree/index.py", line 210, in __init__
    self.handle = core.rt.Index_Create(self.properties.handle)
  File "/home/msoulier/envs/graphserver/lib/python2.6/site-packages/Rtree-0.6.0-py2.6.egg/rtree/core.py", line 25, in check_void
    raise RTreeError(msg)
 rtree.core.RTreeError: Error in "Index_Create": Spatial Index Error:   IllegalStateException: SpatialIndex::DiskStorageManager: Failed reading pageSize.

I'm using spatialindex 1.5.0 and Rtree 0.6.0.

Add "transit reluctance" parameter to core

In order to avoid using transit (and favor walking), it would be nice to have a tunable "transit reluctance" parameter similar to the existing "walking reluctance" parameter.

Reference: http://groups.google.com/group/graphserver/browse_thread/thread/7a779082f0561c57

Possible fibheap issues/performance issues

David Turner of OTP said he observed some problems in the Java port of GS:

http://opentripplanner.org/changeset/135
http://opentripplanner.org/changeset/141

Worth looking at for their implications to the C code base.

Walking directions zigzag too much

Streets need a 'way' property, and a change from one way to another should carry a penalty.

segfault on g.shortest_path_tree() in graph.c, line 355

Rebasing to the latest graphserver code has been very bumpy. I am at commit

commit da19ba353f6c17beeec6197a56d183d66d5cb63e
Merge: 95cf72e e337760
Author: Brandon Martin-Anderson 
Date:   Fri Mar 26 11:48:12 2010 -0700

    Merge branch 'master' of [email protected]:bmander/graphserver

And now when I load a graphdb and try to find the shortest_path_tree, I get this segfault

Core was generated by `python ./gs_server.py --gtfsdb=toronto.gtfsdb --graphdb=toronto.gdb --debug'.
Program terminated with signal 11, Segmentation fault.
#0  vGetIncomingEdgeList (g=0x20e2da70, origin_label=0xa0b4944 "sta-10491") at graph.c:355
355         return this->incoming->next; //the first node is a dummy

Transit+bike trip planner

The narrative generation is the main part of this.

Database ORM

This is more of a feature request than a bug, but it'd be really nice if graphserver wasn't quite so tied to SQLite, and instead used an ORM like SQLAlchemy, allowing developers to choose whatever DB they care to use. If I can find some time, I might fork and spend a weekend or two looking into it. Others may find it a useful addition.

Graph compile handles inteprolated stops

Presently blank lines in the GTFS.stop_time.depart and GTFS.stop_time.arrive break everything. Interpolate stops as the GTFS intends.

gs_compile_gdb hangs on 64-bit machine

On a 64-bit platform I'm finding that I am unable to build a graphdb, as it is hanging part way through, chewing 100% cpu and never finishing.

It's been suggested that this is an sqlite3 on 64-bit problem, but I cannot find an existing report upstream.

Python 2.5 compatability

Not everything runs in Python 2.5; some random junk only works in 2.6

`Undefined symbols for architecture x86_64` error on Mac

Hello, everyone. When I try to compile this tool on mac, I got the following errors:

Undefined symbols for architecture x86_64:
   "_alWalk", referenced from:
       _alNew in edgetypes.o
   "_alWalkBack", referenced from:
       _alNew in edgetypes.o
   "_crWalk", referenced from:
       _crNew in edgetypes.o
   "_crWalkBack", referenced from:
       _crNew in edgetypes.o
   "_egressWalk", referenced from:
       _egressNew in edgetypes.o
   "_egressWalkBack", referenced from:
       _egressNew in edgetypes.o
   "_elapseTimeWalk", referenced from:
       _elapseTimeNew in edgetypes.o
   "_elapseTimeWalkBack", referenced from:
       _elapseTimeNew in edgetypes.o
   "_haWalk", referenced from:
       _haNew in edgetypes.o
   "_haWalkBack", referenced from:
       _haNew in edgetypes.o
   "_hbWalk", referenced from:
       _hbNew in edgetypes.o
   "_hbWalkBack", referenced from:
       _hbNew in edgetypes.o
   "_headwayWalk", referenced from:
       _headwayNew in edgetypes.o
   "_headwayWalkBack", referenced from:
       _headwayNew in edgetypes.o
   "_linkWalk", referenced from:
       _linkNew in edgetypes.o
   "_linkWalkBack", referenced from:
       _linkNew in edgetypes.o
   "_streetWalk", referenced from:
       _streetNew in edgetypes.o
   "_streetWalkBack", referenced from:
       _streetNew in edgetypes.o
   "_tbWalk", referenced from:
       _tbNew in edgetypes.o
   "_tbWalkBack", referenced from:
       _tbNew in edgetypes.o
   "_waitWalk", referenced from:
       _waitNew in edgetypes.o
   "_waitWalkBack", referenced from:
       _waitNew in edgetypes.o
 ld: symbol(s) not found for architecture x86_64

The command I use is python setup.py install. My mac is macOS High Sierra 10.13.4. I have made the following modifications to make it pass C99 standard. Thanks if anyone can help!

-- a/core/hashtable_itr.h
+++ b/core/hashtable_itr.h
@@ -28,20 +28,12 @@ hashtable_iterator(struct hashtable *h);
 /* hashtable_iterator_key
  * - return the value of the (key,value) pair at the current position */

-extern inline void *
-hashtable_iterator_key(struct hashtable_itr *i)
-{
-    return i->e->k;
-}
+void *hashtable_iterator_key(struct hashtable_itr *i);

 /*****************************************************************************/
 /* value - return the value of the (key,value) pair at the current position */

-extern inline void *
-hashtable_iterator_value(struct hashtable_itr *i)
-{
-    return i->e->v;
-}

pygs does not find C library under Cygwin

Under Cygwin, pygs doesn't correctly find the standard C library.

The culprit is the following line in pygs/graphserver/gsdll.py:
libc = cdll.LoadLibrary(find_library('c'))

A more general solution would be to replace the above line with something like:

# Adapted from ctypes.test.test_loading
# Find and load the c runtime library

libc_name = None
if sys.platform == "cygwin":
  libc_name = "cygwin1.dll"
else:
  libc_name = find_library("c")
if not libc_name:
  raise ImportError('could not determine which c runtime library to
  use')
libc = cdll.LoadLibrary(libc_name)

typo in gs_import_osm.py

vertices_namespace should be vertex_namespace line 66.

slog values: {}
 importing osmdb 'provence-alpes-cote-d-azur.osmdb' into graphdb 'provence-alpes-cote-d-azur.gdb'
Traceback (most recent call last):
File "/home/vpicavet/work/local/bin/gs_import_osm", line 9, in <module>
 load_entry_point('graphserver==0.1', 'console_scripts', 'gs_import_osm')()
File "/home/vpicavet/work/local/lib/python2.6/site-packages/graphserver-0.1-py2.6.egg/graphserver/compiler/gdb_import_osm.py", line 112, in main
  gdb_import_osm(gdb, osmdb, options.namespace, slogs, profiledb);
File "/home/vpicavet/work/local/lib/python2.6/site-packages/graphserver-0.1-py2.6.egg/graphserver/compiler/gdb_import_osm.py", line 66, in gdb_import_osm
  for i, (vertex1_label, vertex2_label, edge ) in enumerate( edges_from_osmdb( osmdb, vertices_namespace, slogs, profiledb ) ):
 NameError: global name 'vertices_namespace' is not defined

inconsistent SQL in graphdb.py

Error when compiling an OSM database to a graphdb.
edges table is created with 3 fields and add_edge tries to insert 4 values :

$ ~/work/local/bin/gs_import_osm provence-alpes-cote-d-azur.gdb provence-alpes-  cote-d-azur.osmdb
slog values: {}
importing osmdb 'provence-alpes-cote-d-azur.osmdb' into graphdb 'provence-alpes-cote-d-azur.gdb'
0/2282923 edges loaded
Traceback (most recent call last):
File "/home/vpicavet/work/local/bin/gs_import_osm", line 9, in <module>
  load_entry_point('graphserver==0.1', 'console_scripts', 'gs_import_osm')()
File "/home/vpicavet/work/local/lib/python2.6/site-packages/graphserver-  0.1-py2.6.egg/graphserver/compiler/gdb_import_osm.py", line 112, in main
  gdb_import_osm(gdb, osmdb, options.namespace, slogs, profiledb);
File "/home/vpicavet/work/local/lib/python2.6/site-packages/graphserver-   0.1-py2.6.egg/graphserver/compiler/gdb_import_osm.py", line 73, in gdb_import_osm
  gdb.add_edge( vertex1_label, vertex2_label, edge, cursor )
File "/home/vpicavet/work/local/lib/python2.6/site-packages/graphserver-0.1-py2.6.egg/graphserver/graphdb.py", line 109, in add_edge
  c.execute( "INSERT INTO edges VALUES (?, ?, ?, ?)", (from_v_label, to_v_label, cPickle.dumps( payload.__class__ ), cPickle.dumps( payload.__getstate__() ) ) )
sqlite3.OperationalError: table edges has 3 columns but 4 values were supplied

Allow for selection of particular mode(s)

It would be nice to have a way to select particular modes, perhaps using the required "route_type" parameter in the GTFS spec.

This way, for example, if I have a graph DB with road, bus and train network data, I would be able to generate a walking-only route, or a route that uses walking and trains but no buses. This would be useful for allowing user-preference to come into play.

Reference: http://groups.google.com/group/graphserver/browse_thread/thread/7a779082f0561c57

Contraction heirarchies should stop a a common meeting point

From David Turner:

I think one of them was that the CH query code did a full
dijkstra on the up and down graphs rather than stopping once it there is
some meeting point that is optimal.

From BMA:
That was just lazyness on my part. The improvement would result in a
constant factor speedup, more or less.

gs_import_osm -- NameError: global name 'vertices_namespace' is not defined

I installed graphserver from git, spatialindex-1.4.0, and RTree 0.5.0 via easy_install, following the instructions.

Running gs_import_osm on map.osm from the test directory fails with the error:

$ gs_import_osm map.gdb map.osmdb
slog values: {}
importing osmdb 'map.osmdb' into graphdb 'map.gdb'
Traceback (most recent call last):
  File "/usr/bin/gs_import_osm", line 9, in <module>
    load_entry_point('graphserver==0.1', 'console_scripts', 'gs_import_osm')()
  File "/usr/lib/python2.6/site-packages/graphserver-0.1-py2.6.egg/graphserver/compiler/gdb_import_osm.py", line 112, in main
    gdb_import_osm(gdb, osmdb, options.namespace, slogs, profiledb);
  File "/usr/lib/python2.6/site-packages/graphserver-0.1-py2.6.egg/graphserver/compiler/gdb_import_osm.py", line 66, in gdb_import_osm
    for i, (vertex1_label, vertex2_label, edge ) in enumerate( edges_from_osmdb( osmdb, vertices_namespace, slogs, profiledb ) ):
NameError: global name 'vertices_namespace' is not defined

Changing 'vertices_namespace' to 'vertex_namespace' on line 66 of compiler/gdb_import_osm.py results in a different error:

$ gs_import_osm map.gdb map.osmdb
slog values: {}
importing osmdb 'map.osmdb' into graphdb 'map.gdb'
0/50664 edges loaded
Traceback (most recent call last):
  File "/usr/bin/gs_import_osm", line 9, in <module>
    load_entry_point('graphserver==0.1', 'console_scripts', 'gs_import_osm')()
  File "/usr/lib/python2.6/site-packages/graphserver-0.1-py2.6.egg/graphserver/compiler/gdb_import_osm.py", line 112, in main
    gdb_import_osm(gdb, osmdb, options.namespace, slogs, profiledb);
  File "/usr/lib/python2.6/site-packages/graphserver-0.1-py2.6.egg/graphserver/compiler/gdb_import_osm.py", line 73, in gdb_import_osm
    gdb.add_edge( vertex1_label, vertex2_label, edge, cursor )
  File "/usr/lib/python2.6/site-packages/graphserver-0.1-py2.6.egg/graphserver/graphdb.py", line 109, in add_edge
    c.execute( "INSERT INTO edges VALUES (?, ?, ?, ?)", (from_v_label, to_v_label, cPickle.dumps( payload.__class__ ), cPickle.dumps( payload.__getstate__() ) ) )
  sqlite3.OperationalError: table edges has 3 columns but 4 values were supplied

Removing the 4th value from the insert statement at graphdb.py:109 allows data to be inserted but when I run gs_gdb_inspect osm-92080455, I get None instead of <Street ...> objects.

Transit + bike graph generation

Mostly built, just needs to be completed.

Documentation is a little sparse

Documentation seems to be a little thin, with lots of digging around the internals required to get an idea as to how to use graphserver. The examples on http://graphserver.sourceforge.net/ seem to be pretty out of date. Would be nice if there was some good documentation here, maybe in the wiki. Tons and tons of examples would be great.

gs_import_osm not tolerant to preexisting indices

Following the instructions at http://bmander.github.com/graphserver/ I am trying to integrate GTFS and OSM data.

When running gs_import_osm on my osmdb file, it works for a while and then fails.

100201/103282 edges loaded
101234/103282 edges loaded
102267/103282 edges loaded
103300/103282 edges loaded
indexing vertices...
Traceback (most recent call last):
  File "/home/msoulier/envs/pathway/bin/gs_import_osm", line 8, in 
    load_entry_point('graphserver==0.1', 'console_scripts', 'gs_import_osm')()
  File "/home/msoulier/envs/pathway/lib/python2.6/site-packages/graphserver-0.1-py2.6.egg/graphserver/compiler/gdb_import_osm.py", line 87, in main
    gdb_import_osm(gdb, osmdb, options.namespace, slogs);
  File "/home/msoulier/envs/pathway/lib/python2.6/site-packages/graphserver-0.1-py2.6.egg/graphserver/compiler/gdb_import_osm.py", line 56, in gdb_import_osm
    gdb.index()
  File "/home/msoulier/envs/pathway/lib/python2.6/site-packages/graphserver-0.1-py2.6.egg/graphserver/graphdb.py", line 143, in index
    c.execute( "CREATE INDEX vertices_label ON vertices (label)" )
sqlite3.OperationalError: index vertices_label already exists

Seems like that exception should just be caught. Ok, it exists. Move on.

Segments need to be downvotable

Like, you get some plan, and it's absolutely terrible for some reason. You need to be able to downvote it somehow.

transfers.txt is not handled currently

This is what is adopted:
http://code.google.com/transit/spec/transit_feed_specification.html#transfers_txt___Field_Definitions

This is what is currently implemented (for a connections.txt file):
http://github.com/bmander/graphserver/blob/master/pygs/graphserver/compiler/gdb_import_gtfs.py#L155
http://github.com/bmander/graphserver/blob/master/pygs/graphserver/ext/gtfs/gtfsdb.py#L196

This is a minor change.