[Networkit] Feedback req'd: Multi-edges

Matteo Riondato matteo at cs.brown.edu
Wed Aug 12 16:02:36 CEST 2015


> On Aug 12, 2015, at 6:30 PM, Christian Staudt <christian.staudt at kit.edu> wrote:
> 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.
> 
> It’s possible to break the Graph data structure for performance reasons, that’s a conscious choice.

Interesting. Can you please elaborate on this, maybe with an example?

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

If I may comment on that, perhaps this decision of whether the slowdown is acceptable should be left to the user. I.e., it should be possible to have a “bool addEdge(vertex u, vertex v, …, bool check_for_dups)" and a similar flag for a buildGraph() function (names completely arbitrary, I don’t remember the nkit API).

Also, one could use a membership data structure to store which edges have been inserted, and the lookup would be O(1) in amortized time, at the price of O(E) additional space.

Yes, I’m sure patches would be welcome, and yes, I know that I’m changing the return value of addEdge (this can be avoided though) ;)

By the way, it is kind of difficult to comment of what would hurt the complexity of some operations and what wouldn’t, as the documentation doesn’t contain time complexities for most operations. For example, how much time does “hasEdge(u,v)” take? From your comment I get that it takes O(deg(u)) (it should actually take O(min(out_deg(u),in_deg(v)) imho, provided out_deg() and in_deg() are O(1), which is also not documented/clear).
In any case with the membership data structure mentioned above, you would make hasEdge() take O(1) on average.

> introducing multi-graphs probably leads to a ton of follow-up work: The definitions of all algorithms probably need to be revisited

Yes, IMHO this is the valid observation for not having multigraphs as “first class citizens” (and perhaps at all). Most algorithms are not entirely straightforward to extend to multigraphs and actually many problems on graphs may not even have a unique extension to multigraphs. In the literature everyone (+- epsilon) assume that G is not a multigraph.

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

Perhaps it should be mentioned that adding an edge multiple times (e.g., by calling add_edge with the same parameters) leads to undefined behavior (does it actually?) and is not supported (but it doesn’t return any error, which is kind of undesirable, imho)

Matteo
-------------- 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/20150813/42a42aa6/attachment.sig>


More information about the NetworKit mailing list