networkit.matching

class networkit.matching.BMatcher

Bases: Algorithm

Abstract base class for matching algorithms

getBMatching()

Returns the matching.

Returns:

Current b-matching of graph.

Return type:

networkit.BMatching

class networkit.matching.BMatching(b)

Bases: object

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

Parameters:
blist(int)

List containing the b-values for all 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

getB()

Get the b-value for each node.

Returns:

A list, containing the b-values (int) for each node.

Return type:

list(int)

getMatches()

Get the set of matches for each node.

Returns:

Returns the set of matches for each node.

Return type:

list(set)

isProper()

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.

Returns:

True if this is a proper matching.

Return type:

bool

isUnmatched(u)

Check if node u is unmatched.

Parameters:

u (int) – The input node.

Returns:

True if u has no matching partner.

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.

reset()

Removes all entries from the b-matching data structure

size()

Get the number of edges in this matching.

Returns:

Total number of edges in the matching.

Return type:

int

unmatch(u, v)

Reset the two nodes u and v to unmatched.

Parameters:
  • u (int) – The first node.

  • v (int) – The second node.

weight()

Get total weight of edges in this matching.

Returns:

Total weight of edges in this matching.

Return type:

float

class networkit.matching.BSuitorMatcher(G, second)

Bases: BMatcher

Computes a 1/2-approximate maximum weight b-matching of an undirected weighted Graph @c G using the sequential b-Suitor algorithm published by Khan et al. in “Efficient Approximation Algorithms For Weighted B-Matching”, SIAM Journal on Scientific Computing, Vol. 38, Iss. 5 (2016).

Parameters:
Gnetworkit.Graph

The input graph, must be undirected.

secondThe second parameter contains information about b-values of nodes. This can either be given as

single value (int), indicating the same b-value for all nodes. Other options: list of b-values for each node, str-based path to file containing b-values.

buildBMatching()

Creates the b-matching for given graph G. Function run() automatically invokes buildMatching. After invoking buildBMatching(), use getBMatching() to retrieve the resulting b-matching.

class networkit.matching.DynamicBSuitorMatcher(G, second)

Bases: BSuitorMatcher, DynAlgorithm

Implementation from the algorithm from “A Fully-dynamic Approximation Algorithm for Maximum Weight b-Matchings in Graphs” from Proceedings of The Thirteenth International Conference on Complex Networks and their Applications 2024 by Fabian Brandt-Tumescheit, Frieda Gerharz and Henning Meyerhenke. The algorithm dynamically updates the b-matching based on the b-Suitor algorithm by Khan et al. The solution is the same as a complete recomputation of the b-Suitor b-matching.

Parameters:
Gnetworkit.Graph

An unweighted graph.

secondThe second parameter contains information about b-values of nodes. This can either be given as

single value (int), indicating the same b-value for all nodes. Other options: list of b-values for each node, str-based path to file containing b-values.

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