Hi,
It is indeed safe up to a certain point. But one needs to be careful when
using an algorithm like dijkstra_search, as the result might be unexpected.
But there is a work-around...
dijkstra_search: when specifying the weights as small integer values stored
in a "bool", the result dist_map has only 0 or 1 values for the distance
from a source vertex. There is a work-around as one can give the dist_map
as argument, and declare dist_map to have a value type of 'int16_t or
higher'.
It works as expected, but one needs to be aware that the result map should
be given as argument to dijkstra_search().
Thanks for the great package...
Didier
import graph_tool.all as gt
import numpy as np
g = gt.Graph()
g.add_vertex(10)
for i in range(9): g.add_edge(i, i+1)
# 'bool' edge_property: dijkstra_search() assumes the edge values to be
boolean
g.edge_properties['weight'] = g.new_edge_property('bool')
for e in g.edges(): g.edge_properties['weight'][e] = np.random.randint(1,
10)
dist_map, pred_map = gt.dijkstra_search(g, source=g.vertex(0),
weight=g.edge_properties['weight'])
print dist_map.value_type()
print dist_map.a
bool
[0 1 1 1 1 1 1 1 1 1] # NOT the expected value...
# 'int16_t' edge_property: dijkstra_search() saves the path distances in
int16_t
g.edge_properties['weight'] = g.new_edge_property('int16_t')
for e in g.edges(): g.edge_properties['weight'][e] = np.random.randint(1,
100)
dist_map, pred_map = gt.dijkstra_search(g, source=g.vertex(0),
weight=g.edge_properties['weight'])
print dist_map.value_type()
print dist_map.a
int16_t
[ 0 85 164 186 217 239 298 374 439 457]
# workaround: provide dist_map with desired value_type to algorithm
# Note that the value type needs to be able to contain a **sum** of edge
weights.
# For large graphs, thos might not fit in an int16_t if the edge weights
are
# themselves int16_t.
g.edge_properties['weight'] = g.new_edge_property('bool')
for e in g.edges(): g.edge_properties['weight'][e] = np.random.randint(1,
100)
dist_map = g.new_vertex_property('int32_t')
dist_map, pred_map = gt.dijkstra_search(g, source=g.vertex(0),
weight=g.edge_properties['weight'], dist_map = dist_map)
print dist_map.value_type()
print dist_map.a
int32_t
[ 0 65 140 206 237 330 374 431 501 583]
# 'int16_t' edge_property: ensure that the **sum** of several int16_t
fits in a int16_t
g.edge_properties['weight'] = g.new_edge_property('int16_t')
for e in g.edges(): g.edge_properties['weight'][e] = np.random.randint(1,
32000)
dist_map, pred_map = gt.dijkstra_search(g, source=g.vertex(0),
weight=g.edge_properties['weight'])
print dist_map.value_type()
print dist_map.a
OverflowError: bad numeric conversion: positive overflow
--
View this message in context:
http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/Property-maps-Type-name-Safe-to-use-bool-type-to-store-values-between-1-and-100-tp4025875p4025902.html
Sent from the Main discussion list for the graph-tool project mailing list
archive at Nabble.com.
_______________________________________________
graph-tool mailing list
[email protected]
http://lists.skewed.de/mailman/listinfo/graph-tool
