Class DenseEdmondsMaximumCardinalityMatching.Levels

java.lang.Object
org.jgrapht.alg.matching.DenseEdmondsMaximumCardinalityMatching.Levels
Enclosing class:
DenseEdmondsMaximumCardinalityMatching<V,E>

private static class DenseEdmondsMaximumCardinalityMatching.Levels extends 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 Details

    • even

      private int[] even
    • odd

      private int[] odd
    • dirty

      private List<Integer> dirty
  • Constructor Details

    • Levels

      public Levels(int n)
  • Method Details

    • 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()