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