[graph-tool] GraphView with lambda function

Gerion Entrup gerion.entrup at flump.de
Wed Jan 8 15:33:32 CET 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.

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

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 659 bytes
Desc: This is a digitally signed message part.
URL: <https://lists.skewed.de/pipermail/graph-tool/attachments/20200108/bfacd7ab/attachment.asc>

More information about the graph-tool mailing list