Network Walking in PostGIS

One of the new features in PostgreSQL 8.4 was the “WITH RECURSIVE” clause available for queries. It allows you to define a subquery based on a recursive term — fancy language for a function that calls itself. One of the favorite uses of recursion is walking a network. Geospatial applications use networks all the time: electrical grids, stream systems, and storm sewers are all directed networks (they have unidirectional flow).

Here’s an example of network walking using a simple collection of segments. As is common in many GIS applications, the segment are implicitly connected — their end points are coincident with the start points of other segments.

CREATE TABLE network ( segment geometry, id integer primary key );

INSERT INTO network VALUES ('LINESTRING(1 1, 0 0)', 1);
INSERT INTO network VALUES ('LINESTRING(2 1, 1 1)', 2);
INSERT INTO network VALUES ('LINESTRING(1 2, 1 1)', 3);
INSERT INTO network VALUES ('LINESTRING(3 1, 2 1)', 4);
INSERT INTO network VALUES ('LINESTRING(3 2, 2 1)', 5);
INSERT INTO network VALUES ('LINESTRING(2 3, 1 2)', 6);
INSERT INTO network VALUES ('LINESTRING(1 3, 1 2)', 7);
INSERT INTO network VALUES ('LINESTRING(4 2, 3 2)', 8);
INSERT INTO network VALUES ('LINESTRING(3 4, 2 3)', 9);
INSERT INTO network VALUES ('LINESTRING(2 4, 2 3)', 10);
INSERT INTO network VALUES ('LINESTRING(1 4, 1 3)', 11);
INSERT INTO network VALUES ('LINESTRING(4 3, 4 2)', 12);
INSERT INTO network VALUES ('LINESTRING(4 4, 3 4)', 13);

CREATE INDEX network_gix ON network USING GIST (segment);

Visually, the network looks like this:



To walk our network, use a WITH clause that starts with one segment, then repeatedly adds the next downstream segment to the collection. In our case, the “next downstream segment” is defined as a segment whose start point is close to the end point of the current segment. We’ll walk down from segment 6.

WITH RECURSIVE walk_network(id, segment) AS (
    SELECT id, segment FROM network WHERE id = 6
  UNION ALL
    SELECT n.id, n.segment
    FROM network n, walk_network w
    WHERE ST_DWithin(ST_EndPoint(w.segment),ST_StartPoint(n.segment),0.01)
  )
SELECT id
FROM walk_network

Which returns:

 id
----
  6
  3
  1
(3 rows)

From 6 to 3 to 1, correct! Once we have our walker producing the results we want, we can wrap more PostGIS and PostgreSQL functions around the walker to produce a finished product. Here’s a function that takes in an edge identifier and outputs a linestring based on the downstream path.

CREATE OR REPLACE FUNCTION downstream(integer)
RETURNS geometry
LANGUAGE sql
AS '
WITH RECURSIVE walk_network(id, segment) AS (
    SELECT id, segment FROM network WHERE id = $1
  UNION ALL
    SELECT n.id, n.segment
    FROM network n, walk_network w
    WHERE ST_DWithin(ST_EndPoint(w.segment),ST_StartPoint(n.segment),0.01)
  )
SELECT ST_MakeLine(ST_EndPoint(segment))
FROM walk_network
' IMMUTABLE;

And here’s the function in action, generating the downstream path from segment 12.

=# SELECT ST_AsText(Downstream(12));

            st_astext
---------------------------------
 LINESTRING(4 2,3 2,2 1,1 1,0 0)
(1 row)

Check the generated path against our network picture — looks good!