[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,
Moritz

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