[Networkit] ClusterContractor creates loops in the coarsened graph

Patrick Bisenius patrick.bisenius at gmail.com
Sat Apr 4 10:18:21 CEST 2015


Hi,

thank you for your fast answer. I have added an option now.

Greetings,
Patrick Bisenius

> Am 04.04.2015 um 09:09 schrieb Henning Meyerhenke <meyerhenke at kit.edu>:
> 
> 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
> =======================================================
> 
> _______________________________________________
> NetworKit mailing list
> NetworKit at ira.uni-karlsruhe.de
> https://lists.ira.uni-karlsruhe.de/mailman/listinfo/networkit

-------------- 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/20150404/a699a4f5/attachment.sig>


More information about the NetworKit mailing list