[graph-tool] Running all_shortest_path on large graph

Tiago de Paula Peixoto tiago at skewed.de
Tue Feb 6 13:32:24 CET 2018


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 at skewed.de>



More information about the graph-tool mailing list