[pgrouting-users] PgRouting and sub-networks / catchments

pgRouting pgrouting-users
1

Thank you Stephen (and sorry about the wonky list digest reply),

I much appreciate your explanation of the issues here. It sounds like
I may need a slightly better understanding of network solving
algorithms. This is probably beyond my technical capacity / time
budget right at the moment, but I'll keep this in mind as a potential
summer project.

Cheers,
Peter

------------------------------

Message: 2
Date: Wed, 25 May 2011 14:05:50 -0400
From: Stephen Woodbridge <woodbri@swoodbridge.com>
Subject: Re: [pgrouting-users] PgRouting and sub-networks / catchments
To: pgrouting-users@lists.osgeo.org
Message-ID: <4DDD44FE.4070001@swoodbridge.com>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed

Hi Peter,

pgRouting has a driving distance function which kind of does what you
want but not quite. I am trying to do something similar so I can
describe what you need to do and the problems are that I have found so far.

1. if you do a Dijkstra solutions from a given node, it will generate
the shortest path tree from that start node.

Problem: driving distance almost give you this as it returns:
vertex_id, edge_id, cost (to that vertex from the start).
In theory you should be able to reconstruct the tree from this
information, but there appears to be a bug in pgRouting where it does
not return all the edges and you end up with multiple disconnected trees
in the reconstruction of the tree because of the missing edge records.

Work-a-rounds:
1. wait for a bug fix
2. fix it yourself if you have the skill
3. clone the driving distance code and make a new function that returns:
vertex_id, parent_id, edge_id, cost and then reconstruct the tree from
this.

2. assuming you can get the Dijkstra tree, write a DFS (depth first
search) of the tree the collects the edges and of one of you outbound paths

3. create a linestring from the outbound path, maybe something like
select st_memunion(the_geom) from edges where gid in (list of edge
ids from DFS);

4. trim the linestring to your cutoff distance. look at the linear
referencing functions.

So bottom line, there is no canned solution for this today. Search the
dev list for subject "Driving Directions Revisited" for my discussion on
the bug above.

I would like to see a function that returns a setof paths from a start
node to a cutoff distance as you describe. Or a set of tools that make
the Dijkstra solution available for additional post processing.

-Steve W