Package org.jgrapht.alg.matching
Class PathGrowingWeightedMatching.DynamicProgrammingPathSolver
- java.lang.Object
-
- org.jgrapht.alg.matching.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
-
Constructor Summary
Constructors Constructor Description DynamicProgrammingPathSolver()
-
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.
-
-
-
Field Detail
-
WORK_ARRAY_INITIAL_SIZE
private static final int WORK_ARRAY_INITIAL_SIZE
- See Also:
- Constant Field Values
-
a
private double[] a
-
-
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
-
-