On 26.01.2018 18:55, Evangelos Petsalis wrote:
Tiago,
I start to believe that the error is not related to the size of the graph but rather to the epsilon parameter that is passed to the function all_shortest_paths(). Based on the documentation the epsilon parameter is defined as "Maximum relative difference between distances to be considered equal". I want to compute not only the best path but also paths that are "fairly" close to the best one, so I set epsilon=5 to have the function return multiple "best paths". This messes up the function it either creates a segmentation error, or it crashes the whole virtual machine.
The following code creates a 5x5 graph where each edge that does not lie to the periphery of the square is connected to all neighboring edges with a weight of 1. The best path from vertex "3_1" to "1_2" is obvious the diagonal path which has a weight of 2. I was expecting that by setting epsilon=5, other paths would also be returned, for example (3_1, 3_2, 2_2, 1_2) that has weight of 4. Instead, the function crashes and returns the following error: Traceback (most recent call last): File "<input>", line 3, in <module> File "/home/labuser/anaconda3/envs/py35/lib/python3.5/site-packages/graph_tool/topology/__init__.py", line 1978, in all_shortest_paths _prop("v", g, all_preds_map)) MemoryError
I probably misuse the epsilon parameter, but is there a way to achieve what I described above? The source code that recreates the problem can be found at the end of the email.
I am using version 2.26 on an Ubuntu 17.10 virtual machine.
Sorry for taking so long to reply. Indeed, you are not supposed to use the epsilon parameters in this way... If it is too large, it adds loops to the shortest path tree, creating an infinite loop in the algorithm. The only way to achieve what you want is to use all_paths() instead, and filter the length range you want. Best, Tiago -- Tiago de Paula Peixoto <tiago@skewed.de>