Class PathGrowingMatcher¶

Inheritance Relationships¶

Class Documentation¶

class PathGrowingMatcher : public NetworKit::Matcher¶

Path growing matching algorithm as described by Hougardy and Drake, http://dx.doi.org/10.1016/S0020-0190(02)00393-9 Computes an approximate maximum weight matching with guarantee 1/2. (Note that better algorithms in terms of approximation quality exist.)

Public Functions

PathGrowingMatcher(const Graph &G)¶

Parameters:

G – [in] Undirected graph with no self-loops for which matching is computed.

PathGrowingMatcher(const Graph &G, const std::vector<double> &edgeScores)¶

Parameters:

G – [in] Undirected graph with no self-loops for which matching is computed.

virtual void run() override¶

Runs path growing algorithm to compute approximate maximum weight matching for graph G.

Returns:

Matching (at least half as heavy as maximum weight matching).