Class EdmondsBlossomShrinking<V,​E>

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

      • match

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

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

        private java.util.Map<V,​V> contracted
    • Constructor Detail

      • EdmondsBlossomShrinking

        public EdmondsBlossomShrinking​(Graph<V,​E> graph)
        Construct an instance of the Edmonds blossom shrinking algorithm.
        Parameters:
        graph - the input graph
        Throws:
        java.lang.IllegalArgumentException - if the graph is not undirected
    • Method Detail

      • findMatch

        private java.util.Set<E> findMatch()
        Runs the algorithm on the input graph and returns the match edge set.
        Returns:
        set of edges
      • findPath

        private V findPath​(V root)
      • markPath

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

        private V lowestCommonAncestor​(V a,
                                       V b)