I am trying to run the shortest_path function on various nodes on a graph. I am using a starting vertex, and returning all vertices within a certain threshold distance. The edges are weighted by a distance metric.
My dilemma is that it works as intended except for some nodes. All I can think of is that the problematic edges have an edge that exceeds the threshold distance, in which case it is returning only one edge, instead of all edges that are less than the threshold distance. Is it possible that once the algorithm reaches an edge that exceeds the cutoff distance, that it stops then-and-there, instead of searching the remaining vertices? I am attaching my python file and the graph file that I’m testing this on. - The file prints information about two test vertices to the console, one of a working vertex (A) and the other of a vertex (B) that doesn’t work as anticipated. (I can’t see anything suspiciously different between them.) - It also plots three copies of the graph: A) filtered graph of vertex (A); B) filtered graph of vertex (B); C) non-filtered copy of the entire graph showing index numbers and weights Thanks.
Plaza.xml.gz
Description: GNU Zip compressed data
from graph_tool.all import *
# Load and setup the graph:
Dir = '/your/Directory/'
g = load_graph(Dir + 'Plaza.xml.gz')
# Loaded property maps
v_coords = g.vertex_properties["v_coords"]
e_dist = g.edge_properties['e_dist']
# set distance threshold
dist = 600
def info(n):
print ''
print '#### START INFO ####'
print 'id: ' + str(n)
print 'edge: ' + str([str(e) for e in n.all_edges()])
print 'neighbour: ' + str([str(nb) for nb in n.all_neighbours()])
print 'graph: ' + str(n.get_graph())
print 'in_degree: ' + str(n.in_degree())
print 'in_edges: ' + str([str(ie) for ie in n.in_edges()])
print 'in_neighbours: ' + str([str(inb) for inb in n.in_neighbours()])
print 'is valid: ' + str(n.is_valid())
print 'out degree: ' + str(n.out_degree())
print 'out_edges: ' + str([str(oe) for oe in n.out_edges()])
print 'out_neighbours: ' + str([str(on) for on in n.out_neighbours()])
print '####'
print 'edge distances: ' + str([str(e_dist[e]) for e in n.all_edges()])
print 'neighbour out degree: ' + str([str(nb.out_degree()) for nb in n.all_neighbours()])
print '#### END INFO ####'
print ''
info(g.vertex(37))
info(g.vertex(66))
v_localDist = shortest_distance(g, source=37, weights=e_dist, max_dist=dist)
v_mask = g.new_vertex_property('bool')
v_mask.a = v_localDist.a <= dist
g.set_vertex_filter(v_mask)
graph_draw(g,
output_size=(2000, 2000),
pos=v_coords,
vertex_pen_width=0.4,
vertex_text=g.vertex_index,
edge_text=e_dist,
output=Dir+'shortest_distance_test_node_37.png')
g.set_vertex_filter(None)
v_localDist = shortest_distance(g, source=66, weights=e_dist, max_dist=dist)
v_mask = g.new_vertex_property('bool')
v_mask.a = v_localDist.a <= dist
g.set_vertex_filter(v_mask)
graph_draw(g,
output_size=(2000, 2000),
pos=v_coords,
vertex_pen_width=0.4,
vertex_text=g.vertex_index,
edge_text=e_dist,
output=Dir+'shortest_distance_test_node_66.png')
g.set_vertex_filter(None)
graph_draw(g,
output_size=(2000, 2000),
pos=v_coords,
vertex_pen_width=0.4,
vertex_text=g.vertex_index,
vertex_size=5,
edge_text=e_dist,
output=Dir+'shortest_distance_whole_graph.png')
_______________________________________________ graph-tool mailing list [email protected] http://lists.skewed.de/mailman/listinfo/graph-tool
