[Networkit] ClusterContractor creates loops in the coarsened graph

Patrick Bisenius patrick.bisenius at gmail.com
Fri Apr 3 21:04:16 CEST 2015


I believe I found a bug in the ClusterContractor but it could just as well be desired behavior. The contracted graph does contain loops because there is no check whether the two nodes u and v are mapped to the same supernode.
https://algohub.iti.kit.edu/parco/NetworKit/NetworKit/files/e2bea21f51e9e27df981bf172c4af2d13f80c795/networkit/cpp/coarsening/ClusterContractor.cpp#L49 <https://algohub.iti.kit.edu/parco/NetworKit/NetworKit/files/e2bea21f51e9e27df981bf172c4af2d13f80c795/networkit/cpp/coarsening/ClusterContractor.cpp#L49>

I am not sure if there are use-cases where loops are desired and useful, but they are pretty terrible for my use-case (coarsening with size-constrained label propagation). If this is indeed a feature and not a bug, there should be an option to disable self-loops.

The other contractors should probably be checked for this bug/feature, too.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20150403/cc7a2d08/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 842 bytes
Desc: Message signed with OpenPGP using GPGMail
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20150403/cc7a2d08/attachment.sig>

More information about the NetworKit mailing list