Property maps: Type name: Safe to use "bool" type to store values between 1 and 100?

graph-tool
1

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

2

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

3

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