Complexity of graphview

classic Classic list List threaded Threaded
3 messages Options
P-M
Reply | Threaded
Open this post in threaded view
|

Complexity of graphview

P-M
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



--
Sent from: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/
_______________________________________________
graph-tool mailing list
[hidden email]
https://lists.skewed.de/mailman/listinfo/graph-tool
Reply | Threaded
Open this post in threaded view
|

Re: Complexity of graphview

Tiago Peixoto
Administrator
Am 21.06.2018 um 17:40 schrieb P-M:
> 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?

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

--
Tiago de Paula Peixoto <[hidden email]>


_______________________________________________
graph-tool mailing list
[hidden email]
https://lists.skewed.de/mailman/listinfo/graph-tool

signature.asc (849 bytes) Download Attachment
--
Tiago de Paula Peixoto <tiago@skewed.de>
P-M
Reply | Threaded
Open this post in threaded view
|

Re: Complexity of graphview

P-M
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



--
Sent from: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/
_______________________________________________
graph-tool mailing list
[hidden email]
https://lists.skewed.de/mailman/listinfo/graph-tool