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

Matteo Riondato matteo at cs.brown.edu
Wed Nov 4 17:32:59 CET 2015

> On Nov 4, 2015, at 10:56 AM, 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?
> For append it makes sense what you propose since it is so much faster.


> For union it depends on the result you want to have. Iirc, we do not allow multiple edges. Thus, during a union, you would have to test for duplicates. For that you have different options that depend on the size of the respective adjacency "lists" you need to merge. For a small addition the standard API should suffice, but for larger "lists" of roughly equal size I'd go for something else.

I’m talking without actually having looked at how the adjacency structure is implemented, so feel free to ignore/correct me =), but if

1) the adjacency structure is sorted in some way, and
2) you can get an iterator of its members according to the sorting order, and
3) you can define a comparison function to compare a member of S1 with a member of S2 for equality (Si is the adjacency structure for the graph Gi)

then you can use set_union from <algorithm> and the running time is O(min(|S1|, |S2)), and it will take care of the duplicates.

One additional comment: are these operations modifying one of the two Graph object or are they creating a new Graph (I vote for this second option, new Graph). I’m asking because while union() and intersect() should create a new graph (in the same way that the set operation “create" a “new” set), append() is more ambiguous, and actually suggests that one of the Graph object is modified, but I would suggest some uniformity among these (or non-uniformity, my point is that it must be a motivated design choice).

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 163 bytes
Desc: Message signed with OpenPGP using GPGMail
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20151104/847015e8/attachment.sig>

More information about the NetworKit mailing list