Package com.jgalgo.alg.match

Interface MatchingAlgo

All Known Implementing Classes:

MatchingAlgoAbstract, MatchingAlgoAbstractBasedMaximum, MatchingAlgoAbstractBasedMinimum, MatchingAlgoAbstractCardinality, MatchingCardinalityBipartiteHopcroftKarp, MatchingCardinalityGabow1976, MatchingWeightedBipartiteHungarianMethod, MatchingWeightedBipartiteSssp, MatchingWeightedBlossomV, MatchingWeightedGabow1990, MatchingWeightedGabow1990Simpler

public interface MatchingAlgo

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.

Use newInstance() to get a default implementation of this interface. A builder obtained via builder() may support different options to obtain different implementations.

Author:

Barak Ugav

See Also:

Wikipedia

Nested Class Summary

Nested Classes

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

Method Summary

Modifier and Type	Method	Description
static MatchingAlgo.Builder	builder()	Create a new matching algorithm builder.
<V,E> Matching<V,E>	computeMaximumMatching(Graph<V,E> g, WeightFunction<E> w)	Compute the maximum weighted matching of a weighted undirected graph.
<V,E> Matching<V,E>	computeMaximumPerfectMatching(Graph<V,E> g, WeightFunction<E> w)	Compute the maximum perfect matching of a weighted undirected graph.
<V,E> Matching<V,E>	computeMinimumMatching(Graph<V,E> g, WeightFunction<E> w)	Compute the minimum weighted matching of a weighted undirected graph.
<V,E> Matching<V,E>	computeMinimumPerfectMatching(Graph<V,E> g, WeightFunction<E> w)	Compute the minimum perfect matching of a weighted undirected graph.
static MatchingAlgo	newInstance()	Create a new matching algorithm object.

Method Detail

computeMaximumMatching

<V,E> Matching<V,E> computeMaximumMatching(Graph<V,E> g,
                                                       WeightFunction<E> w)

Compute the maximum weighted matching of a weighted undirected graph.

To compute the maximum cardinality (non weighted) matching, pass null instead of the weight function w.

If g is IntGraph, the returned object is IMatching.

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

g - an undirected graph

w - an edge weight function

Returns:

the computed matching

Throws:

IllegalArgumentException - if g is a directed graph

computeMinimumMatching

<V,E> Matching<V,E> computeMinimumMatching(Graph<V,E> g,
                                                       WeightFunction<E> w)

Compute the minimum weighted matching of a weighted undirected graph.

If g is IntGraph, the returned object is IMatching.

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

g - an undirected graph

w - an edge weight function

Returns:

the computed matching

Throws:

IllegalArgumentException - if g is a directed graph

computeMaximumPerfectMatching

<V,E> Matching<V,E> computeMaximumPerfectMatching(Graph<V,E> g,
                                                              WeightFunction<E> 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.

To compute the maximum cardinality (non weighted) perfect matching, pass null instead of the weight function w.

If g is IntGraph, the returned object is IMatching.

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

g - an undirected graph

w - an edge weight function

Returns:

the computed perfect matching

Throws:

IllegalArgumentException - if g is a directed graph

computeMinimumPerfectMatching

<V,E> Matching<V,E> computeMinimumPerfectMatching(Graph<V,E> g,
                                                              WeightFunction<E> 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.

To compute the maximum cardinality (non weighted) matching, pass null instead of the weight function w. Note that this is equivalent to computeMaximumPerfectMatching(Graph, WeightFunction).

If g is IntGraph, the returned object is IMatching.

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

g - an undirected graph

w - an edge weight function

Returns:

the computed perfect matching

Throws:

IllegalArgumentException - if g is a directed graph

newInstance

static MatchingAlgo newInstance()

Create a new matching algorithm object.

This is the recommended way to instantiate a new MatchingAlgo object. The MatchingAlgo.Builder might support different options to obtain different implementations.

Returns:

a default implementation of MatchingAlgo

builder

static MatchingAlgo.Builder builder()

Create a new matching algorithm builder.

Use newInstance() for a default implementation.

Returns:

a new builder that can build MatchingAlgo objects