Hi Jay,<div><br></div><div>Thank you for taking a look at the source code!</div><div>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:</div>
<div><ul><li><meta http-equiv="content-type" content="text/html; charset=utf-8"><a href="http://routingdemo.geofabrik.de/">http://routingdemo.geofabrik.de/</a></li><li><meta http-equiv="content-type" content="text/html; charset=utf-8"><a href="http://sourceforge.net/projects/routed/">http://sourceforge.net/projects/routed/</a></li>
</ul><div>It uses contraction hierarchies algorithm.</div><div><br></div><div>Regarding the license (AGPL) and the one of pgRouting (GPL) we probably need to make sure, that CH will become an optional component.</div><div>
<br></div><div>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.</div>
<div><br></div><div>@Anton ... did you catch this conversation?</div><div><br></div><div>Daniel</div><div><br></div><div><br></div><br><div class="gmail_quote">2011/2/17 Stephen Woodbridge <span dir="ltr"><<a href="mailto:woodbri@swoodbridge.com">woodbri@swoodbridge.com</a>></span><br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"><div class="im">On 2/16/2011 10:17 PM, Jay Mahadeokar wrote:<br>
</div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="im">
Hi,<br>
<br>
<br>
On Sat, Jan 29, 2011 at 6:13 AM, Stephen Woodbridge<br></div><div class="im">
<<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.com</a> <mailto:<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.com</a>>> wrote:<br>
<br>
*Source Code *(Quote from their web-page)<br>
<br>
/The source code of our implementation of contraction<br>
hierarchies (CHs)<br>
is now available under the terms of the AGPL. If you are<br>
interested in<br>
getting the source code write an email to Robert Geisberger<br>
<<a href="http://algo2.iti.kit.edu/english/geisberger.php" target="_blank">http://algo2.iti.kit.edu/english/geisberger.php</a>>.<br>
/<br>
<br>
<br>
I had requested Robert Geisberger for the source code of CH, and I went<br>
thru it (Grateful to him for making the source available under AGPL). It<br>
takes as input .ddsg files and produces contraction hierarchies in .ch<br>
file format.<br>
<br>
*.DDSG* *File Format:*<br>
<br>
* a /text/-file, whitespace-separated;<br>
* starts with single letter 'd';<br>
* followed by the number of nodes /n/ and the number of edges /m/<br>
* for each of the /m/ edges, we have<br></div>
o source node ID /s/, an unsigned 32-bit integer, 0 <= /s/ < /n/;<br>
o target node ID /t/, an unsigned 32-bit integer, 0 <= /t/ < /n/;<br>
o edge weight /w/, an unsigned 32-bit integer; note that the<div class="im"><br>
length of the longest shortest path must fit into a 32-bit<br>
integer<br></div>
o the direction /d/: //<div class="im"><br>
+ //0 = open in both directions //<br>
+ //1 = open only in forward direction (from /s/ to /t/) //<br>
+ //2 = open only in backward direction (from /t/ to /s/) //<br>
+ //3 = closed //<br>
//Note that specifying an edge (s,t,w,1) is equivalent to<br>
specifying an edge (t,s,w,2). It does not matter which form<br>
is used. In the current implementation, 3 is interpreted as<br>
0, i.e., closed roads are used in both directions. If you<br></div>
really want to completely close a road, just leave it away. //<br>
</blockquote>
<br>
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.<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
*CH File Format:*<div class="im"><br>
<br>
* a /binary/ file, 32-bit-interger organized<br>
* layout:<br></div>
o "|CH\r\n|" (|0x32 0x48 0x0d 0x0a|)<br>
o unsigned int: version (currently "|1|", shold be |==| compared)<br>
o unsigned int: number of nodes (= n)<br>
o unsigned int: number of original edges (= m_1 )<br>
o unsigned int: number of shortcut edges (= m_2 )<br>
o n times, for each node 0..(n-1):<br>
+ unsigned int: level<br>
o m_1 times, original edges:<div class="im"><br>
+ unsigned int: source node<br>
+ unsigned int: target node<br>
+ unsigned int: weight<br>
+ unsigned int: flags<br></div>
o m_2 times, shortcut edges:<div class="im"><br>
+ unsigned int: source node<br>
+ unsigned int: target node<br>
+ unsigned int: weight<br>
+ unsigned int: flags<br>
+ unsigned int: shortcut middle node<br></div>
o unsigned int: |0x12345678| as terminator<br>
* possible (bit) flags are:<br>
o |1| = forward edge<br>
o |2| = backward edge<br>
o |4| = shortcut edge<br>
o Note that not all edges of the original graph are listed as<div class="im"><br>
original edges. Edges that are not on any shortest path may<br>
be removed or replaced by shortcuts.<br>
</div></blockquote>
<br>
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.<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
*Few queries:*<div class="im"><br>
<br>
1. If pgRouting has to support the routing using contraction<br>
hierarchies, what exactly is the idea? The postgres database table like<br>
"ways" will be taken as input and the output would be another postgres<br>
database table that will include data in form of contraction hierarchies?<br>
</div></blockquote>
<br>
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.<br>
<br>
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.<div class="im">
<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
2. The queries will be same like shortest_path() just that at backend<br>
the contraction hierarchies pre-processed data be used?<br>
</blockquote>
<br></div>
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:<br>
<br>
Each of these represents a set of record:<br>
<br>
1. gid<br>
2. gid, cost<br>
3. gid, reversed, cost<br>
etc<br>
<br>
gid - unique edge id from the "ways" table<br>
cost - cumlative cost to get to the end of this segment along the path<br>
reversed - Y|N flag to indicate if traversed backwards or forwards<div class="im"><br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
3. What should be the exact format for representing data for contraction<br>
hierarchies?<br>
</blockquote>
<br></div>
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.<br>
<br>
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.<br>
<br>
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:<br>
<br>
select start_node from CH_pnt_to_node(start_point);<br>
select end_node from CH_pnt_to_node(end_point);<br>
select * from CH_solve("table", start_node, end_node);<br>
<br>
or something like that. Basically if there are helper function needed then that is appropriate.<br>
<br>
Best regards,<br>
-Steve<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="im">
<br>
Right, but there are also a few other implementations of the<br>
contraction hierarchies in the wild that might not be based on their<br>
code, like the MONAV implementation, which is released on GPLv3, and<br>
at least one person was looking at it in conjunction with Boost<br>
(google: contraction hierarchies boost)<br>
<br>
<br>
<br>
--<br>
Regards,<br>
-Jay Mahadeokar<br>
<br>
<br>
<br></div><div class="im">
_______________________________________________<br>
pgrouting-dev mailing list<br>
<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/mailman/listinfo/pgrouting-dev</a><br>
</div></blockquote><div><div></div><div class="h5">
<br>
_______________________________________________<br>
pgrouting-dev mailing list<br>
<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/mailman/listinfo/pgrouting-dev</a><br>
</div></div></blockquote></div><br><br clear="all"><br>-- <br><span style="font-family:arial, sans-serif;font-size:13px;border-collapse:collapse">Georepublic UG & Georepublic Japan<br>eMail: <a href="mailto:daniel.kastl@georepublic.de" style="color:rgb(66, 99, 171)" target="_blank">daniel.kastl@georepublic.de</a><br>
Web: <a href="http://georepublic.de/" style="color:rgb(66, 99, 171)" target="_blank">http://georepublic.de</a></span><br>
</div>