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

[Stephen Woodbridge]

On 12/16/2010 8:28 AM, arno wrote:
> Hi,
> I have a multistring geometry, and I want to get the maximal length of
> consecutive linestrings.
>
> For example, if the following example is my multilinestring, I want to get the
> length of A + B + E
>
>
>
> \ A
>   \                    C
>    \         B          /
>     -------------------
>   /                    \
>    D                    \
>                          \  E
>                           \
>      \ F                   \
>       \   G
>        \___
>
> So, I think I should try to generate all the possible paths and check their
> length and get the maximum of them.
> I've looked at ST_LineMerge but, from what I understand, it will take the first
> segment, and add them as soon as it can. So, I think I'll end up with (ABC, D,
> E, FG). Am I right about that ?
>
> So, I've tried to decompose the geom in an array of linestring (with
> ST_NumGeometries and ST_GeometryN), then rearrange them with a permutation
> (http://wiki.postgresql.org/wiki/Permutations). But this quickly became
> complicated, so before going on in that direction, I was wondering if there was
> an easy/direct way of doing what I want.

This class of problems belongs to graph theory. While there is not a 
direct solution to this problem implemented in pgRouting, pgRouting does 
deal with graph problems in the postgresql/postgis database by using the 
boost graph library. You might want to look into boost graph if you are 
a C++ programmer, or start a discussion on the pgRouting list.

Here is an algorithm that may be helpful:
http://en.wikipedia.org/wiki/Longest_path_problem

CC this to the pgRouting list.

Hope this helps,
   -Steve