[Networkit] ClusterContractor creates loops in the coarsened graph

Henning Meyerhenke meyerhenke at kit.edu
Sat Apr 4 09:09:02 CEST 2015

Hello Patrick,

What you describe is indeed desired behavior for some use cases.

You have permission to make it optional, with default behavior to 
introduce self-loops as before (so that no other code changes are 
necessary). The same applies to other contractors if you need them.

Thank you,
Henning Meyerhenke

Am 03.04.15 um 21:04 schrieb Patrick Bisenius:
> Hi,
> 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
> 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.
> Greetings,
> Patrick


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: 5316 bytes
Desc: S/MIME Cryptographic Signature
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20150404/b2471296/attachment.p7s>

More information about the NetworKit mailing list