Distance map returned from shortest_distance function misses entries of certain vertices

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

Distance map returned from shortest_distance function misses entries of certain vertices

Mathias Versichele
Maybe someone can help me out with this problem I posted on StackOverFlow:
https://stackoverflow.com/questions/61955566/distance-map-returned-from-shortest-distance-function-misses-entries-of-certain

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/
_______________________________________________
graph-tool mailing list
[hidden email]
https://lists.skewed.de/mailman/listinfo/graph-tool
Reply | Threaded
Open this post in threaded view
|

Re: Distance map returned from shortest_distance function misses entries of certain vertices

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.



--
Sent from: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/
_______________________________________________
graph-tool mailing list
[hidden email]
https://lists.skewed.de/mailman/listinfo/graph-tool
Reply | Threaded
Open this post in threaded view
|

Re: Distance map returned from shortest_distance function misses entries of certain vertices

Tiago Peixoto
Administrator
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 <[hidden email]>


_______________________________________________
graph-tool mailing list
[hidden email]
https://lists.skewed.de/mailman/listinfo/graph-tool

signature.asc (849 bytes) Download Attachment
--
Tiago de Paula Peixoto <tiago@skewed.de>
Reply | Threaded
Open this post in threaded view
|

Re: Distance map returned from shortest_distance function misses entries of certain vertices

Mathias Versichele
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/
_______________________________________________
graph-tool mailing list
[hidden email]
https://lists.skewed.de/mailman/listinfo/graph-tool