[Networkit] Feedback req'd: Multi-edges

Christian Staudt christian.staudt at kit.edu
Wed Aug 12 10:30:04 CEST 2015

Hi all,
currently inserting multi-edges into networkit.Graph are not supported, you basically break the data structure doing that. Maybe the documentation could be more obvious on this.

>  In particular, there is a method in Graph.cpp called checkConsistency which checks for multiedges, suggesting that multiedges are a natural extension of NetworKit's Graph object.

Documentation of Graph.checkConsistency says: "Check for invalid graph states, such as multi-edges.”

It’s possible to break the Graph data structure for performance reasons, that’s a conscious choice. Checking during insertion whether an edge (u,v) already exists takes O(deg(u)) time, the resulting slowdown for graph generators and readers is of course not acceptable.

Support for multi-graphs has not been needed so far. Before investing work into this, I’d like to hear how multi-graphs are relevant and why they cannot be modelled with the existing machinery. (Remember that you can efficiently attach arbitrary data to any edge through indexing.) My feeling is that they are probably not necessary. Furthermore, introducing multi-graphs probably leads to a ton of follow-up work: The definitions of all algorithms probably need to be revisited, and the special case of multi-edges needs to be handled….  

Provided that the documentation is clear, I think it is okay to leave things as they are.


On 12 Aug 2015, at 09:42, Henning Meyerhenke <henning.meyerhenke at kit.edu> wrote:

> Right now multi-edges are inserted, but the search for a particular edge stops at its first occurrence. This behavior should be changed.
> These are the obvious options:
> - Disallow multi-edges, i.e. checking during insertion if an edge already exists
> - Proper iteration (likely to slow down numerous algorithms)
> - Separate handling of multi-graphs (may require a lot of additional code)
> All, could we please get some feedback if and when you need multi-edges?

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

More information about the NetworKit mailing list