shortest_distance anomalies?

graph-tool
1

I am trying to run the shortest_path function on various nodes on a graph.

I am using a starting vertex, and returning all vertices within a certain threshold distance. The edges are weighted by a distance metric.

My dilemma is that it works as intended except for some nodes. All I can think of is that the problematic edges have an edge that exceeds the threshold distance, in which case it is returning only one edge, instead of all edges that are less than the threshold distance.

Is it possible that once the algorithm reaches an edge that exceeds the cutoff distance, that it stops then-and-there, instead of searching the remaining vertices?

I am attaching my python file and the graph file that I’m testing this on.

- The file prints information about two test vertices to the console, one of a working vertex (A) and the other of a vertex (B) that doesn’t work as anticipated. (I can’t see anything suspiciously different between them.)

- It also plots three copies of the graph:
A) filtered graph of vertex (A);
B) filtered graph of vertex (B);
C) non-filtered copy of the entire graph showing index numbers and weights

Thanks.

Plaza.xml.gz (5.48 KB)

shortestDistanceTest.py (2.35 KB)

2

Yes, this is indeed a bug! This works fine for DFS, but for Dijkstra it
gives the wrong result.

I have just corrected this in the git version. Could you please try it
and see if it is working as expected for you?

Thanks for spotting this and for the working example.

Best,
Tiago

3

Thanks Tiago.

A quick question as a newb to Linux: If I install from git onto Ubuntu using pip, then would this in anyway conflict with the graph-tool version installed via Ubuntu’s apt-get?

Thanks,
Gareth

4

You can't install from git using pip. You have to run ./autogen.sh and
then ./configure, make, make install. And yes, if you do that it will
overwrite the version installed via apt-get.

If compiling from source is too cumbersome for you, you can just wait
until the next version is released.

Best,
Tiago

5

Hi Tiago, do you have a rough timeline till the next version? Thanks.

6

No. I want to do it ASAP, but I need to get some other things finished
first.

Best,
Tiago

7

Hi Tiago, managed to install and it now works as intended. Thanks.