Class DenseEdmondsMaximumCardinalityMatching.Levels

  • Enclosing class:
    DenseEdmondsMaximumCardinalityMatching<V,​E>

    private static class DenseEdmondsMaximumCardinalityMatching.Levels
    extends java.lang.Object
    Storage of the forest, even and odd levels. We explicitly maintain a dirty mark in order to be able to cleanup only the values that we have changed. This is important when the graph is sparse to avoid performing an $O(n)$ operation per augmentation.
    • Field Summary

      Fields 
      Modifier and Type Field Description
      private java.util.List<java.lang.Integer> dirty  
      private int[] even  
      private int[] odd  
    • Constructor Summary

      Constructors 
      Constructor Description
      Levels​(int n)  
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      int getEven​(int v)  
      int getOdd​(int v)  
      boolean isEven​(int v)  
      boolean isOdd​(int v)  
      boolean isOddOrUnreached​(int v)  
      void reset()  
      void setEven​(int v, int value)  
      void setOdd​(int v, int value)  
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Field Detail

      • even

        private int[] even
      • odd

        private int[] odd
      • dirty

        private java.util.List<java.lang.Integer> dirty
    • Constructor Detail

      • Levels

        public Levels​(int n)
    • Method Detail

      • getEven

        public int getEven​(int v)
      • setEven

        public void setEven​(int v,
                            int value)
      • getOdd

        public int getOdd​(int v)
      • setOdd

        public void setOdd​(int v,
                           int value)
      • isEven

        public boolean isEven​(int v)
      • isOddOrUnreached

        public boolean isOddOrUnreached​(int v)
      • isOdd

        public boolean isOdd​(int v)
      • reset

        public void reset()