[pgrouting-dev] Re: Network Layering support
Daniel Kastl
daniel at georepublic.de
Fri Feb 18 07:57:25 EST 2011
Hi Jay,
Thank you for taking a look at the source code!
I think Anton can answer better to your questions, so I actually just want
to send you two additional links I just found about now:
- http://routingdemo.geofabrik.de/
- http://sourceforge.net/projects/routed/
It uses contraction hierarchies algorithm.
Regarding the license (AGPL) and the one of pgRouting (GPL) we probably need
to make sure, that CH will become an optional component.
>From my level of understanding I agree with Steve, that CH would just
provide another way of pre-processing the data than we do now. If this is
possible and how it works best within a database, that's probably the big
challenge.
@Anton ... did you catch this conversation?
Daniel
2011/2/17 Stephen Woodbridge <woodbri at swoodbridge.com>
> On 2/16/2011 10:17 PM, Jay Mahadeokar wrote:
>
>> Hi,
>>
>>
>> On Sat, Jan 29, 2011 at 6:13 AM, Stephen Woodbridge
>> <woodbri at swoodbridge.com <mailto:woodbri at swoodbridge.com>> wrote:
>>
>> *Source Code *(Quote from their web-page)
>>
>> /The source code of our implementation of contraction
>> hierarchies (CHs)
>> is now available under the terms of the AGPL. If you are
>> interested in
>> getting the source code write an email to Robert Geisberger
>> <http://algo2.iti.kit.edu/english/geisberger.php>.
>> /
>>
>>
>> I had requested Robert Geisberger for the source code of CH, and I went
>> thru it (Grateful to him for making the source available under AGPL). It
>> takes as input .ddsg files and produces contraction hierarchies in .ch
>> file format.
>>
>> *.DDSG* *File Format:*
>>
>> * a /text/-file, whitespace-separated;
>> * starts with single letter 'd';
>> * followed by the number of nodes /n/ and the number of edges /m/
>> * for each of the /m/ edges, we have
>> o source node ID /s/, an unsigned 32-bit integer, 0 <= /s/ < /n/;
>> o target node ID /t/, an unsigned 32-bit integer, 0 <= /t/ < /n/;
>> o edge weight /w/, an unsigned 32-bit integer; note that the
>>
>> length of the longest shortest path must fit into a 32-bit
>> integer
>> o the direction /d/: //
>>
>> + //0 = open in both directions //
>> + //1 = open only in forward direction (from /s/ to /t/) //
>> + //2 = open only in backward direction (from /t/ to /s/)
>> //
>> + //3 = closed //
>> //Note that specifying an edge (s,t,w,1) is equivalent to
>> specifying an edge (t,s,w,2). It does not matter which form
>> is used. In the current implementation, 3 is interpreted as
>> 0, i.e., closed roads are used in both directions. If you
>> really want to completely close a road, just leave it away. //
>>
>
> So this seems to define the minial requirements of the "ways" table in that
> we need to easily be able to extract this data and pass it to the
> pre-processor. And maybe the results need to be able to fetch some of this
> data.
>
> *CH File Format:*
>>
>>
>> * a /binary/ file, 32-bit-interger organized
>> * layout:
>> o "|CH\r\n|" (|0x32 0x48 0x0d 0x0a|)
>> o unsigned int: version (currently "|1|", shold be |==| compared)
>> o unsigned int: number of nodes (= n)
>> o unsigned int: number of original edges (= m_1 )
>> o unsigned int: number of shortcut edges (= m_2 )
>> o n times, for each node 0..(n-1):
>> + unsigned int: level
>> o m_1 times, original edges:
>>
>> + unsigned int: source node
>> + unsigned int: target node
>> + unsigned int: weight
>> + unsigned int: flags
>> o m_2 times, shortcut edges:
>>
>> + unsigned int: source node
>> + unsigned int: target node
>> + unsigned int: weight
>> + unsigned int: flags
>> + unsigned int: shortcut middle node
>> o unsigned int: |0x12345678| as terminator
>> * possible (bit) flags are:
>> o |1| = forward edge
>> o |2| = backward edge
>> o |4| = shortcut edge
>> o Note that not all edges of the original graph are listed as
>>
>> original edges. Edges that are not on any shortest path may
>> be removed or replaced by shortcuts.
>>
>
> Seem like this data could be put in tables or blob(s) depending on how much
> there. Obviously get data in/out of the database instead of these files will
> have an impact on the code, but hopefully that is manageable.
>
> *Few queries:*
>>
>>
>> 1. If pgRouting has to support the routing using contraction
>> hierarchies, what exactly is the idea? The postgres database table like
>> "ways" will be taken as input and the output would be another postgres
>> database table that will include data in form of contraction hierarchies?
>>
>
> I would envision that we take a table like "ways" as input. I could see
> additional columns or tables that might contain other data like turn
> restrictions, or whatever might be needed for input. But to keep it simple
> something similar to the current table which has edges, geometry, costs,
> etc. I might have nodes assigned or not if you process did that.
>
> Today we prep the "ways" table by creating the "source" and "target" node
> number columns and run assign_node_id() process to create nodes for each
> edge. I see some kind of process the reads this data and creates the
> contraction hierarchies data that then gets stored back into the database
> however you deem appropriate.
>
>
> 2. The queries will be same like shortest_path() just that at backend
>> the contraction hierarchies pre-processed data be used?
>>
>
> Correct. The input might change because the requirements for contraction
> hierarchies might be different, but a route request would be started by a
> call to a stored procedure. The result should be a record set where each
> represents traversing a single segment in the original "ways" table. For
> example the results might be simply a list of gid in the order of traversal
> or something more. Some example results might be:
>
> Each of these represents a set of record:
>
> 1. gid
> 2. gid, cost
> 3. gid, reversed, cost
> etc
>
> gid - unique edge id from the "ways" table
> cost - cumlative cost to get to the end of this segment along the path
> reversed - Y|N flag to indicate if traversed backwards or forwards
>
>
> 3. What should be the exact format for representing data for contraction
>> hierarchies?
>>
>
> I'm not sure what you are asking here. If this is the internal contraction
> hierarchies data created by the preprocessing step, then I think this is up
> to you. You might want to store it as a blob, if data can be spatially
> organized so you can fetch it as needed, then some brainstorming on how to
> do that might be appropriate.
>
> To some extent, performance of this process in the database will probably
> be limited to how efficiently you can access the data need to process the
> request.
>
> In the current process, we give a bounding box for the data we need,
> because we have to read that data and then build a boost graph structure and
> then solve that graph. Since the data is preprocessed, I'm not sure that is
> need for this so we might just have something like:
>
> select start_node from CH_pnt_to_node(start_point);
> select end_node from CH_pnt_to_node(end_point);
> select * from CH_solve("table", start_node, end_node);
>
> or something like that. Basically if there are helper function needed then
> that is appropriate.
>
> Best regards,
> -Steve
>
>
>> Right, but there are also a few other implementations of the
>> contraction hierarchies in the wild that might not be based on their
>> code, like the MONAV implementation, which is released on GPLv3, and
>> at least one person was looking at it in conjunction with Boost
>> (google: contraction hierarchies boost)
>>
>>
>>
>> --
>> Regards,
>> -Jay Mahadeokar
>>
>>
>>
>> _______________________________________________
>> pgrouting-dev mailing list
>> pgrouting-dev at lists.osgeo.org
>> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>>
>
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>
--
Georepublic UG & Georepublic Japan
eMail: daniel.kastl at georepublic.de
Web: http://georepublic.de
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20110218/a5747dfc/attachment-0001.html
More information about the pgrouting-dev
mailing list