[Networkit] matching algorithms and data structure
Moritz von Looz
moritz.looz-corswarem at kit.edu
Wed Oct 28 18:00:00 CET 2015
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.
> NetworKit mailing list
> NetworKit at ira.uni-karlsruhe.de
More information about the NetworKit