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

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, 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

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).

Quoting Tiago de Paula Peixoto (2016-09-26 13:02:03)

>
> 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, 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 :slight_smile:

> 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