Distance map returned from shortest_distance function misses entries of certain vertices
Maybe someone can help me out with this problem I posted on StackOverFlow: https://stackoverflow.com/questions/61955566/distance-map-returned-from-shor... Basically, I discovered that a call to shortest_distance returns a distance map where certain node entries are missing (I need 349, I only get 328). Weird thing is that some of the missing nodes are intermediaries for other nodes that *are* present in the distance map. The link contains a MWE, which I tested on an older py2 setup, as well as an up-to-date Docker container. Results are the same. Would be very grateful for a solution, because I need to be certain about results correctness before I can proceed with this (very fast!) library. -- Sent from: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/
Anyone that can help me out ? There must be something I'm missing, or there must be an easy fix. Any help would be greatly appreciated. -- Sent from: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/
Am 03.06.20 um 10:26 schrieb Mathias Versichele:
Anyone that can help me out ? There must be something I'm missing, or there must be an easy fix. Any help would be greatly appreciated.
This is a numerical precision problem. You have very low edge weights (1e-6) combined with very large values (1000000), which cause differences to be lost to finite precision. If you replace all values 1000000 (which I assume mean infinite weight) by numpy.inf, you actually get a more stable calculation, and no missing nodes in your example. An even better alternative is to actually remove the "infinite weight" edges using an edge filter. Best, Tiago Ps. I note you are using Python 2, but current versions of graph-tool only support Python 3. -- Tiago de Paula Peixoto <tiago@skewed.de>
Awesome. Thanks for that. One question though. Apart from the edge filter which will make Dijkstra calculation faster, can I also get around storing lots of Inf values in an edgepropertymap ? Suppose, I only want to route along highways. Right now, I would have an edgepropertymap with 98% inf values (all roads lower than highway), which is wasted memory. -- Sent from: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/
participants (2)
-
Mathias Versichele -
Tiago de Paula Peixoto