On 2/18/2011 3:53 PM, Jay Mahadeokar wrote:
Hi Anton,
On Fri, Feb 18, 2011 at 6:27 PM, Daniel Kastl <daniel@georepublic.de
<mailto:daniel@georepublic.de>> wrote:
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.
Thanks for the links. Are you certain that the above project uses
contraction hierarchies algorithm by Robert Geisberger? I went thru the
source, and they are using contraction, but I did not see where they
have used the node ordering step as proposed in the CH paper. I did not
find contraction hierarchies mentioned in their readme too:
http://sourceforge.net/apps/trac/routed/wiki/ReadMe
It is possible that they read the paper and made their own implementation to avoid the AGPL license. The paper is describes the algorithms in great detail, so I'm sure this is possible.
Anyways, they are using osm file as input and the output consists of two
files 'file.osrm' and 'file.osrm.names'. Which is again preprocessed to
generate file.osrm.hsgr' 'file.osrm.nodes' which are then used for
answering queries.
Again, a method to keep the data pre-processed in order to speed up
dijekstra.
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.
I agree. So, basically if we want to add CH to pgRouting we will need
following components:
*
Preprocessing*
Tool like osmtopgrouting_CH that would preprocess the osm files to
postgres tables.
I think we need a general tool that can extract data from postgis tables into the CH preprocessor. There are a lot of people that are not using OSM data.
If we are using the code already made available thru AGPL (I dont
understand the intricacies of different licences) by Robert
I think we need to read and understand the AGPL license and how it might impact on the current license. These are tricky issues and it might prohibit us from including their code directly.
If we wanted to do that we could still use the AGPL code to build test model that would allow us to validate the our code was getting reasonable results.
Geisberger, then we can first have following:
A. Module that converts osm data to ddsg files.
B. Use the above code to convert ddsg files into .ch(contraction
hierarchy) files
C. Convert the .ch file into postgres_ch database table.
This seems like a reasonable approach to start with. We might eventually want to replace step A. with a stored procedure that does this step in the database, but that would be more complicated and require re-factoring the Geisberger code or designing and coding a new module that does the same thing which might get around the licensing issues.
*Quering*
If you look at the CH algorithm, the main idea is to add shortcut edges
using node ordering such that the overall new edges added justify the
extra space used in terms of speed-up gained.
The .ch file produced retains original edges, but also contains the
added short-cut edges. Now, suppose we have converted this info into
postgres table. According to my intuition, the original shortest path
query should readily work on this table data and provide considerable
speed up due to shortcuts.
Obviously, you need to be able to reconstruct the original path that the short-cut edge represented.
The CH paper also talks about various refinements in the shortest path
algo which will enhance the speed even more. Techniques include the
concept of searching on Upward and Downward graphs, pruning search space
using stall-on-demand technique etc. (I have just had an overview and
not understood the techniques in complete detail for now)
Sounds like more good stuff that needs to be understood. I read the paper about a year ago, so it is not fresh in my mind, so I guess I need to make some time to re-read it.
So, this can be a completely different module :
Shortest path query on the CH preprocessed table using the speed-up
techniques mentioned in CH paper.
I tried to put forward my understanding of the problem. Need to take a
deeper look into source code as well as paper before the above points
can be confirmed.
Sounds like you have made a great start already, keep up the good work on this.
Best regards,
-Steve
@Anton ... did you catch this conversation?
Daniel
2011/2/17 Stephen Woodbridge <woodbri@swoodbridge.com
<mailto:woodbri@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@swoodbridge.com <mailto:woodbri@swoodbridge.com>
<mailto:woodbri@swoodbridge.com
<mailto:woodbri@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/;Quering
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@lists.osgeo.org
<mailto:pgrouting-dev@lists.osgeo.org>
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org <mailto:pgrouting-dev@lists.osgeo.org>
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
--
Georepublic UG & Georepublic Japan
eMail: daniel.kastl@georepublic.de <mailto:daniel.kastl@georepublic.de>
Web: http://georepublic.de/>
_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org <mailto:pgrouting-dev@lists.osgeo.org>
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
--
Regards,
-Jay Mahadeokar
_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
