Reduce function on parallel edges, and more general groupby-reduce in graph-tool

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

Reduce function on parallel edges, and more general groupby-reduce in graph-tool

linello
I have a graph in graph-tool with parallel edges. All parallel edges are assigned an `EdgePropertyMap` representing their weight with a double. I would like to return a graph where the edges are condensed into a single edge where a custom reduce operation on these weights is performed. For example:


    H = gt.Graph(directed=True)
    H.add_edge(0,1) # edge 0
    H.add_edge(0,1) # edge 1
    H.add_edge(0,1) # edge 2
    H.add_edge(1,0) # edge 3
    H.add_edge(0,2) # edge 4

    ew = H.new_edge_property("double")
   
    ew[list(H.edges())[0]]=1.2
    ew[list(H.edges())[1]]=2.3
    ew[list(H.edges())[2]]=-4.2
    ew[list(H.edges())[3]]=5.8
    ew[list(H.edges())[3]]=1.0
    H.ep['weights'] = ew

   
   
In this case the edge (0,1), with a reduce function "sum", should have total weight 1.2+2.3-4.2= -0.7 while the remaining edges should keep the same weight (i.e. edge 3 should keep weight 5.8 and edge 4 should maintain weight 1.0).
Using `gt.condensation_graph` seems to do the trick, but only sum operation can be performed. To do this we need to use `H.vertex_index` as vertex property:

    Hcond, prop, vcount, ecount, v_avg, edge_avg = gt.condensation_graph(H,prop=H.vertex_index, aeprops=[H.ep['weights']])

Unfortunately this function only allows sum operation to be performed. What about using a different "reduce" function, like for example max? What about operations on non-numeric types of edges?
It would greatly help carrying complex operations directly in Graph-tool, even if the value type of edges property is different than numeric.


More generally, what about introducing a split-apply-reduce framework to vertices and edges, or is it already possible with some modifications to `gt.condensation_graph`?



_______________________________________________
graph-tool mailing list
[hidden email]
https://lists.skewed.de/mailman/listinfo/graph-tool
Reply | Threaded
Open this post in threaded view
|

Re: Reduce function on parallel edges, and more general groupby-reduce in graph-tool

Tiago Peixoto
Administrator
Am 26.05.20 um 12:10 schrieb Carlo Nicolini:
> More generally, what about introducing a split-apply-reduce framework to
> vertices and edges, or is it already possible with some modifications to
> `gt.condensation_graph`?

This indeed would be quite nice, and no it's not currently possible with
condensation_graph(). Please open an issue in the website with a feature
request, and I will implement it when time permits.

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