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

Peter Schmiedeskamp peter at thoughtspot.net
Fri May 27 12:00:51 EDT 2011

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.


> ------------------------------
> Message: 2
> Date: Wed, 25 May 2011 14:05:50 -0400
> From: Stephen Woodbridge <woodbri at swoodbridge.com>
> Subject: Re: [pgrouting-users] PgRouting and sub-networks / catchments
> To: pgrouting-users at lists.osgeo.org
> Message-ID: <4DDD44FE.4070001 at 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

More information about the Pgrouting-users mailing list