graph_tool.topology.shortest_distance() - Confusing documentation or possible bug in return_reached; wrong documentation
Hello everyone,
In the "shortest_distance" routine there is the option to return an array with the reached vertices by setting the flag/attribute "return_reached" to True. While using this routine, having set the max_dist, I have found that in the returned array not only are included the vertices in fact reached within the max_dist limit, but also some neighbouring vertices that probably were visited during the Dijkstra steps but exceeded the limit. I believe this behaviour is confusing and it may lead to erratic code/bugs for those who are not expecting it. I propose either:
1. Change the routine as to return only the vertices that are in fact reached within max_dist; 2. Change this flag to something like "return_visited", as to hint that the returned vertices may not in fact be reached within the expected distance limit; 3. Add a warning in the documentation regarding this behaviour.
Regarding the same method but on another subject, I believe there is an error in the documentation, namely on the return variables. There we can see two optional return values named "pred_map", while in fact one of them is the reached-vertices array mentioned above. Having the same name one may think that it might actually be a exclusive OR return where only either one is returned and it is just an matter of weird naming.
I may try to implement one of the changes above, if it is decided so, but the access to the GitLab repo through GitHub account linking has not been accepted by the admin yet.
JA
Dear João,
Am 02.02.22 um 14:31 schrieb João Aveiro:
Hello everyone,
In the "shortest_distance" routine there is the option to return an array with the reached vertices by setting the flag/attribute "return_reached" to True. While using this routine, having set the max_dist, I have found that in the returned array not only are included the vertices in fact reached within the max_dist limit, but also some neighbouring vertices that probably were visited during the Dijkstra steps but exceeded the limit. I believe this behaviour is confusing and it may lead to erratic code/bugs for those who are not expecting it. I propose either:
- Change the routine as to return only the vertices that are in fact reached within max_dist;
- Change this flag to something like "return_visited", as to hint that the returned vertices may not in fact be reached within the expected distance limit;
- Add a warning in the documentation regarding this behaviour.
The usual procedure when reporting bugs is to provide a minimal working example that shows the problem. Otherwise we have to hunt blindly for an instance of the behavior you are reporting.
Can you please provide a minimal example?
Regarding the same method but on another subject, I believe there is an error in the documentation, namely on the return variables. There we can see two optional return values named "pred_map", while in fact one of them is the reached-vertices array mentioned above. Having the same name one may think that it might actually be a exclusive OR return where only either one is returned and it is just an matter of weird naming.
This is indeed a bug in the documentation, and will be fixed. (Could you please open an issue in gitlab so that it is not forgotten?)
I may try to implement one of the changes above, if it is decided so, but the access to the GitLab repo through GitHub account linking has not been accepted by the admin yet.
I have approved your account.
If you could open an issue for each bug with a minimal working example that would be appreciated.
Best, Tiago
Hello Tiago,
Thanks for the quick reply . I don't have time for opening the issues right now, but I'll try to do so later today or tomorrow. Regardless, below you'll find a minimal example for the first issue I mentioned, for if you want to try it in the meantime.
Best regards, JA
_
from graph_tool import Graph from graph_tool.topology import shortest_distance
if __name__ == '__main__': """In this example we have a 4 vertices/ 3 edges graph with the following topology:
(2) <----- (1) ----> (3) ----> (4)
where each edge has weight=5. Shortest distance is calculated from vertex (1). """
# Create graphs g = Graph(directed=True)
# Add vertices g.add_vertex() g.add_vertex() g.add_vertex() g.add_vertex()
# Edge weight property w = g.new_edge_property("float")
# Add edges e1 = g.add_edge(1, 2) w[e1] = 5 e2 = g.add_edge(1, 3) w[e2] = 5 e3 = g.add_edge(3, 4) w[e3] = 5
# Tests:
# Case 1: max_dist = 1, so only the source should be reached. dist, reached = shortest_distance(g, source=g.vertex(1), weights=w, max_dist=1, return_reached=True) print(f"\nCase 1 (source=1, max_dist=1): \n\t- Reached: {reached}\n\t- Dist.: {dist.a}") # Result: reached has vertex 1 (the only reached), but also the neighbours 2 and 3 which have dist == inf
# Case 2: max_dist = 6, so 1,2,3 should be reached but not 4 dist, reached = shortest_distance(g, source=g.vertex(1), weights=w, max_dist=6, return_reached=True) print(f"\nCase 2 (source=1, max_dist=6): \n\t- Reached: {reached}\n\t- Dist.: {dist.a}") # Result: reached has all vertices, despite 1 -> 4 having total distance of 10 (path 1 -> 3 -> 4, two edges with w=5)
-
João Aveiro -
Tiago de Paula Peixoto