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