[pgrouting-users] Re: [postgis-users] getting the longest connected
path of a multistring
Stephen Woodbridge
woodbri at swoodbridge.com
Thu Dec 16 20:38:36 EST 2010
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
More information about the Pgrouting-users
mailing list