[Networkit] NetworKit

Henning Meyerhenke meyerhenke at kit.edu
Tue Feb 10 11:37:35 CET 2015


Dear Lars,

You are right, the contraction considers both directions of an edge and 
thus doubles the weight. The class is quite old and has never been 
extensively used so far. Please make the changes necessary to fix this 
error. One way of doing this is to check in the second loop if the other 
vertex has smaller or equal ID (equal is necessary for the self-loop case).

You have permission to change the PathGrowingMatcher according to your 
needs. It's another class that has hardly been used except for teaching. 
Exclude self-loops, they do not make sense for matchings (the code is 
older than NetworKit's capability of handling self-loops, I think). 
Include the rating function but make the code easy to read and use in 
cases where no rating function is necessary. Please align the 
ParallelMatcher with your changes.

Thanks for raising these issues.

Best,
Henning Meyerhenke


Am 09.02.15 um 23:02 schrieb Lars Gottesbüren:
> Dear NetworKit developers,
>
> I am currently working on a student project about matching-based
> multilevel graph partitioning for Professor Meyerhenke's optimization
> problems class and have a few questions and suggestions.
>
> We use the MatchingContractor (subfolder coarsening), which when
> assigning weights to the coarsened graph counts each original edge twice
> (thereby doubling the total edge weight of the original graph). Now I am
> wondering if that is unwanted behaviour or a feature. And most
> importantly if we're allowed to modify it.
>
> Secondly, we use the path-growing matching algorithm. Our graphs are
> supposed to have selfloops but these are not supposed to be eligible for
> a matching. As far as I can see, the path growing algorithm allows for
> that to happen.
> In this case, we would only like to add another function (so as not to
> mess up other people's code), which essentially performs the same
> algorithm but instead forbids selfloops as matching edges. In addition
> we would like the new function to accept an EdgeScoring instance in
> addition to the graph, because we want to easily deploy different edge
> ratings without having to copy the graphs.
>
> So, what's your opinion on this?
>
> Regards,
> Lars Gottesbüren

-- 

=======================================================
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/20150210/3fb2e3b9/attachment.p7s>


More information about the NetworKit mailing list