PostGIS recursive query in order to find the longest connected subnetwork in my line network

Question

Let's said that I have this line network:

The goal is to find the longest connected subnetwork. So I want to find all the line's ID that are connected to the line with the ID = 1 because I know that the ID=1 is part of the longest connected subnetwork.

I guess that have to use a recursive query, I have try to run the following query:

WITH RECURSIVE connected_line AS (
    SELECT a.ID,a.geom FROM network a WHERE ID = 1
  UNION ALL
    SELECT b.ID,b.geom FROM network b, connected_line c
    WHERE st_intersects(b.geom, c.geom)
    AND NOT b.ID = c.ID
)
SELECT ID FROM connected_line;

The result should be:

ID
1
2
3
4

But the query is endless, how to create such a recursive query ?

Answer 1

The key here is to collect the visited edges into a path array and check against that in each iteration. Try

WITH RECURSIVE
  connected_line AS (
    SELECT 0 AS it,
           ARRAY[a.id] AS path,
           a.geom AS geom
    FROM network a
    WHERE id = 1
  UNION ALL
    SELECT c.it + 1 AS it
           array_append(c.path, b.id) AS path,
           b.geom AS geom
    FROM network b
    JOIN connected_line c
      ON ST_Intersects(b.geom, c.geom)
     AND b.id <> ALL(c.path)
)
SELECT it,
       path,
       geom
FROM connected_line;

Note:

This approach works if there is always exactly one connected edge that has not yet been found. However, it produces one path for each branch when the network forks and will find already visited edges when they were found in different paths.

If your question is answered by simply finding all connected sub-networks and get the longest, try ST_ClusterDBSCAN with eps := 0 and search for the max ST_Length of the clusters collected components. This way, you could also specify attributes to cluster (i.e. specify the sub-network type) for if you need to (in the mandatory OVER() clause, e.g. OVER(PARTITION BY <attribute>).

Answer 2

As suggested by @ThingumaBob, I resolved my problem with ST_ClusterDBSCAN (postgis 9.3 and above).

So I select the line's ID which are included in the longest subnetwork with:

WITH subnetwork AS
(
   SELECT gid, ST_CLUSTERDBSCAN(geom, eps := 0.0, minpoints := 1) OVER () AS sub, ST_LENGTH(geom) AS len
   FROM network
) 
SELECT gid FROM subnetwork
WHERE sub = (SELECT sub FROM (SELECT sub, SUM(len) AS t_len FROM subnetwork GROUP BY sub ORDER BY t_len DESC LIMIT 1) AS temp)

Answer 3

The documentation says:

When working with recursive queries it is important to be sure that the recursive part of the query will eventually return no tuples, or else the query will loop indefinitely. Sometimes, using UNION instead of UNION ALL can accomplish this by discarding rows that duplicate previous output rows.

In this case, the entire rows are indeed identical, so you can simply use UNION:

WITH RECURSIVE connected_line AS (
  SELECT a.ID,a.geom FROM network a WHERE ID = 1
  UNION                                                 -- no ALL
  SELECT b.ID,b.geom FROM network b, connected_line c
  WHERE st_intersects(b.geom, c.geom)
  AND NOT b.ID = c.ID
)
SELECT ID FROM connected_line;