Package org.jgrapht.alg.matching
Class EdmondsBlossomShrinking<V,E>
- java.lang.Object
-
- org.jgrapht.alg.matching.EdmondsBlossomShrinking<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
MatchingAlgorithm<V,E>
public class EdmondsBlossomShrinking<V,E> extends java.lang.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
-
-
Nested Class Summary
-
Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.MatchingAlgorithm
MatchingAlgorithm.Matching<E>, MatchingAlgorithm.MatchingImpl<E>
-
-
Field Summary
Fields Modifier and Type Field Description private java.util.Map<V,V>
contracted
private UndirectedGraph<V,E>
graph
private java.util.Map<V,V>
match
private java.util.Map<V,V>
path
-
Fields inherited from interface org.jgrapht.alg.interfaces.MatchingAlgorithm
DEFAULT_EPSILON
-
-
Constructor Summary
Constructors Constructor Description EdmondsBlossomShrinking(Graph<V,E> graph)
Construct an instance of the Edmonds blossom shrinking algorithm.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description MatchingAlgorithm.Matching<E>
computeMatching()
Compute a matching for a given graph.private java.util.Set<E>
findMatch()
Runs the algorithm on the input graph and returns the match edge set.private V
findPath(V root)
private V
lowestCommonAncestor(V a, V b)
private void
markPath(V v, V child, V stem, java.util.Set<V> blossom)
-
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
getMatching
-
-
-
-
Method Detail
-
computeMatching
public MatchingAlgorithm.Matching<E> computeMatching()
Compute a matching for a given graph.- Specified by:
computeMatching
in interfaceMatchingAlgorithm<V,E>
- Returns:
- a matching
-
findMatch
private java.util.Set<E> findMatch()
Runs the algorithm on the input graph and returns the match edge set.- Returns:
- set of edges
-
-