5

Let's said that I have this line network:

enter image description here

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 ?

  • 1
    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
4

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

  • 1
    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
  • 2
    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
1

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

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
  • 1
    Well, it's fixed in PostGIS 2.5.0, but that one is not yet released. – CL. Jun 20 '18 at 8:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.