networkit.matching¶

class networkit.matching.Matcher¶

Bases: Algorithm

Abstract base class for matching algorithms

getMatching()¶

Returns the matching.

Returns:: Current Matching of graph.
Return type:: networkit.Matching

class networkit.matching.Matching(z=0)¶

Bases: object

Implements a graph matching. Create a new matching data structure for z elements.

Parameters:

zint, optional: Maximum number of nodes. Default: 0

areMatched(u, v)¶

Check if the nodes u and v are matched to each other.

Parameters:

u (int) – The first node.
v (int) – The second node.

Returns:

True if node u and v are matched to each other.

Return type:

bool

getVector()¶

Get the vector storing the data.

Returns:: Vector indexed by node id containing the node id of mate or networkit.none if unmatched
Return type:: list(int or None)

isMatched(u)¶

Check if node u is matched.

Parameters:: u (int) – The input node.
Returns:: True if u has a matching partner.
Return type:: bool

isProper(G)¶

Check whether this is a proper matching in the graph, i.e. there is an edge between each pair and if the matching partner of v is u then the matching partner of u is v.

Parameters:: G (networkit.Graph) – Graph to be checked.
Returns:: True if this is a proper matching.
Return type:: bool

match(u, v)¶

Set two nodes u and v as each others matching partners.

Parameters:

u (int) – The first node.
v (int) – The second node.

mate(v)¶

Get the matched neighbor of v if it exists, otherwise +inf.

Parameters:: v (int) – The input node.
Returns:: Matching partner of v if it exists, otherwise +inf.
Return type:: int

size(G)¶

Get the number of edges in this matching.

Parameters:: G (networkit.Graph) – The input graph.
Returns:: Total number of edges in the matching.
Return type:: int

toPartition(G)¶

Convert matching to a Partition object where matched nodes belong to the same subset and unmatched nodes belong to a singleton subset.

Parameters:: G (networkit.Graph) – The corresponding graph.
Returns:: The resulting partition.
Return type:: networkit.Partition

unmatch(u, v)¶

Reset the two nodes u and v to unmatched.

Parameters:

u (int) – The first node.
v (int) – The second node.

weight(G)¶

Get total weight of edges in this matching.

Parameters:: G (networkit.Graph) – The corresponding graph.
Returns:: Total weight of edges in this matching.
Return type:: float

class networkit.matching.PathGrowingMatcher(G, edgeScores)¶

Bases: Matcher

Path growing matching algorithm as described by Hougardy and Drake. Computes an approximate maximum weight matching with guarantee 1/2.

class networkit.matching.SuitorMatcher(G, sortSuitor=True, checkSortedEdges=False)¶

Bases: Matcher

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, call nk.graphtools.sortEdgesByWeight(G, True) to sort the adjacency lists by non-increasing edge weight.

Parameters:

G (networkit.Graph) – The input graph, must be undirected.
sortSuitor (bool, optional) – If True uses the SortSuitor version, otherwise it uses Suitor. Default: True
checkSortedEdges (bool, optional) – 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 raises a RuntimeError. Default: False