DijkstraOneToMany with elevation? / GraphHopper.route(…) using DijkstraOneToMany?

tl;dr

Is there a way to make DijkstraOneToMany factor in elevation? Alternatively, even preferred: Can I configure GraphHopper so GraphHopper.route(…) uses DijkstraOneToMany (or something as fast) internally?

Background

Given a starting location and a set of end locations on a map, I want to quickly calculate which ones are how far away (and how costly to reach). I found that:

val hopper: GraphHopper = …
val req = new GHRequest(…).setProfile("bike")
hopper.route(req)

Gives seemingly good results that I assume factor in elevation. Indeed, I can query the resulting Paths for ascend meters.

The Problem

However, using DijkstraOneToMany is much, much faster than using above API. Unfortunately the results it returns do not seem to factor in elevation. They differ greatly from the ones the above code produces:

val graphPlus = QueryGraph.create(graph, tileSnapsAndStartSnap.toList.asJava)
val weighting = new FastestWeighting(graph.getEncodingManager().getEncoder("bike2"))
val dij = new DijkstraOneToMany(graphPlus, weighting, TraversalMode.NODE_BASED)

I am using FastestWeighting, maybe there’s a different weighting that takes elevation into account?

On a sidenote

In my case, DijkstraOneToMany also returns odd results that still need more investigating. E.g., the costliest result having a distance of 0 (!) and a cost / weight of
179769313486231570000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000.

1 Like

I’m not sure if this is a typo, but the only profile that factors in elevation is bike2. You wrote setProfile("bike"), but in your DijkstraOneToMany example you actually use bike2.

What do you mean?

It is faster for two (or three reasons): 1) It builds one search tree for all end locations, instead of one search tree for each end location. 2) It allocates memory for every node of the graph instead of using hash maps to represent the shortest path tree and (maybe) 3) You were using bike2 while you used bike for the single route requests.

There is no reason DijkstraOneToMany would not factor in elevation while the other algorithms do. I think you must be missing something here.

So far there is no such weighting. Elevation is only handled by adjusting the speeds via the bike2 encoder. This is something I’d like to improve in the future though.

Ok, let us know if you figure out what’s wrong, or otherwise share your code so we can have a look.

In my actual code it’s a constant that’s used in both places. So, yes, it’s a typo. Good catch!

I see! That is certainly good to know! I’d have hoped that mtb would as well. I mean, mountain is literally in the name :grin:. But I suppose that profile was there before support for elevation was added?

Exactly! That’s why I was really excited when I saw there’s an implementation of Dijkstra built in that I can use directly.

The GH router uses hash maps for that? Interesting!

OK good. Indeed, you provided a clue:

I see. I’ve only been looking at what getWeight() (in the case of DijkstraOneToMany) and getRouteWeight() (in the GraphHopper Router case) returned. If that doesn’t factor in speed then that might be the reason.

I am referring to .getAscend() IIRC. That’s only available on the result returned by the GraphHopper routing (in contrast to the routing done by DijkstraOneToMany).

I can’t make the GraphHopper routing use DijkstraOneToMany under the hood, can I?

Yes, this is definitely something that should be improved.

Yes. The approach taken in DijkstraOneToMany does not work so well in a multi-threaded/server environment, because every request requires memory that is proportional to the size of the map (might be ok for city maps, but certainly not for planet OSM) using hash maps.

It normally does factor in speed, unless you were using ShortestWeighting for example.

getAscend() only returns the elevation gain for a given route after it was calculated. It does not mean the route was optimized to e.g. minimize the elevation gain. You can do that for every route no matter which algorithm was used to calculate it. All you need to do is take the route’s point list and sum over the elevation differences (or use the code that does this in PathMerger.java).

There is no config setting that does this, but it should not be hard to tweak the code accordingly.

Nope, I’m definitely using FastestWeighting.

I see, thanks! I understand the relation between Path and ResponsePath better now. The latter is (more or less) the sum of multiple Paths and you can “upgrade” (= merge) a Path (= a list containing this one Path) to a ResponsePath using PathMerger. After which you can then conveniently ask for the change in elevation.
I am tempted to think of ResponsePath as a “route”. A final routing result that is meant to be presented to the user whereas a mere Path is more of a low level construct from the bowels of the library.

I see. However, turning Paths into ResponsePaths after the fact might be easier and should yield the same results. That is, if my DijkstraOneToMany approach stopped handing out such weird results. Trying to turn those into ResponsePaths got me this:

java.lang.IllegalStateException: Edge 4413726 not found with adjNode:3470593. found edges were:321500->3470594, 3470594->321500

Now I can either spend time and try to figure out the underlying problem or I bite the bullet and just use the slow HashMap based routing and leave that problem for future me if it ever will be too slow. For now I can get away with a bit of patience and running it in multiple threads. After all, this is just for a silly pet project of mine.

Yes, that is quite accurate. The Path is the result of the low-level algorithms and the ResponsePath is the result of our post-processing of the Path (like accumulating elevation gain). PathMerger is not the greatest name btw. And yes at some point we actually discussed calling ResponsePath just Route. (It was called PathWrapper before…: https://github.com/graphhopper/graphhopper/issues/1147#issuecomment-461537225)

Ok that could be a bug. Historically, DijkstraOneToMany was not primarily written to calculate Paths (as weird as this might sound), but rather to calculate weights (during CH preparation). So maybe it was never used to create ResponsePaths… If you can share some code that reproduces this error I can take a look.

Note that the HashMap approach is slower, but that is not the main reason DijkstraOneToMany is faster. The main reason is that only one search tree is built. You could e.g. easily modify Dijkstra.java to search for multiple end locations, or use ShortestPathTree.java to do the same.

That is the easiest thing you can do, yes. :smiley:

Alright, found some more time to work on this.

I am running DijkstraOneToMany on a QueryGraph. Might that be the problem? If I call .calcPoints() on a returned Path it crashes stating that java.lang.IllegalStateException: Edge soandso not found with adjNode:foobar. found edges were:meep->bla, whatnot->thing

Indeed, if I print whether the edges in the path exist:

def edgeExistsIn(graph: GraphHopperStorage)(e: Int) = {
  e < graph.getEdges()
}
val dbg = paths.map(p => p.getEdges().asScala.map(_.value).map(edgeExistsIn(graph))).toSeq
println(dbg)

I get output such as:

List(ArrayBuffer(false), ArrayBuffer(false, false, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, false), ArrayBuffer(false, false, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, false), ArrayBuffer(false, false, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, false))

Indicating that at the start and end of the paths found are edges that don’t exist in the actual data. AKA, virtual edges. Those have IDs larger than what is returned by GraphHopperStorage#getEdges(), right?

Is DijkstraOneToMany not supposed to be used with QueryGraphs? Do I have to use a different API? The HashMap based one works fine, I suppose it takes care of the virtual bits in the Path. Do I have to manually filter out all virtual edges and nodes from the paths? Is there a ready made method for this? Thanks!

Addendum:

If I filter out aforementioned edges:

def cleanPath(p: Path): Path = {
  val realPath = new Path(graph)
  val realEdges = p.getEdges().asScala.map(_.value).filter(edgeExistsIn(graph))
  realEdges.foreach(realPath.addEdge)
  realPath
}

and then run .calcPoints() on those supposedly real paths, I get:

[error] (run-main-19) java.lang.IllegalStateException: fromNode < 0 should not happen
[error] java.lang.IllegalStateException: fromNode < 0 should not happen
[error]         at com.graphhopper.routing.Path.getFromNode(Path.java:105)
[error]         at com.graphhopper.routing.Path.calcPoints(Path.java:281)
[error]         at io.doerfler.TilesHopperMain$.$anonfun$main$55(TilesHopperMain.scala:277)

Guess, I have to set to fromNode manually. fwiw, I first tried copying the virtual path’s fromNode:

val fromNodeF = classOf[Path].getDeclaredField("fromNode")
fromNodeF.setAccessible(true)
val fromNode = fromNodeF.get(virtualPath).asInstanceOf[Int]
realPath.setFromNode(fromNode)

Having to use reflection is, of course, a strong indicator that I’m rubbing the cat the wrong way. There just has to be an easier way to do this.

As expected, this only got me an exception saying the node was out of bounds. Of course, the fromNode might as well be a virtual node, too.
So, I now set the fromNode to the base node of the first actual edge if there is any real edge left in the path. Some paths consist just of virtual edges. So, finally:

def cleanPath(p: Path): Option[Path] = {
  val realPath = new Path(graph)
  val realEdges = p.getEdges().asScala.map(_.value).filter(edgeExistsIn(graph)).toSeq
  realEdges.foreach(realPath.addEdge)
  for {
    fe   <- realEdges.headOption
    feis  = upgrade(fe)
    bn    = feis.getBaseNode
    _     = realPath.setFromNode(bn)
  } yield realPath
}

(and:)

def upgrade(e: Int): EdgeIteratorState =
  graph.getEdgeIteratorState(e, Integer.MIN_VALUE)

gives me actual, real paths based on the virtual ones found by DijkstraOneToMany used with a QueryGraph that I can turn into a PointList and dump in a gpx file for viewing.

right

Kind of yes. You might be the first to try this. See my comment above.

Probably yes, but I haven’t seen your code so I don’t know whats wrong.

No, I don’t think there is/should be code that explicitly handles virtual edges.

That could be a possible workaround, but probably not necessary if you fix the code that causes the problem.

No, I don’t think so.

Ah, I was updating my question with more code and what, so far, appears to be a working solution while you wrote your answer. Maybe this explains things a bit? If I find the time I want to clean up my code a bit and make a minimal example that shows the possible bug or my wrong use of Graphhopper.

Ok, I see. The problem is probably in DijkstraOneToMany#extractPath. Compare this to Dijkstra#extractPath. We should start with a unit test that: Sets up a graph and a query graph, then runs a query using DijkstraOneToMany and produces your error when we call path.calcPoints().

I took a brief look at your cleanPath code and this is probably what you need to do before the actual issue is fixed, at least I do not have a better idea.

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.