Bases: Algorithm
Abstract base class for matching algorithms
Returns the matching.
Current b-matching of graph.
networkit.BMatching
Bases: object
Implements a graph matching. Create a new matching data structure for z elements.
List containing the b-values for all nodes.
Check if the nodes u and v are matched to each other.
u (int) – The first node.
v (int) – The second node.
True if node u and v are matched to each other.
bool
Get the b-value for each node.
A list, containing the b-values (int) for each node.
list(int)
Get the set of matches for each node.
Returns the set of matches for each node.
list(set)
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.
True if this is a proper matching.
bool
Check if node u is unmatched.
u (int) – The input node.
True if u has no matching partner.
bool
Set two nodes u and v as each others matching partners.
u (int) – The first node.
v (int) – The second node.
Removes all entries from the b-matching data structure
Get the number of edges in this matching.
Total number of edges in the matching.
int
Reset the two nodes u and v to unmatched.
u (int) – The first node.
v (int) – The second node.
Get total weight of edges in this matching.
Total weight of edges in this matching.
float
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).
The input graph, must be undirected.
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.
Creates the b-matching for given graph G. Function run() automatically invokes buildMatching. After invoking buildBMatching(), use getBMatching() to retrieve the resulting b-matching.
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.
An unweighted graph.
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.
Bases: Algorithm
Abstract base class for matching algorithms
Returns the matching.
Current Matching of graph.
networkit.Matching
Bases: object
Implements a graph matching. Create a new matching data structure for z elements.
Maximum number of nodes. Default: 0
Check if the nodes u and v are matched to each other.
u (int) – The first node.
v (int) – The second node.
True if node u and v are matched to each other.
bool
Get the vector storing the data.
Vector indexed by node id containing the node id of mate or networkit.none if unmatched
list(int or None)
Check if node u is matched.
u (int) – The input node.
True if u has a matching partner.
bool
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.
G (networkit.Graph) – Graph to be checked.
True if this is a proper matching.
bool
Set two nodes u and v as each others matching partners.
u (int) – The first node.
v (int) – The second node.
Get the matched neighbor of v if it exists, otherwise +inf.
v (int) – The input node.
Matching partner of v if it exists, otherwise +inf.
int
Get the number of edges in this matching.
G (networkit.Graph) – The input graph.
Total number of edges in the matching.
int
Convert matching to a Partition object where matched nodes belong to the same subset and unmatched nodes belong to a singleton subset.
G (networkit.Graph) – The corresponding graph.
The resulting partition.
networkit.Partition
Reset the two nodes u and v to unmatched.
u (int) – The first node.
v (int) – The second node.
Get total weight of edges in this matching.
G (networkit.Graph) – The corresponding graph.
Total weight of edges in this matching.
float
Bases: Matcher
Path growing matching algorithm as described by Hougardy and Drake. Computes an approximate maximum weight matching with guarantee 1/2.
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.
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