# 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:

"""

# this fails
import numpy
notm = numpy.invert(M.ma)

# this works, but is O(|V|)
it = imap(lambda x:not Mask[x], graph.vertices())
"""

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:

"""

# this fails
import numpy
notm = numpy.invert(M.ma)

# this works, but is O(|V|)
it = imap(lambda x:not Mask[x], graph.vertices())
"""

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?

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():

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:
>
> """
>
> # this fails
> import numpy
> notm = numpy.invert(M.ma)
>
> # this works, but is O(|V|)
> it = imap(lambda x:not Mask[x], graph.vertices())
> """
>
> 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.

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