org.jgrapht.alg.matching

Class EdmondsBlossomShrinking<V,E>

java.lang.Object

org.jgrapht.alg.matching.EdmondsBlossomShrinking<V,E>

Type Parameters:

V - the graph vertex type

E - the graph edge type

All Implemented Interfaces:

MatchingAlgorithm<V,E>

Deprecated.

Deprecated in favor of the more efficient EdmondsMaximumCardinalityMatching.

@Deprecated
public class EdmondsBlossomShrinking<V,E>
extends Object
implements MatchingAlgorithm<V,E>

An implementation of Edmonds Blossom Shrinking algorithm for constructing maximum matchings on graphs. The algorithm runs in time O(V^4).

Since:

Jan 24, 2012

Author:

Alejandro R. Lopez del Huerto

Nested Class Summary

Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.MatchingAlgorithm

MatchingAlgorithm.Matching<V,E>, MatchingAlgorithm.MatchingImpl<V,E>

Field Summary

Fields inherited from interface org.jgrapht.alg.interfaces.MatchingAlgorithm

DEFAULT_EPSILON

Constructor Summary

Constructors

Constructor and Description
EdmondsBlossomShrinking(Graph<V,E> graph) Deprecated. Construct an instance of the Edmonds blossom shrinking algorithm.

Method Summary

Modifier and Type	Method and Description
MatchingAlgorithm.Matching<V,E>	getMatching() Deprecated. Compute a matching for a given graph.

Methods inherited from class java.lang.Object

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

Methods inherited from interface org.jgrapht.alg.interfaces.MatchingAlgorithm

computeMatching

Constructor Detail

EdmondsBlossomShrinking

public EdmondsBlossomShrinking(Graph<V,E> graph)

Deprecated.

Construct an instance of the Edmonds blossom shrinking algorithm.

Parameters:

graph - the input graph

Throws:

IllegalArgumentException - if the graph is not undirected

Method Detail

getMatching

public MatchingAlgorithm.Matching<V,E> getMatching()

Deprecated.

Compute a matching for a given graph.

Specified by:

getMatching in interface MatchingAlgorithm<V,E>

Returns:

a matching