Class SuitorMatcher¶

Inheritance Relationships¶

Class Documentation¶

class SuitorMatcher : public NetworKit::Matcher¶

Suitor matching finding algorithm.

Public Functions

SuitorMatcher(const Graph &G, bool sortSuitor = true, bool checkSortedEdges = false)¶

Computes a 1/2-approximation of the maximum (weighted) matching of an undirected graph using the Suitor algorithm from Manne and Halappanavar presented in “New Effective Multithreaded

Matching Algorithms”, IPDPS 2014. The algorithm has two versions: SortSuitor (faster, but only works on graphs with adjacency lists sorted by non-increasing edge weight) and Suitor (works on generic graphs). If using SortSuitor, use GrapTools::sortEdgesByWeight(G, true) to sort the adjacency lists by non-increasing edge weight.

Parameters:

• G – An undirected graph.

• sortSuitor – If true uses the SortSuitor version, otherwise it uses Suitor.

• checkSortedEdges – If true and sortSuitor is true it checks whether the adjacency lists of the input graph are sorted by non-increasing edge weight. If they are not, it throws a std::runtime_error.

~SuitorMatcher() override = default¶

virtual void run() override¶

Runs the algorithm.