[postgis-devel] Discussion about routing in PostGIS
Jean-Denis Giguère
jdenisgiguere at fastmail.fm
Tue Apr 19 08:08:21 PDT 2005
Hi all,
Few comments on current discussion.
*Some time, graph used for routing must be more complex than :
intersection is a node and segment is an arc. For example, an
intersection doesn't "cost" the same thing if you turn right or left in
"fastest path" computation.
* I read a very interesting paper about this topic :
Zhan F B, A set of shortest path algorithms that run fastest on real
networks in Proceedings GIS/LIS 96, Falls Church, 1996, p. 755-764
* The boost graph library (http://www.boost.org/libs/graph/) offer a
number of functionnalities for graph modeling.
* We are developping an open source sptalial extension for computer
aided dispatch. It is at an early stage, but we will work on routing
with postgis at beginning of May.
* It could be interesting to integrate a flexible geocoding support. If
you have suggestion, they are welcome.
Best regards,
Jean-Denis
Sylvain Pasche wrote:
> Hello,
>
> I understand the concept of subgraph is a quite powerful datastructure
> for dealing with large graph, avoiding the intermediate structure in
> memory, and finding quickly neighbour nodes and edges.
>
> I would however propose another more simple approach, which is not tied
> to geographical graphs. This can be some "proof of concept" which could
> lead to another implementation using your subgraph proposal.
>
> Basically, we have a node and an edges table. The node table contains an
> id and optional fields like the geometry. The edge table contains edge
> id, node start and end id's, and other optional fields. The cost could
> either be in the node / edge table, or in another table mapping
> node/edge id to their cost (useful for precomputed costs scenarios (no
> main-roads, fastest / shortest path, ...).
>
> For the implementation we have either the dglib approach which consist
> in fetching all nodes/edges, building the internal dglib graph
> structure, and computing the shortest path. This is only one sql query
> for fetching all data, but may consume more memory.
>
> The other approach is to implement the Dijkstra algorithm directly in
> PostGIS, fetching nodes successors for each step of the algorithm. This
> approach will generate a query for each node at least.
>
> If this compromise seems acceptable, I will do some testing with these
> different approaches, and give you some feedback about the results.
>
> Cheers,
>
> Sylvain
>
> Le jeudi 07 avril 2005 à 13:28 -0700, Chris Hodgson a écrit :
>
>>I think that in order to do routing _well_ in the database, there first
>>needs to be some concept of graph structure storage in the database. It
>>is clearly _possible_ to build a graph using standard geometries with
>>node ID's and/or edge ID's, and using standard indexes on the ID's will
>>speed up access to them. But traversing this network will be pretty
>>slow if done by querying one ID at a time (ie. get all edges adjacent to
>>this node, repeated many times over). The only alternative (if using
>>standard database tables and indexes) is to read the entire table into
>>memory and build an in-memory graph data structure - which will
>>obviously be much faster, but we will be limited to dealing with graph
>>structures that are small enough to fit into memory - a limitation which
>>I don't think is acceptable.
>>So, I think to do this right, we need a way to store a graph structure
>>in the database which is somehow more advanced than just a table of
>>geometries with their adjacencies identified. What we want is a way to
>>store on disk, the same graph structure that we would build in memory,
>>in a randomly-accessible fashion. That is to say, connected sub-graphs
>>of the complete graph should be stored in each table row, with some kind
>>of index to allow speedy access to the nieghboring sub-graphs.
>>
>>My idea to build this "graph table" is something like this:
>>
>>1) break the graph into connected sub-graphs, with every edge belonging
>>to exactly one subgraph, and every node belonging to one or more sub-graph
>>2) index the graphs by the IDs of the of nodes on the edge of the subgraph
>>
>>Now we can change the "get all edges adjacent to this node" query to a
>>"get all subgraphs adjacent to this node" query, which will have to be
>>done significantly fewer times within any given algorithm (eg.
>>shortest-path/routing).
>>
>>I'm not sure what the ideal characteristics of the subgraphs are. They
>>definitely need to fit into a reasonable amount of memory - probably
>>fitting them into the page size of the database would be the way to go.
>>The geometric and topological characteristics need to be considered as
>>well... the more nodes inside each subgraph, and the fewer nodes on the
>>edges of each subgraph, the fewer queries will be required to traverse
>>them (I think?). Should they be geometrically clustered, or
>>topologically clustered?
>>
>>One way I might see this working is that the graph structure table is
>>initially constructed from the geometry table, and then a trigger causes
>>any updates to the geometry table to cause similar updates in the graph
>>table - if this is the case, we also need to consider how our
>>subgraphing algorithm will be affected by updates to the geometries -
>>ideally the subgraphs will be able to shrink, and to grow and eventually
>>split, in an organic fashion.
>>
>>Also, we would need to decide whether the attributes and/or geometries
>>of the features associated with each edge of the graph should be stored
>>inside the graph structure, or not. If they are not, then the edges of
>>the graph would simply store pointers to the associated features, and
>>our graph stucture becomes more of a new type of index than anything
>>else. I don't know if this sort of "graph index" could be implemented
>>using GiST, but I think it may be too different of an idea for GiST to
>>handle.
>>
>>For the specific application of routing, it makes sense to store the
>>cost of each edge inside the graph structure, as this is the only
>>attribute (including the geometry) of interest for each edge. This could
>>be an optional additional piece of information stored in the index, or
>>we could decide that the graph should actually be stored its own table,
>>completely separate from the original feature table once it has been built.
>>
>>Sorry if I'm rambling here, but since we're brainstormning, I think it
>>is relevant.
>>
>>After considering the above, I think the idea that I like best is to
>>implement the graph structure inside a new kind of index on the geometry
>>table. This index would either need some additional parameters to
>>specify exactly how the graph is built, or the geometry table would be
>>required to have specific field names for the pieces of information
>>required to build the graph (node IDs). The index could also have the
>>option of storing the weight value of each edge inside the index, in
>>order to speed up routing-oriented queries.
>>
>>Having not done much of the work on PostGIS, and never working
>>specifically within the Postgresql code, I'm guessing this would require
>>significant work, probably as much or more than PostGIS itself, and it
>>may need to be tightly integrated into postgresql (ie. need to have
>>changes made within postgresql in order to support it). Paul Ramsey and
>>I have discussed this sort of functionality before... I think it would
>>be very exciting to implement and could potentially be very "killer app"
>>to add to PostGIS - as if PostGIS wasn't already a killer app itself ;)
>>
>>I think I'll leave it at that for now...
>>
>>Chris
>>_______________________________________________
>>postgis-devel mailing list
>>postgis-devel at postgis.refractions.net
>>http://postgis.refractions.net/mailman/listinfo/postgis-devel
>
> _______________________________________________
> postgis-devel mailing list
> postgis-devel at postgis.refractions.net
> http://postgis.refractions.net/mailman/listinfo/postgis-devel
More information about the postgis-devel
mailing list