Re: [graph-tool] GraphView with lambda function

8 Jan 2020

      Am Montag, 6. Januar 2020, 15:11:53 CET schrieb Tiago de Paula Peixoto:
...
Am 06.01.20 um 13:53 schrieb Gerion Entrup:
...
Hi,
the documentation describes that GraphView can be given a unary function
to filter vertices or edges.
I have tried that and it seems to fail. My GraphView has not the
expected vertices and edges.
However, my assumption is that the filter is only evaluated one time
(at initialization).
Let me make an example:
```
g = graph_tool.Graph()
a = graph_tool.GraphView(g, vfilt=...)
fill_the_graph(g)
do_stuff_with(a) # <- here a does not contain any data
```
From the documentation, it seems that graph_tool constructs a property
from the filter function and uses this for filtering (therefore also
needing O(N)), but fill this property only on construction. Can you
mention this in the documentation as a hint or warning?
Right, this is entirely expected behavior. It seems obvious to me in the
documentation, but I will make it more explicit.
Thanks.
...
Note that it would be completely unreasonable performance-wise to
populate the filter property map lazily on demand.
Only kind of. It should be feasible to populate the property on demand
(only for the nodes/edges requested), but cache them and only recalculate
them if a graph change is done and only for the changed vertices/edges.
Then overall, it should be an O(N) operation again (with N = amount of
all vertices/edges, even the deleted ones).
...
Note also that if you had modified `a` instead of `g` in your example,
the filtering would behave as expected (i.e. new vertices or edges would
appear in the graph view).
...
Maybe also a recalculate function for GraphView is meaningful that
evaluates the lambda function again.
I don't think this is good design. GraphViews are supposed to be cheap
objects that can be constructed on demand. If the filtering needs to be
re-done, then a new GraphView should be constructed, maybe even composed
from the older one. I.e. in your example you would re-create `a` after
you had modified `g`.
Ok, this should make some additional allocations, but probably is
lightweight enough.
A somewhat related but other question. Currently, I use lambdas only to
match for enum (int) values of properties, because my property can have
three variants instead of two, e.g.:
```
from enum import IntEnum

class TypeEnum(IntEnum):
    Type_A = 1
    Type_B = 2
    Type_C = 3

g = graph_tool.Graph()
g.vertex_properties['type'] = g.new_vp('int')

v = g.add_vertex()

g.vp.type[v] = TypeEnum.Type_C

g_view = graph_tool.GraphView(g, vfilt=lambda x: g.vp.type[x] == TypeEnum.Type_C)
```
This works with the behavior described above. I guess, the same filter directly
in C++ would be really efficient. What do you think of adding C++-Filters?

One possible syntax could be:
```
from graph_tool.filter import Filter, Equal, Lesser
g_view1 = graph_tool.GraphView(vfilt=Filter(Equal(g.vp.type, TypeEnum.Type_C)))
g_view2 = graph_tool.GraphView(vfilt=Filter(Equal(g.vp.type, 2)))
g_view3 = graph_tool.GraphView(vfilt=Filter(Lesser(g.vp.type, 3)))
```
Of course they need some constraints:
1. The comparison can only done between two properties or a constant and a property
2. Only basic operations (<, >, <=, >=, ==, !=) are possible. Maybe also boolean
operations (and, or).

Best,
Gerion