[graph-tool] GraphView with lambda function

Tiago de Paula Peixoto tiago at skewed.de
Wed Jan 8 18:49:47 CET 2020


Am 08.01.20 um 15:33 schrieb Gerion Entrup:
> 
>> 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).

The point is that this would require the GraphView to know and be
updated when the underlying graph changes, and it would tie _access_ to
the filtered graph (even from C++) to function calls to the Python-side
filter function.

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

A much more efficient approach would be to use the numpy array interface
to property maps, instead of a lambda function:

g_view = GraphView(g, vfilt=g.vp.type.fa == TypeEnum.Type_C)

The equal comparison is done in C, and hence is much faster.

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

All of this is completely unnecessary once you remember that the numpy
array interface exists, which already implements all of this and more.

Best,
Tiago

-- 
Tiago de Paula Peixoto <tiago at skewed.de>


More information about the graph-tool mailing list