Hi,<br><br><br><div class="gmail_quote">On Sat, Jan 29, 2011 at 6:13 AM, Stephen Woodbridge <span dir="ltr"><<a href="mailto:woodbri@swoodbridge.com">woodbri@swoodbridge.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
*Source Code *(Quote from their web-page)<br><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><div class="im">
/The source code of our implementation of contraction hierarchies (CHs)<br>
is now available under the terms of the AGPL. If you are interested in<br>
getting the source code write an email to Robert Geisberger<br></div>
<<a href="http://algo2.iti.kit.edu/english/geisberger.php" target="_blank">http://algo2.iti.kit.edu/english/geisberger.php</a>>.<br>
/<br></blockquote></blockquote><div><br>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.<br>
<br><b>.DDSG</b> <b>File Format:</b>
<ul><li>a <i>text</i>-file, whitespace-separated;
</li><li>starts with single letter 'd';
</li><li>followed by the number of nodes <i>n</i> and the number of edges <i>m</i>
</li><li>for each of the <i>m</i> edges, we have
<ul><li>source node ID <i>s</i>, an unsigned 32-bit integer, 0 <= <i>s</i> < <i>n</i>;
</li><li>target node ID <i>t</i>, an unsigned 32-bit integer, 0 <= <i>t</i> < <i>n</i>;
</li><li>edge weight <i>w</i>, an unsigned 32-bit integer; note that the length of
the longest shortest path must fit into a 32-bit integer
</li><li>the direction <i>d<i>:
</i></i><ul><li><i><i>0 = open in both directions
</i></i></li><li><i><i>1 = open only in forward direction (from <i>s</i> to <i>t</i>)
</i></i></li><li><i><i>2 = open only in backward direction (from <i>t</i> to <i>s</i>)
</i></i></li><li><i><i>3 = closed
</i></i></li></ul>
<i><i>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.
</i></i></li></ul>
</li></ul><br><br><b>CH File Format:</b>
<ul><li>a <i>binary</i> file, 32-bit-interger organized</li><li>layout:<ul><li>"<code>CH\r\n</code>" (<code>0x32 0x48 0x0d 0x0a</code>)</li><li>unsigned int:
version (currently "<code>1</code>", shold be <code>==</code> compared)</li><li>
unsigned int: number of nodes (= n)</li><li>unsigned int: number of original edges
(= m<sub>1</sub>)</li><li>unsigned int: number of shortcut edges (= m<sub>2</sub>)</li><li>n times, for each
node 0..(n-1):<ul><li>unsigned int: level</li></ul>
</li><li>m<sub>1</sub> times, original edges:<ul><li>unsigned int: source node
</li><li>unsigned int: target node
</li><li>unsigned int: weight
</li><li>unsigned int: flags</li></ul>
</li><li>m<sub>2</sub> times, shortcut edges:<ul><li>unsigned int: source node
</li><li>unsigned int: target node
</li><li>unsigned int: weight
</li><li>unsigned int: flags
</li><li>unsigned int: shortcut middle node
</li></ul>
</li><li>unsigned int: <code>0x12345678</code> as terminator</li></ul>
</li><li>possible (bit) flags are:<ul><li><code>1</code> = forward edge</li><li><code>2</code> = backward edge</li><li>
<code>4</code> = shortcut edge</li><li>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.
</li></ul></li></ul><br><br><b>Few queries:</b><br><br>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? <br>
<br>2. The queries will be same like shortest_path() just that at backend the contraction hierarchies pre-processed data be used?<br><br>3. What should be the exact format for representing data for contraction hierarchies?<br>
<br><br></div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
</blockquote>
<br>
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)<br>
<br clear="all"></blockquote></div><br><br>-- <br>Regards,<br>-Jay Mahadeokar<br><br>