[postgis-users] getting the longest connected path of a multistring

[Kevin Neufeld]

On 12/17/2010 5:33 AM, arno wrote:
> thanks for your pointers. The post does not match exactly my needs. And I
> did not succeeded in modifying it. Also, I don't want to go the c++ way for
> now. Fortunately, that computation is not a vital of my project, so I'll
> probably let it down, at least for  the moment.
>
> regards
> arno

If you're still curious, you could solve this using the recursive 
capabilities of postgres.  A routing solution would be nice, but a brute 
force approach works too from time to time.  Here, I'm LineMerging every 
combination of line segments that form a connected string, then I'm 
picking the longest path.

CREATE TEMP TABLE mlines (id serial, geom geometry);
-- sample result similar to your original post.
INSERT INTO mlines (geom)
SELECT (ST_Dump('
   MULTILINESTRING (
     ( 30 380, 120 280 ),
     ( 70 220, 120 280 ),
     ( 120 280, 260 280 ),
     ( 260 280, 290 310 ),
     ( 260 280, 350 190 ),
     ( 40 90, 90 40 ),
     ( 90 40, 150 40 ))'::geometry)).geom;


SELECT ST_AsText(geom)
FROM (
   WITH RECURSIVE t(path, geom) AS (
     -- select every linestring as a starting point.
     SELECT ARRAY[id], geom FROM mlines

     UNION ALL

     -- find all connecting linestrings and union them together.
     SELECT path || ARRAY[a.id], ST_Union(a.geom, t.geom)
     FROM mlines a, t
     WHERE NOT a.id = ANY(path)
     AND ST_DWithin(a.geom, t.geom, 0)
   )
   SELECT path, ST_LineMerge(geom) AS geom
   FROM t
   -- where the result are not multilinestrings
   WHERE ST_NumGeometries(ST_Multi(ST_LineMerge(geom))) = 1
) AS routes
ORDER BY ST_Length(geom) DESC
LIMIT 1;

                  st_astext
--------------------------------------------
  LINESTRING(30 380,120 280,260 280,350 190)
(1 row)

You could probably write a plpgsql function that accepts a 
multilinestring and returns the longest path.

Cheers,
Kevin