[Networkit] matching algorithms and data structure

Christian Staudt christian.staudt at kit.edu
Mon Nov 2 17:11:14 CET 2015

I have had a bunch of problems with the Matching data structure and algorithms. When I tried to use the matching algorithms I got random crashes, and a run through valgrind showed invalid read errors coming from the Matching class. Then I looked at the implementation of Matching, which is very much out of date and will fail at least for graphs with deleted nodes. I tried to rewrite it properly.

If you are working with this, please check thoroughly, because it seems that you have been building on buggy code that’s not up to the standards.


On 28 Oct 2015, at 13:00, Moritz von Looz <moritz.looz-corswarem at kit.edu> wrote:

> 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
> _______________________________________________
> NetworKit mailing list
> NetworKit at ira.uni-karlsruhe.de
> https://lists.ira.uni-karlsruhe.de/mailman/listinfo/networkit

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 495 bytes
Desc: Message signed with OpenPGP using GPGMail
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20151102/cb88626a/attachment.sig>

More information about the NetworKit mailing list