[Networkit] Feedback req'd: Multi-edges

Patrick Bisenius patrick.bisenius at gmail.com
Fri Aug 14 18:40:41 CEST 2015


Hi everybody, 

> Am 13.08.2015 um 19:26 schrieb Christian Staudt <christian.staudt at kit.edu>:
> 
>>> 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).
> 
> Could be done. Then again, we probably want an expensive check to be off in normal usage, and would switch it on when debugging and testing, i.e. when we are already suspicious. The main problem I see with the missing check is that the error passes unnoticed when we are not.

For my bachelor thesis, I had to compute subgraphs based on a given bipartition of a graph. Instead of using baseGraph.forEdges() to iterate over all the edges of the base graph and add them to one of the subgraphs, I used a nested baseGraph.forNodes() + baseGraph.forNeighborsOf(node v) construct at first. Of course, that resulted in undesired multi-edges in the subgraphs. I noticed that bug weeks later while implementing an unrelated algorithm and only after hours of debugging.

While this is only an anecdote, a warning in debug mode would probably be a good idea to avoid problems like this for other developers.

Yours faithfully,
Patrick Bisenius


More information about the NetworKit mailing list