[pgrouting-dev] Re: Network Layering support

[Jay Mahadeokar]

Hi,


On Sat, Jan 29, 2011 at 6:13 AM, Stephen Woodbridge <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
      - source node ID *s*, an unsigned 32-bit integer, 0 <= *s* < *n*;
      - target node ID *t*, an unsigned 32-bit integer, 0 <= *t* < *n*;
      - edge weight *w*, an unsigned 32-bit integer; note that the length of
      the longest shortest path must fit into a 32-bit integer
      - 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. *



*CH File Format:*

   - a *binary* file, 32-bit-interger organized
   - layout:
      - "CH\r\n" (0x32 0x48 0x0d 0x0a)
      - unsigned int: version (currently "1", shold be == compared)
      - unsigned int: number of nodes (= n)
      - unsigned int: number of original edges (= m1)
      - unsigned int: number of shortcut edges (= m2)
      - n times, for each node 0..(n-1):
         - unsigned int: level
      - m1 times, original edges:
         - unsigned int: source node
         - unsigned int: target node
         - unsigned int: weight
         - unsigned int: flags
      - m2 times, shortcut edges:
         - unsigned int: source node
         - unsigned int: target node
         - unsigned int: weight
         - unsigned int: flags
         - unsigned int: shortcut middle node
      - unsigned int: 0x12345678 as terminator
   - possible (bit) flags are:
      - 1 = forward edge
      - 2 = backward edge
      - 4 = shortcut edge
      - 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.



*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?

2. The queries will be same like shortest_path() just that at backend the
contraction hierarchies pre-processed data be used?

3. What should be the exact format for representing data for contraction
hierarchies?



> 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20110217/983fac17/attachment.html