[Networkit] Feedback req'd: Multi-edges
henning.meyerhenke at kit.edu
Fri Aug 14 14:54:55 CEST 2015
Even if we have to factor in vacation time, it seems that multi-graphs
are not of high concern for anybody. (Dissenting opinions: please email us!)
Thus, let's go for the option of disallowing multi-edges by making the
documentation more explicit. I have already inserted a comment for
addEdge. Who volunteers for other relevant methods?
Moreover, Matteo's remark about missing statements on time complexity is
important, in particular for the Graph class. All, please add
corresponding comments for new developments and revisit your old code
where relevant -- this effort is also likely to avoid performance bugs
in the future.
Am 13.08.15 um 19:26 schrieb Christian Staudt:
> Hi Matteo
> On 12 Aug 2015, at 16:02, Matteo Riondato <matteo at cs.brown.edu>
>>> Its possible to break the Graph data structure for performance
>>> reasons, thats a conscious choice.
>> Interesting. Can you please elaborate on this, maybe with an
> Just saying that the issue is known but we chose not to implement an
> expensive check, a choice pro performance and contra safety.
>>> 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,
>> check_for_dups)" and a similar flag for a buildGraph() function
>> (names completely arbitrary, I dont 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
>> 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.
> O(E) space is not something we can easily afford. We are targeting
> large networks and memory is likely to be the primary bottleneck in
>> By the way, it is kind of difficult to comment of what would hurt
>> the complexity of some operations and what wouldnt, as the
>> documentation doesnt contain time complexities for most
> Yes, that could definitely be improved.
>> For example, how much time does hasEdge(u,v) take?
> Needs to scan the vector of adjacent nodes associated with u until it
> finds the entry v.
>> 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
> The introduction of directed graphs is still keeping us busy after a
> year, but that was a necessary thing. Multi-graphs - not so much.
> Best, Chris
> _______________________________________________ NetworKit mailing
> list NetworKit at ira.uni-karlsruhe.de
Karlsruhe Institute of Technology (KIT)
Institute of Theoretical Informatics (ITI)
Juniorprof. Dr. Henning Meyerhenke
Theoret. Informatics / Parallel Computing
KIT - University of the State of Baden-Wuerttemberg and
National Research Center of the Helmholtz Association
-------------- next part --------------
A non-text attachment was scrubbed...
Size: 5399 bytes
Desc: S/MIME Cryptographic Signature
More information about the NetworKit