Hi,
I want to add a ‘weight’ edge attribute with weights ranging from 1 to 100 (values that fit in an unsigned char). In order to save some space, I would like to store those weights in an uint8_t instead of int16_t. The uint8_t is accessible through the ‘bool’ type name for the Property Maps.
- I checked that serializing and de-serializing ‘bool’ type names with values in the range [1-100] works fine. - I also checked that running PageRank using the ‘weight’ edge property gives the same result whether the weights ([1-100]) are stored as type ‘bool’ or type ‘int16_t’.
My question is it safe to assume that it will always work. Do some of the algorithms check the type name of the property and seeing ‘bool’, those algorithms could decide to use true/false values rather than an integer in range [0-255].
Thanks for any feedback,
Didier
On 19.11.2014 17:13, Didier Guillevic wrote:
Hi,
I want to add a ‘weight’ edge attribute with weights ranging from 1 to 100 (values that fit in an unsigned char). In order to save some space, I would like to store those weights in an uint8_t instead of int16_t. The uint8_t is accessible through the ‘bool’ type name for the Property Maps.
- I checked that serializing and de-serializing ‘bool’ type names with values in the range [1-100] works fine.
- I also checked that running PageRank using the ‘weight’ edge property gives the same result whether the weights ([1-100]) are stored as type ‘bool’ or type ‘int16_t’.
My question is it safe to assume that it will always work. Do some of the algorithms check the type name of the property and seeing ‘bool’, those algorithms could decide to use true/false values rather than an integer in range [0-255].
Yes, this is totally safe. "bool" is a just a synonym to "uint8_t" everywhere in the library, as far as property maps are concerned.
Best, Tiago
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/... Sent from the Main discussion list for the graph-tool project mailing list archive at Nabble.com.
-
Didier Guillevic -
Tiago de Paula Peixoto