[Networkit] Feedback req'd: Multi-edges

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

Thank you,

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>
> wrote:
>>> 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?
> 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, 
, 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.
>> 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
> practice.
>> 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.
> 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
>> multigraphs.
> 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
> https://lists.ira.uni-karlsruhe.de/mailman/listinfo/networkit


Karlsruhe Institute of Technology (KIT)
Institute of Theoretical Informatics (ITI)

Juniorprof. Dr. Henning Meyerhenke
Theoret. Informatics / Parallel Computing

Phone: +49-721-608-41876
Web: http://parco.iti.kit.edu/henningm/

KIT - University of the State of Baden-Wuerttemberg and
National Research Center of the Helmholtz Association

-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 5399 bytes
Desc: S/MIME Cryptographic Signature
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20150814/cf1c4aa2/attachment.p7s>

More information about the NetworKit mailing list