[RouterGeocoder] Some thoughts on OpenRouter

[Stephen Woodbridge]

Hi all,

Here are some of my initial thoughts on the OpenRouter. This is an 
attempt to get a lot of ideas that have been floating around in my head 
and to put some structure to them. It is going to need a lot of 
additional work and input. I also do not see this all getting built all 
at once. I imagine that we will tackle bits and pieces at a time with 
other pieces being stubbed out, simplified or may be hard-coded 
initially, and that we will refactor those parts latter as we build them 
out. I see initially that there are three major areas:

Graph Builder
-------------
1) need requirements for non-transportation analysis?
2) modular data source readers
    a) file formats (GDAL/OGR)
    b) metadata to describe information structure
3) modular data store I/O
4) data store schema

The graph builder is a tool(s) that builds the graph used by the router 
library. This allows for any required preprocessing to be done here 
once. Since the router will likely have plug-in solvers and different 
network analysis that might require different graph structures, we may 
need to think about plug-in builders that service a family of solvers. 
While I'm familiar with transportation network analysis, there has been 
a desire expressed to not limit this to traffic it networks. I see no 
need to limit this, but input and expertise will need to be found to 
help identify any additional requires that these separate analysis 
require. Hopefully using a plug-in architecture will make it easy to 
support these as they are needed.

The generic tasks here involve reading various physical file formats and 
(GDAL/OGR) is a good candidate for that, but we also need to understand 
the content of the data files and how it relates to the task of building 
the graph. This might be via an XML document describing the data source. 
We might want to have an optional GUI tool that can explore the data and 
collect information from the user and then write the XML document and 
trigger the builder to run. I can envision a given builder plug-in 
calling standard APIs for reading and writing data. We need to create a 
logical graph and store it in some physical stores. The logical graph 
may need to keep a table of back pointers to the original data if it is 
not copied forward. For example and network graph needs little or not 
geometry to produce a solution, but the geometry is needed to create a 
route polyline and/or driving directions. The physical stores might be a 
packed data file that gets memory mapped into internal data structures, 
or it might be a database blob, or a set of database tables depending on 
the application environment's requirements.

OpenRouter Library
-------------------
1) general network analysis library with plug-in solvers
2) layered access to data to separate physical and logical data stores
3) plug-in post-solution processors
    a) create isochronal polygons
    b) explicate driving directions
    c) format results as XML, JSON, CSV, text, etc
    d) save solution as ...
    e) ...
4) ...

This is the core analysis library, that will get initialized and open a 
graph builder graph, then take take some input and solve the requested 
problem. After the solution, a chain of post processors can be called on 
the solved graph as required and finally cleanup routines are called to 
release system resources.

Applications using the library
------------------------------
1) commandline tool
2) debugging - graph anaysis query tool
3) webservice instance (using OpenLS?)
4) embed in other applications
5) embed in Databases
6) SWIG library interfaces to Perl, Python, PHP, C#, etc
7) ...

Finally some applications are build around the library. I see a 
commandline tool and a debugging - graph analysis query tool as usual 
tools for developing the library, testing the library, etc. A webservice 
tool would make this immediately useful to the user community for 
driving directions in a AJAX web 2.0 environment like OpenLayers 
applications. SWIG interfaces would help extent the reach of the library 
into other communities.

So my goal in this document is to try and paint in broad strokes an 
outline of where I think we want to get to. The purpose for this is that 
I hope it will allow developers to see down the road so when they are 
making decisions about implementation they can better choose options 
that will need less work to refactor as we tackle the next requirement. 
This is just me thinking out loud and I'm open to anyone that want to 
build upon this. It would be great if people want to take any chunks of 
this and drill down into a more complete analysis, design and/or code.

Misc. things to do:
1) look at Boost Graph (yet again)
2) look at how grass handles graph building/solving

Thoughts?

-Steve