Package com.jgalgo

Interface MaximumMatching

public interface MaximumMatching

Maximum matching algorithm.

Given a graph \(G=(V,E)\), a matching is a sub set of edges \(M\) such that any vertex in \(V\) has at most one adjacent edge in \(M\). A maximum cardinality matching is a matching with the maximum number of edges in \(M\). A maximum weighted matching is a matching with the maximum edges weight sum with respect to some weight function. A perfect maximum weighted matching is a matching with the maximum edges weight sum out of all the matching with are maximum cardinality matching. Note that the weight of a perfect maximum matching is smaller or equal to the weight of a maximum weight matching.

Author:

Barak Ugav

See Also:

Wikipedia

Nested Class Summary

Nested Classes

Modifier and Type	Interface	Description
static interface	MaximumMatching.Builder	A builder for MaximumMatching objects.

Method Summary

Modifier and Type	Method	Description
Matching	computeMaximumCardinalityMatching(Graph g)	Compute the maximum matching of unweighted undirected graph.
Matching	computeMaximumWeightedMatching(Graph g, WeightFunction w)	Compute the maximum weighted matching of a weighted undirected graph.
Matching	computeMaximumWeightedPerfectMatching(Graph g, WeightFunction w)	Compute the maximum perfect matching of a weighted undirected graph.
static MaximumMatching.Builder	newBuilder()	Create a new maximum matching algorithm builder.

Method Detail

computeMaximumCardinalityMatching

Matching computeMaximumCardinalityMatching(Graph g)

Compute the maximum matching of unweighted undirected graph.

Parameters:

g - an undirected graph

Returns:

the computed matching

Throws:

IllegalArgumentException - if g is a directed graph

computeMaximumWeightedMatching

Matching computeMaximumWeightedMatching(Graph g,
                                        WeightFunction w)

Compute the maximum weighted matching of a weighted undirected graph.

Parameters:

g - an undirected graph

w - an edge weight function

Returns:

the computed matching

Throws:

IllegalArgumentException - if g is a directed graph

computeMaximumWeightedPerfectMatching

Matching computeMaximumWeightedPerfectMatching(Graph g,
                                               WeightFunction w)

Compute the maximum perfect matching of a weighted undirected graph.

Parameters:

g - an undirected graph

w - an edge weight function

Returns:

the computed perfect matching, or the maximal one if no perfect one found

Throws:

IllegalArgumentException - if g is a directed graph

newBuilder

static MaximumMatching.Builder newBuilder()

Create a new maximum matching algorithm builder.

This is the recommended way to instantiate a new MaximumMatching object.

Returns:

a new builder that can build MaximumMatching objects