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