I was wondering how to walk networks without using pgRouting…. and found Paul Ramsey’s blog had the answer…
The text here is taken from his blog.. backed up here for future quick reference.
http://blog.cleverelephant.ca/2010/07/network-walking-in-postgis.html
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);
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)
This can be made into a function like this:
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)
