Class EdmondsBlossomShrinking<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - 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.
    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
    • Field Detail

      • matching

        private java.util.Set<E> matching
        Deprecated.
      • match

        private java.util.Map<V,​V> match
        Deprecated.
      • path

        private java.util.Map<V,​V> path
        Deprecated.
      • contracted

        private java.util.Map<V,​V> contracted
        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 interface MatchingAlgorithm<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
      • findPath

        private V findPath​(V root)
        Deprecated.
      • markPath

        private void markPath​(V v,
                              V child,
                              V stem,
                              java.util.Set<V> blossom)
        Deprecated.
      • lowestCommonAncestor

        private V lowestCommonAncestor​(V a,
                                       V b)
        Deprecated.