Complexity of graphview

graph-tool
1

Hello,

If I try to filter a graph by passing a list of vertices in an ndarray as
argument to GraphView is the complexity proportional to the number of
vertices in the overall graph or the number of vertices in my array?

Best,

Philipp

2

That is not how GraphView works. It requires a vertex/edge mask or a filter
function. In the former case it is O(1), in the latter O(N) or O(E).

Best,
Tiago

3

Thank you for the clarification. I am trying to filter a set of vertices from
a graph to determine the number of edges each vertex has connecting it to
the other vertices in that sub-graph. Is this the most efficient way of
doing it or are there more optimised ways of doing so within graph-tool:

v_filter = g.new_vertex_property('bool')
for v in g.vertices():
    for target_block in groups:
        v_filter.set_value(False)
        vertices = groups[target_block] + [v]
        k = v.in_degree()+v.out_degree()
        for v_filt in vertices:
             v_filter[v_filt] = True
        f_g = gt.GraphView(g,v_filter)
        k_s = f_g.vertex(int(v)).in_degree()+f_g.vertex(int(v)).out_degree()

In essence I loop through all vertices two times (group contains all
vertices according to group memberhsip) which obviously slows things down.
Hence I was wondering, can I achieve the filtering more efficiently (as that
would reduce at least one of the O(V) dependencies)?

Thanks for any thoughts that anybody might have in advance!

Best,

Philipp