inverting boolean PropertyMaps
Hi again, I'm using boolean PropertyMaps to represent subsets of graph vertices in combination with `GraphView(g, vfilt=Mask).vertices()` for iteration. I often need the complement of such sets and would like to complement a mask using `numpy.invert`, for efficiency: """ Mask = graph.new_vertex_property('bool') # this fails import numpy notm = numpy.invert(M.ma) NotMask = graph.new_vertex_property('bool', vals=notm) # this works, but is O(|V|) it = imap(lambda x:not Mask[x], graph.vertices()) NotMask = graph.new_vertex_property("bool", vals=it) """ The issue seems to be that in boolean PropertyMap internally uses a PropertyArray of dtype `uint8`, and not `bool`: In the example above (my graph has 6 nodes), Mask.ma is PropertyArray([0, 0, 0, 0, 0, 0], dtype=uint8) So of course, numpy.invert(M.ma) yields PropertyArray([255, 255, 255, 255, 255, 255], dtype=uint8) and not, as expected, the array with only 1's. Is there a reason for using uint8 instead of booleans? And is there a O(1) operation to invert masks? Thanks, Patrick
On 26.09.2016 11:06, Patrick Totzke wrote:
Hi again,
I'm using boolean PropertyMaps to represent subsets of graph vertices in combination with `GraphView(g, vfilt=Mask).vertices()` for iteration. I often need the complement of such sets and would like to complement a mask using `numpy.invert`, for efficiency:
""" Mask = graph.new_vertex_property('bool')
# this fails import numpy notm = numpy.invert(M.ma) NotMask = graph.new_vertex_property('bool', vals=notm)
# this works, but is O(|V|) it = imap(lambda x:not Mask[x], graph.vertices()) NotMask = graph.new_vertex_property("bool", vals=it) """
The issue seems to be that in boolean PropertyMap internally uses a PropertyArray of dtype `uint8`, and not `bool`: In the example above (my graph has 6 nodes), Mask.ma is
PropertyArray([0, 0, 0, 0, 0, 0], dtype=uint8)
So of course, numpy.invert(M.ma) yields
PropertyArray([255, 255, 255, 255, 255, 255], dtype=uint8)
and not, as expected, the array with only 1's.
You should use numpy.logical_not() instead.
Is there a reason for using uint8 instead of booleans?
Yes, efficiency. Vector of bools (i.e. vector<bool>) tends to be considerably slower.
And is there a O(1) operation to invert masks?
Of course not, that would be magic. Both logical_lot() and invert() are O(N). They are faster than imap because the loops are performed in C, not python. Best, Tiago -- Tiago de Paula Peixoto <tiago@skewed.de>
On 26.09.2016 13:02, Tiago de Paula Peixoto wrote:
And is there a O(1) operation to invert masks?
Of course not, that would be magic. Both logical_lot() and invert() are O(N). They are faster than imap because the loops are performed in C, not python.
Just to briefly contradict myself, in fact there _is_ a O(1) way to invert a mask in graph-tool, you simply set the "inverted" parameter in set_vertex_filter(): g.set_vertex_filter(mask, inverted=True) Since this does not touch the contents of 'mask', it is O(1). -- Tiago de Paula Peixoto <tiago@skewed.de>
Quoting Tiago de Paula Peixoto (2016-09-26 13:02:03)
On 26.09.2016 11:06, Patrick Totzke wrote:
Hi again,
I'm using boolean PropertyMaps to represent subsets of graph vertices in combination with `GraphView(g, vfilt=Mask).vertices()` for iteration. I often need the complement of such sets and would like to complement a mask using `numpy.invert`, for efficiency:
""" Mask = graph.new_vertex_property('bool')
# this fails import numpy notm = numpy.invert(M.ma) NotMask = graph.new_vertex_property('bool', vals=notm)
# this works, but is O(|V|) it = imap(lambda x:not Mask[x], graph.vertices()) NotMask = graph.new_vertex_property("bool", vals=it) """
The issue seems to be that in boolean PropertyMap internally uses a PropertyArray of dtype `uint8`, and not `bool`: In the example above (my graph has 6 nodes), Mask.ma is
PropertyArray([0, 0, 0, 0, 0, 0], dtype=uint8)
So of course, numpy.invert(M.ma) yields
PropertyArray([255, 255, 255, 255, 255, 255], dtype=uint8)
and not, as expected, the array with only 1's.
You should use numpy.logical_not() instead.
Great! I overlooked this. Works like a charm :)
Is there a reason for using uint8 instead of booleans?
Yes, efficiency. Vector of bools (i.e. vector<bool>) tends to be considerably slower.
And is there a O(1) operation to invert masks?
Of course not, that would be magic. Both logical_lot() and invert() are O(N). They are faster than imap because the loops are performed in C, not python.
Right, OK. So if I just want to iterate over the nodes of the complement subgraph, relative to a given vertex mask, I could use `GraphView.vertices()`, on a graph view after setting `gv.set_vertex_filter(Mask, inverted=True)`. Setting this filter is O(1), as is the instantiation of the GraphView. So far this makes perfect sense to me. Thanks again for your quick response. P
participants (2)
-
Patrick Totzke -
Tiago de Paula Peixoto