Class PathGrowingWeightedMatching.DynamicProgrammingPathSolver

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

class PathGrowingWeightedMatching.DynamicProgrammingPathSolver extends Object
Helper class for repeatedly solving the maximum weight matching on paths. The work array used in the dynamic programming algorithm is reused between invocations. In case its size is smaller than the path provided, its length is increased. This class is not thread-safe.
  • Field Details

    • WORK_ARRAY_INITIAL_SIZE

      private static final int WORK_ARRAY_INITIAL_SIZE
      See Also:
    • a

      private double[] a
  • Constructor Details

    • DynamicProgrammingPathSolver

      DynamicProgrammingPathSolver()
  • Method Details

    • getMaximumWeightMatching

      public Pair<Double,Set<E>> getMaximumWeightMatching(Graph<V,E> g, LinkedList<E> path)
      Find the maximum weight matching of a path using dynamic programming.
      Parameters:
      path - a list of edges. The code assumes that the list of edges is a valid simple path, and that is not a cycle.
      Returns:
      a maximum weight matching of the path