Package com.jgalgo

Interface MatchingAlgorithm

public interface MatchingAlgorithm

Maximum/minimum 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/minimum weighted matching is a matching with the maximum/minimum edges weight sum with respect to some weight function. A perfect maximum/minimum weighted matching is a matching with the maximum/minimum edges weight sum out of all the matchings in which each vertex has an adjacent matched edge. 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	MatchingAlgorithm.Builder	A builder for MatchingAlgorithm 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.
Matching	computeMinimumWeightedMatching(Graph g, WeightFunction w)	Compute the minimum weighted matching of a weighted undirected graph.
Matching	computeMinimumWeightedPerfectMatching(Graph g, WeightFunction w)	Compute the minimum perfect matching of a weighted undirected graph.
static MatchingAlgorithm.Builder	newBuilder()	Create a new 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

computeMinimumWeightedMatching

Matching computeMinimumWeightedMatching(Graph g,
                                        WeightFunction w)

Compute the minimum 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.

A perfect matching in which each vertex has an adjacent matched edge is assumed to exist in the input graph, and if no such matching exist the behavior is undefined.

Parameters:

g - an undirected graph

w - an edge weight function

Returns:

the computed perfect matching

Throws:

IllegalArgumentException - if g is a directed graph

computeMinimumWeightedPerfectMatching

Matching computeMinimumWeightedPerfectMatching(Graph g,
                                               WeightFunction w)

Compute the minimum perfect matching of a weighted undirected graph.

A perfect matching in which each vertex has an adjacent matched edge is assumed to exist in the input graph, and if no such matching exist the behavior is undefined.

Parameters:

g - an undirected graph

w - an edge weight function

Returns:

the computed perfect matching

Throws:

IllegalArgumentException - if g is a directed graph

newBuilder

static MatchingAlgorithm.Builder newBuilder()

Create a new matching algorithm builder.

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

Returns:

a new builder that can build MatchingAlgorithm objects