H2GIS

Fork me on GitHub

ST_Accessibility

Signatures

-- Return type:
--     TABLE[SOURCE, CLOSEST_DEST, DISTANCE]
ST_Accessibility('INPUT_EDGES', 'o[ - eo]'[, 'w'], 'ds');
ST_Accessibility('INPUT_EDGES', 'o[ - eo]'[, 'w'], 'dt');

Description

Calculates, for each vertex in a graph, the closest destination among several possible destinations as well as the distance to this destination.

Using this function will be faster than doing an equivalent calculation using ST_ShortestPathLength.

ST_Accessibility is implemented as follows: The graph is reversed, and Dijkstra's algorithm is run from each destination vertex. This is much more efficient than running Dijkstra's algorithm from each vertex to each destination and taking the minimum distance.

Input parameters
Variable Meaning
INPUT_EDGES Table containing integer columns EDGE_ID, START_NODE and END_NODE; and optionally a weight column w (if the graph is weighted) and/or an edge orientation column eo (required if global orientation is not undirected)
o Global orientation string: directed, reversed or undirected
eo Edge orientation column name indicating individual edge orientations: 1 (directed), -1 (reversed) or 0 (undirected); required if global orientation is directed or reversed
w Edge weights column name
ds Comma-separated destination string: 'dest1, dest2, ...'
dt Destination table name; must contain column DESTINATION containing integer vertex ids

Examples

-- We will do graph analysis on the directed weighted graph examined
-- in the ST_ShortestPath examples, illustrated below.
SELECT * FROM EDGES_EO_W;
-- | EDGE_ID | START_NODE | END_NODE | WEIGHT | EDGE_ORIENTATION |
-- |---------|------------|----------|--------|------------------|
-- |       1 |          1 |        2 |   10.0 |                1 |
-- |       2 |          2 |        4 |    1.0 |               -1 |
-- |       3 |          2 |        3 |    2.0 |                1 |
-- |       4 |          3 |        2 |    3.0 |                1 |
-- |       5 |          1 |        3 |    5.0 |                1 |
-- |       6 |          3 |        4 |    9.0 |                1 |
-- |       7 |          3 |        5 |    2.0 |                1 |
-- |       8 |          4 |        5 |    4.0 |                1 |
-- |       9 |          5 |        4 |    6.0 |                1 |
-- |      10 |          5 |        1 |    7.0 |                0 |
-- |      11 |          6 |        7 |    1.0 |                1 |
-- |      12 |          7 |        8 |    2.0 |                1 |

Destination string
SELECT * FROM ST_Accessibility('EDGES_EO_W',
    'directed - EDGE_ORIENTATION', 'WEIGHT', '2, 5');
-- | SOURCE | CLOSEST_DEST | DISTANCE |
-- |--------|--------------|----------|
-- |      1 |            5 |      7.0 |
-- |      2 |            2 |      0.0 |
-- |      4 |            2 |      1.0 |
-- |      3 |            5 |      2.0 |
-- |      5 |            5 |      0.0 |
-- |      6 |           -1 | Infinity |
-- |      7 |           -1 | Infinity |
-- |      8 |           -1 | Infinity |

SELECT * FROM ST_Accessibility('EDGES_EO_W',
    'directed - EDGE_ORIENTATION', 'WEIGHT', '2, 5, 7');
-- | SOURCE | CLOSEST_DEST | DISTANCE |
-- |--------|--------------|----------|
-- |      1 |            5 |      7.0 |
-- |      2 |            2 |      0.0 |
-- |      4 |            2 |      1.0 |
-- |      3 |            5 |      2.0 |
-- |      5 |            5 |      0.0 |
-- |      6 |            7 |      1.0 |
-- |      7 |            7 |      0.0 |
-- |      8 |           -1 | Infinity |

Destination table
-- Here we get the same results as before, but we do it using a
-- destination table.
CREATE TABLE DESTS(DESTINATION INT);
INSERT INTO DESTS VALUES (2), (5), (7);
SELECT * FROM ST_ACCESSIBILITY('EDGES_EO_W',
    'directed - EDGE_ORIENTATION', 'WEIGHT', 'DESTS');
-- | SOURCE | CLOSEST_DEST | DISTANCE |
-- |--------|--------------|----------|
-- |      1 |            5 |      7.0 |
-- |      2 |            2 |      0.0 |
-- |      4 |            2 |      1.0 |
-- |      3 |            5 |      2.0 |
-- |      5 |            5 |      0.0 |
-- |      6 |            7 |      1.0 |
-- |      7 |            7 |      0.0 |
-- |      8 |           -1 | Infinity |
Exercises
  1. Use ST_ShortestPathLength to verify the results of ST_Accessibility.
  2. Find an equivalence between ST_ShortestPathLength called on one source and ST_Accessibility called on one destination. Hint: Think about reversing the graph.
See also