Tiago,
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
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']
#############################
# epsilon=0.0005 WORKS FINE
#############################
all_paths = all_shortest_paths(g, v_start, v_dest, weights=ep["elev_gain"], epsilon=.0005)
print(list(all_paths))
#############################
# epsilon=5 CRASHES
#############################
all_paths = all_shortest_paths(g, v_start, v_dest, weights=ep["elev_gain"], epsilon=5) print(list(all_paths))