Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Show HN: Dijkstra’s algorithm in the web browser with OpenStreetMap

christophercliff.com

Post reply on HN
Print view View original

31–37 of 37 posts

Re: Show HN: Dijkstra’s algorithm in the web browser with OpenStreetMap

#31

Post by amelius »

lorenzhs wrote: post #28
amelius wrote: post #26

Earlier quoted context omitted.

> but the pre-processing time is very long Could you elaborate on why the preprocessing time is long? I didn't study contraction hierarchies, but to me it seems that computing shortcuts in a planar graph is the perfect fit for a divide-and-conquer approach.

You want the shortcuts to be long, so you can't just recursively divide the graph. The Wikipedia article does a fairly good job of explaining CH: https://en.wikipedia.org/wiki/Contraction_hierarchies

Well, intuitively, I'd say you could divide the graph in two parts (along a cut). Then compute the CH-extended graph for both of the parts. And then combine those two graphs into the CH-extended graph for the whole graph. And you do this recursively, alternating the direction of the cut. This way, it is also easy to parallelize.

Re: Show HN: Dijkstra’s algorithm in the web browser with OpenStreetMap

#32

Post by adrianN »

amelius wrote: post #31
lorenzhs wrote: post #28

Earlier quoted context omitted.

You want the shortcuts to be long, so you can't just recursively divide the graph. The Wikipedia article does a fairly good job of explaining CH: https://en.wikipedia.org/wiki/Contraction_hierarchies

Well, intuitively, I'd say you could divide the graph in two parts (along a cut). Then compute the CH-extended graph for both of the parts. And then combine those two graphs into the CH-extended graph for the whole graph. And you do this recursively, alternating the direction of the cut. This way, it is also easy to parallelize.

You might be interested in this paper https://arxiv.org/abs/1302.5611

Re: Show HN: Dijkstra’s algorithm in the web browser with OpenStreetMap

#33

Post by lorenzhs »

amelius wrote: post #31
lorenzhs wrote: post #28

Earlier quoted context omitted.

You want the shortcuts to be long, so you can't just recursively divide the graph. The Wikipedia article does a fairly good job of explaining CH: https://en.wikipedia.org/wiki/Contraction_hierarchies

Well, intuitively, I'd say you could divide the graph in two parts (along a cut). Then compute the CH-extended graph for both of the parts. And then combine those two graphs into the CH-extended graph for the whole graph. And you do this recursively, alternating the direction of the cut. This way, it is also easy to parallelize.

Not sure it's that easy. But parallel CH preprocessing has been done already, by finding sets of nodes that can be contracted independently (similar to your idea): http://algo2.iti.kit.edu/download/vetter_sa.pdf - the speedup wasn't too bad. Also, https://arxiv.org/abs/1208.2543

Re: Show HN: Dijkstra’s algorithm in the web browser with OpenStreetMap

#34

Post by lorenzhs »

adrianN wrote: post #32
amelius wrote: post #31

Earlier quoted context omitted.

Well, intuitively, I'd say you could divide the graph in two parts (along a cut). Then compute the CH-extended graph for both of the parts. And then combine those two graphs into the CH-extended graph for the whole graph. And you do this recursively, alternating the direction of the cut. This way, it is also easy to parallelize.

You might be interested in this paper https://arxiv.org/abs/1302.5611

That's a different speedup technique, though - Transit Node Routing works quite differently from Contraction Hierarchies.

Edit: it seems like the paper you linked uses a technique for parallelizing CH construction that I mentioned in my other comment, https://news.ycombinator.com/item?id=12642961

Re: Show HN: Dijkstra’s algorithm in the web browser with OpenStreetMap

#35

Post by liotier »

EllipticCurve wrote: post #29
liotier wrote: post #25

I thought that Dijkstra required rasterization... But here it appears that it works with graph... Is there something I have missed ?

What would you need rasterization for? Dijkstra works fine on arbitrary graphs with non-negative edges!

Ok, I'll go read a few papers... I'm guessing I misled myself because I needed routing across open spaces around obstacles and that required rasterization - made me forget that the graph routing works just fine.

Re: Show HN: Dijkstra’s algorithm in the web browser with OpenStreetMap

#36

Post by danpat »

amelius wrote: post #31
lorenzhs wrote: post #28

Earlier quoted context omitted.

You want the shortcuts to be long, so you can't just recursively divide the graph. The Wikipedia article does a fairly good job of explaining CH: https://en.wikipedia.org/wiki/Contraction_hierarchies

Well, intuitively, I'd say you could divide the graph in two parts (along a cut). Then compute the CH-extended graph for both of the parts. And then combine those two graphs into the CH-extended graph for the whole graph. And you do this recursively, alternating the direction of the cut. This way, it is also easy to parallelize.

The difficulty is that the performance of queries on the final graph is dependent on it's shape. As lorenzhs said, you want the shortcuts to be as long as possible.

The final shape of the graph is highly dependent on the order you contract the nodes in - small changes in contraction order have large effects on the final shape.

One of the very expensive parts of the pre-processing step is determining the best order to perform contraction. Sure, you could just iterate over all nodes, contracting as you go (and parallelize), but you'd end up with a contracted graph that's not a whole lot better for queries than the original. Order matters.

The original CH paper covers lots of the details:

http://algo2.iti.kit.edu/documents/routeplanning/geisberger_...

There is a general group of approaches that do what you're describing - partition the graph recursively, and produce optimized overlays in various forms. This can be done in parallel, and recursively:

http://www.dis.uniroma1.it/challenge9/papers/holzer.pdf

Query performance is generally not quite as fast as a well-optimizied CH graph, but the overlays can be generated much faster and that work can be highly parallelized. We hope one day to get a chance to implement this approach in OSRM.

The difficult problem with the second approach is partitioning the graph well :-)

Post reply on HN