[Networkit] Request for Comments: Efficient Set Operations on Graphs

Christian Staudt christian.staudt at kit.edu
Tue Nov 3 18:16:42 CET 2015



On 03 Nov 2015, at 12:11, Henning Meyerhenke <henning.meyerhenke at kit.edu> wrote:

> 
> 
> Am 03.11.15 um 18:05 schrieb Christian Staudt:
>> Hi all,
>> I would like to ask for comments on an area we have so far not worked on, namely support for set operations on graphs. For example:
>> 
>> - Graph.union(Graph): merge two graphs, where nodes with same id are treated as identical
>> - Graph.append(Graph): add the second graph as a subgraph to the first, remapping the nodes to new ids
>> - Graph.intersect(Graph): …..
>> - ….
>> 
>> I think all these operations can be realized with the existing Graph API (i.e. calling modifier methods on the graph). But maybe they can be implemented more efficiently by allowing access to the internals of the data structure. E.g. ,could G1.append(G2) be realized by directly appending the adjacency structure of G2 to that of G1 and remapping the indices (add G1.upperNodeIdBound() to every node id of G2).
>> 
> 
> 
> 
>> What are your thoughts on this?
> 
> In the sense of necessity or way of implementation? Or both?
> 
> H.
> 


Both. 

I believe I need to implement something like Graph.append for my new graph generator. There is a chance to build a general instead of one (or several redundant) single-purpose solutions.


-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 5084 bytes
Desc: not available
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20151103/25fe6961/attachment-0001.p7s>


More information about the NetworKit mailing list