Class PathGrowingWeightedMatching.DynamicProgrammingPathSolver

  • Enclosing class:
    PathGrowingWeightedMatching<V,​E>

    class PathGrowingWeightedMatching.DynamicProgrammingPathSolver
    extends java.lang.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 Summary

      Fields 
      Modifier and Type Field Description
      private double[] a  
      private static int WORK_ARRAY_INITIAL_SIZE  
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      Pair<java.lang.Double,​java.util.Set<E>> getMaximumWeightMatching​(Graph<V,​E> g, java.util.LinkedList<E> path)
      Find the maximum weight matching of a path using dynamic programming.
      • Methods inherited from class java.lang.Object

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

      • WORK_ARRAY_INITIAL_SIZE

        private static final int WORK_ARRAY_INITIAL_SIZE
        See Also:
        Constant Field Values
      • a

        private double[] a
    • Constructor Detail

      • DynamicProgrammingPathSolver

        DynamicProgrammingPathSolver()
    • Method Detail

      • getMaximumWeightMatching

        public Pair<java.lang.Double,​java.util.Set<E>> getMaximumWeightMatching​(Graph<V,​E> g,
                                                                                      java.util.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