networkit.matching

class networkit.matching.Matcher

Bases: networkit.base.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.

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: networkit.matching.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: networkit.matching.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