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

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 ?

• See gis.stackexchange.com/q/94203/18189 for an example of a recursive query to do this. But the problem will be solved much, much faster by using `ST_ClusterDBSCAN` or `ST_ClusterIntersecting` instead of a recursive query. – dbaston Jun 19 '18 at 11:42

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>`).

• Great, I was indeed looking for `ST_ClusterDBSCAN` it work like a charm and is much much faster than any other solution. – obchardon Jun 19 '18 at 14:25
• Good answer, and the Cluster trick is good, though recursive queries are worth learning in their own right, imho. I have come to the conclusion that the harder the question/answer, the less upvotes it gets. Must go and answer a question about ST_Length :D. – John Powell Jun 20 '18 at 13:49
• @JohnPowellakaBarça thx! now that you mention it, remember this? actually a close call for a duplicate, and guess how that turned out for my upvote balance... – ThingumaBob Jun 20 '18 at 18:32

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)
``````

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;
``````
• Thanks for pointing that out. It could have been a solution, but due to this problem the UNION keyword can't be used with geometric fields. – obchardon Jun 20 '18 at 8:27
• Well, it's fixed in PostGIS 2.5.0, but that one is not yet released. – CL. Jun 20 '18 at 8:33