meyerhenke at kit.edu
Tue Feb 10 11:37:35 CET 2015
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.
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?
> Lars Gottesbüren
Karlsruhe Institute of Technology (KIT)
Institute of Theoretical Informatics (ITI)
Juniorprof. Dr. Henning Meyerhenke
Theoret. Informatics / Parallel Computing
KIT - University of the State of Baden-Wuerttemberg and
National Research Center of the Helmholtz Association
-------------- next part --------------
A non-text attachment was scrubbed...
Size: 5316 bytes
Desc: S/MIME Cryptographic Signature
More information about the NetworKit