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.

Thanks in advance for the help,

Vaggelis

!image.png|498x511

import gi

import numpy as np

gi.require_version('Gtk', '3.0')

from graph_tool.all import *

import graph_tool as gt

from graph_tool.topology import *

import tqdm

import math

g = gt.Graph(directed=True)

dict_v_name_to_v = {}

g.vertex_properties["name"] = g.new_vertex_property("string")

g.vertex_properties["pos"] = g.new_vertex_property("vector<float>")

g.edge_properties["name"] = g.new_edge_property("string") # name

of edge, if any comes from csf

g.edge_properties["text"] = g.new_edge_property("string") # name

of edge, if any comes from csf

g.edge_properties["elev_gain"] = g.new_edge_property("double") #

name of edge, if any comes from csf

vp = g.vertex_properties

ep = g.edge_properties

N_LON=5

N_LAT=5

# Vertices

print("\r\nCreating Vertices")

for i in range(0, N_LAT):

for j in range(0, N_LON):

v = g.add_vertex()

v_name = str(i) + '_' + str(j)

dict_v_name_to_v[v_name] = v

vp["name"][v] = v_name

vp['pos'][v] = [float(j), float(i)]

# Edges

print("\r\nCreating Edges")

for j in range(1, N_LON - 1): # long

jm1 = j - 1

jp1 = j + 1

for i in range(1, N_LAT - 1): # lat

ip1 = i + 1

im1 = i - 1

im1_s, i_s, ip1_s = [str(el) for el in (im1, i, ip1)]

jm1_s, j_s, jp1_s = [str(el) for el in (jm1, j, jp1)]

v_i_jm1 = dict_v_name_to_v['_'.join([i_s, jm1_s])]

v_i_j = dict_v_name_to_v['_'.join([i_s, j_s])]

v_i_jp1 = dict_v_name_to_v['_'.join([i_s, jp1_s])]

v_ip1_jm1 = dict_v_name_to_v['_'.join([ip1_s, jm1_s])]

v_ip1_j = dict_v_name_to_v['_'.join([ip1_s, j_s])]

v_ip1_jp1 = dict_v_name_to_v['_'.join([ip1_s, jp1_s])]

v_im1_jm1 = dict_v_name_to_v['_'.join([im1_s, jm1_s])]

v_im1_j = dict_v_name_to_v['_'.join([im1_s, j_s])]

v_im1_jp1 = dict_v_name_to_v['_'.join([im1_s, jp1_s])]

e_i_jm1 = g.add_edge(v_i_j, v_i_jm1)

e_i_jp1 = g.add_edge(v_i_j, v_i_jp1)

e_ip1_jm1 = g.add_edge(v_i_j, v_ip1_jm1)

e_ip1_j = g.add_edge(v_i_j, v_ip1_j)

e_ip1_jp1 = g.add_edge(v_i_j, v_ip1_jp1)

e_im1_jm1 = g.add_edge(v_i_j, v_im1_jm1)

e_im1_j = g.add_edge(v_i_j, v_im1_j)

e_im1_jp1 = g.add_edge(v_i_j, v_im1_jp1)

ep["elev_gain"].a = 1

for e in g.edges():

ep["text"][e] = str(ep["elev_gain"][e]) # name of edge, if any

comes from csf

graph_draw(g,

pos=g.vertex_properties['pos'],

vertex_text=g.vertex_properties["name"],

edge_text=ep["text"],

update_layout=False)

v_start = dict_v_name_to_v['3_1']

v_dest = dict_v_name_to_v['1_3']

attachment.html (10.8 KB)