Package com.jgalgo.alg.match

Class MatchingAlgoAbstract

java.lang.Object

com.jgalgo.alg.match.MatchingAlgoAbstract

All Implemented Interfaces:

MatchingAlgo

Direct Known Subclasses:

MatchingAlgoAbstractBasedMaximum, MatchingAlgoAbstractBasedMinimum, MatchingAlgoAbstractCardinality

public abstract class MatchingAlgoAbstract
extends Object
implements MatchingAlgo

Abstract class for computing matchings in graphs.

The class implements the interface by solving the problem on the index graph and then maps the results back to the original graph. The implementation for index graphs is abstract and left to the subclasses.

Author:

Barak Ugav

Nested Class Summary

Nested classes/interfaces inherited from interface com.jgalgo.alg.match.MatchingAlgo

MatchingAlgo.Builder

Constructor Summary

Constructors

Constructor	Description
MatchingAlgoAbstract()	Default constructor.

Method Summary

Modifier and Type	Method	Description
<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.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

MatchingAlgoAbstract

public MatchingAlgoAbstract()

Default constructor.

Method Detail

computeMaximumMatching

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

Description copied from interface: MatchingAlgo

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.

Specified by:

computeMaximumMatching in interface MatchingAlgo

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

g - an undirected graph

w - an edge weight function

Returns:

the computed matching

computeMinimumMatching

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

Description copied from interface: MatchingAlgo

Compute the minimum weighted matching of a weighted undirected graph.

If g is IntGraph, the returned object is IMatching.

Specified by:

computeMinimumMatching in interface MatchingAlgo

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

g - an undirected graph

w - an edge weight function

Returns:

the computed matching

computeMaximumPerfectMatching

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

Description copied from interface: MatchingAlgo

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.

Specified by:

computeMaximumPerfectMatching in interface MatchingAlgo

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

computeMinimumPerfectMatching

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

Description copied from interface: MatchingAlgo

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 MatchingAlgo.computeMaximumPerfectMatching(Graph, WeightFunction).

If g is IntGraph, the returned object is IMatching.

Specified by:

computeMinimumPerfectMatching in interface MatchingAlgo

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