[postgis-devel] Discussion about routing in PostGIS

[Sylvain Pasche]

Hello,

I am investigating the solution of integrating routing algorithm inside
PostGIS, as it was announced previously on the list.

Of course, such an integration is not a trivial task, and I guess there
are several different scenarios and possibilities for such a
development. I see this mail more like brainstorming, for gathering
ideas, proposals, or listing existing things from which we could take
inspiration. I will try not to be to biased towards the problem we need
to solve (shortest path calculation), one goal would be to be the more
generic possible across different problem domains.

Regarding the routing algorithms, a GNU licenced library named DGLib
(http://grass.itc.it/dglib/) is available for performing tasks such as
shortest path, minimal spanning tree calculation and others.

Background
==========

I give below some background information, to clarify the situation.

The graph library has to deal with the following information (for
instance for the shortest path calculation):

input:
list of nodes with optional associated costs
list of edges with associated costs.
Relations between nodes and edges (directed or not)

output:
list of traversed nodes and edges, with associated cost (total cost can
be calculated from this).

Possible usage scenario
===========================

Maybe some usage scenario is useful for having a better feeling about
the data flow:

* Static data: 
  * a list of nodes with associated geographical coordinates, and
identifiers.
  * a list of edges binding pairs of nodes together. Each edge has an
identifier, and an initial cost which is the geographical distance
between the two nodes. 

* Dynamic data:
  * Cost for each edge of the graph. These dynamic cost can take into
account the static geographical distance between nodes. In the real
world, this cost could be the mean speed possible on a road multiplied
with the road distance.

The task is to compute a list of nodes/edges for the shortest path
between two points of the graph, according to a dynamically calculated
list of costs. It should be possible to extract the node identifiers,
and the geographical line of the path.

Design discussion
=================

Datatypes:

As we can see from the above, standard PostGIS datatypes are missing
some information, like nodes id, edges list, ...

One approach is to map the algorithm on the current PostGIS datatypes,
like in the following function (idea from O. Courtin):

static PG_LWGEOM *
dglib_shortest_path(PG_LWGEOM * geom, LWPOINT * from, LWPOINT * to, 
                int strict, int use_cost, int directed)

where:
 stricts: from and to must belong the the graph, nearest otherwise
 use_cost: if true, and points are 3DM/4D: uses the M value otherwise,
uses the cost from the geography distance.
 directed: flag for directed graph.

The resulting Line will be the shortest path.

However, there are some shortcomings with this approach:

- The notion of nodes and edges identifier is not kept. These should be
looked elsewhere, probably in a (x, y) -> id table.
- To dynamically modify the cost of an edge, the whole geometry has to
be modified.


Another approach would be to have some specific "directed graph"
datatypes, on which graph algorithm functions could be called. For
instance a datatype storing the whole graph and another structure for
the cost mapping. This way, different cost mapping structures could be
used in a function like

line1 = shortest_path(graph_structure, cost_mapping_structure1)

line2 = shortest_path(graph_structure, cost_mapping_structure2)

This is just simple illustration to introduce the concept of a specific
graph datatype.

Certainly there are other design approaches for this problem, I would be
pleased to hear from you ideas/thoughts on the matter.

In particular, the "how to others do" would certainly give valuable
informations in this domain. However, I did not find any reference on
the specific routing+sql problem. If you have informations about this it
would be great.


Thanks,

Sylvain Pasche