Node based vs Edge based graph representation
Adrian Ster
I'm working for a company who offer navigation solutions on the market
and we tried to switch our routing solution from an heuristic
algorithm to CH. The first approach was a node based solution who
looked very promising in query time & database size ( e.g. for Germany
we had ~150 Mb for car & pedestrian search trees and a ~50 ms query
time with a very reasonable memory consumption < 2Mb ). Then came the
second step, switching to an edge based solution to support turn costs
( the approach was different from one proposed to have a node for each
road direction but only one node / road ). This solution has a ~450 Mb
database and ~500 ms query time, which is unacceptable for our
targets. As I see the contraction in the edge based graph introduce a
large amount of shortcuts, many of them useless, decreasing
dramatically the performances. We study your document on
http://algo2.iti.kit.edu/download/turn_ch.pdf but there are a lot of
things which need a more detailed explanation there. When do you think
of having the hybrid solution described in the article in the Monav
project ?
Christian Vetter
The code used to obtain test data for the paper you mentioned is
already in the repository, take a look at the turn-contract branch.
Keep in mind though, that it's prototype code without integration into
MoNav's mobile data structure, i.e. the queries are computed in-memory
directly after the contraction.
About using edge-based graphs for Contraction Hierarchies:
I've used Contraction Hierarchies on a normal edge-based
representation of a graph ( one node per original edge + direction )
and it should work out quite fine. The data size will increase by a
factor 3, similar to the amount you see.
From you email I gather you are trying a mobile ( external memory )
implementation?
What part of the query is unacceptable for you, data size or query
time? To reduce the data size you'd have to switch to the node based
implementation mentioned in the paper. However, it is not free from
draw backs, e.g. if you forbid all U-turns it will affect performance,
which it usually does not as much in an edge-based version.
If you have problems with your query times it could be one of the following:
- Node priority / parallel contraction / independent node sets
- Witness search ( especially if you get useless shortcuts? normally
you should only see about 1-3% useless shortcuts )
- Mobile data structure / node order
- Pre-unpacked path
However without knowing the details of your solution its hard to guess
what went wrong
Also: Having an edge-based graph, but using only one node per road
element instead of one per road element and direction means that you
most likely do not / cannot forbid U-Turns? This can create some ugly
/ undesired routes when turn restrictions are involved.
PS: If you intent to to distribute you software under a license
different from GPL, it might be a bad idea to look at MoNav's code for
inspiration. In that case you would not have a "clean room design" and
would have to take greater care to avoid copyright infringement.
However, I will try my best to answer your questions.
Regards,
Christian Vetter