[Networkit] matching algorithms and data structure

Moritz von Looz moritz.looz-corswarem at kit.edu
Wed Oct 28 18:00:00 CET 2015

Hey Christian,

I'm currently using the matching algorithms to build a custom partitioning algorithm based on FM.

As to a), they have a couple of issues:

The MatchingContractor does not check for directedness in the beginning and has a bug where the weight of each edge was added twice, thus doubling the edge weights.

The LocalMaxMatcher matches a node with itself in case of a self-loop. This is bad when matching a coarsened graph, as self-loops are bound to happen there.

Matching.cpp has a bug where isMatched checked for a matching being none, but unMatch(v) sets match[v] to v instead of none.

I've fixes for these issues in a private repository, can merge them into the main repo if you want to.

As to b), they are useful to me right now.

All the best,

Am 28.10.2015 um 17:49 schrieb Christian Staudt:
> Hi developers,
> a) What’s the status of the matching algorithms (LocalMaxMatcher, PathGrowingMatcher) - are they working? They look old by now, should be refactored.
> b) There is a data structure called Matching (matching/Matching.h) which I created in the very early days. I am not sure it is still necessary. It offers some convenience methods, but every non-standard container data structure creates work in other places. One idea would be to replace it with or make it a subclass of Partition. Every matching is a partition of the node set, right? That would also make a class like coarsening/MatchingContracter obsolete.
> Chris
> _______________________________________________
> NetworKit mailing list
> NetworKit at ira.uni-karlsruhe.de
> https://lists.ira.uni-karlsruhe.de/mailman/listinfo/networkit

More information about the NetworKit mailing list