irstv/gdms-topology — pull request #50 by agouge (2013-05-28 23:20:33+00:00)
Title: Add ST_Distances

This addresses #41.

I add a function `ST_Distances` (currently for weighted graphs only) which may be used to calculate distances in the following scenarios:

* d(source, destination)
* d(source, *)
* All distances requested in a source-destination table.

The weight column name is an optional String argument. If omitted, the graph is considered unweighted. (But don't omit it for now, since this has not yet been implemented!)

The graph orientation is also an optional String argument, which may take on the values

* 'directed'
* 'reversed'
* 'undirected'

If a graph is directed (or reversed), we may also specify individual edge orientations by integers

* 1 (directed)
* -1 (reversed)
* 0 (undirected)

**in a column named 'edge_orientation'**. We don't add this to the list of parameters so as to avoid unnecessary clutter. If the graph orientation is omitted, it is assumed to be directed.

The unit tests cover the case of a weighted directed graph. It remains
to implement this for unweighted graphs and write unit tests for the other cases.

#### Possible signatures
```mysql
ST_Distances(edges, source_dest_table OR source[, destination][, 'weights'][, 'orientation']);
```

### Example usage
#### Calculate the distances to all reachable nodes
```mysql
-- Total nodes: 10 993.
-- 0. Directed, oriented by geometries (88)
CREATE TABLE dir_geom AS SELECT * FROM ST_Distances(routes.edges, 4663, 'weight', 'directed');
-- 1. Directed, individual edge orientations (10 607)
-- Update with the edge orientations.
ALTER TABLE routes.edges ADD COLUMN edge_orientation int;
UPDATE routes.edges SET edge_orientation=1 WHERE SENS='Direct';
UPDATE routes.edges SET edge_orientation=-1 WHERE SENS='Inverse';
UPDATE routes.edges SET edge_orientation=0 WHERE SENS='Double';
CREATE TABLE dir_edges AS SELECT * FROM ST_Distances(routes.edges, 4663, 'weight', 'directed');
-- 2. Reversed, individual edge orientations. (10 547)
CREATE TABLE rev_edges AS SELECT * FROM ST_Distances(routes.edges, 4663, 'weight', 'reversed');
-- 3. Undirected (10 741)
CREATE TABLE undir AS SELECT * FROM ST_Distances(routes.edges, 4663, 'weight', 'undirected');
-- Recover the geometries.
CREATE TABLE color_by_distance AS SELECT a.the_geom, b.source, b.destination, b.distance FROM routes.nodes a, undir b WHERE a.id=b.destination;
```