public class LAPJV extends Object implements OutputAlgorithm<int[]>, Benchmark
We rely on the SparseCostMatrix class to represent these costs. The
implementation itself is an unlikely mix between:
Volgenant. Linear and semi-assignment problems:
A core oriented approach. Computers & Operations Research (1996) vol. 23 (10)
pp. 917-932);Computation time performance degrades significantly compared to the non-sparse version. Benchmarks show that when increasing the density from 0.1% to 70%, the computation time increased by a factor ranging from 1.5 to 7 compared to the non-sparse version. For a given density, the comparison depends very weakly on the matrix size.
| Constructor and Description |
|---|
LAPJV(SparseCostMatrix cm)
Instantiates a new Jonker-Volgenant algorithm for the specified sparse
cost matrix.
|
| Modifier and Type | Method and Description |
|---|---|
boolean |
checkInput() |
String |
getErrorMessage() |
long |
getProcessingTime() |
int[] |
getResult()
Returns JVS results as row assignments.
|
boolean |
process() |
String |
resultToString() |
String |
resultToString(List<?> rows,
List<?> cols) |
public LAPJV(SparseCostMatrix cm)
cm - the cost matrix of the linear assignment problem to solve.public boolean checkInput()
checkInput in interface Algorithmpublic String getErrorMessage()
getErrorMessage in interface Algorithmpublic long getProcessingTime()
getProcessingTime in interface Benchmarkpublic int[] getResult()
i is
associated to the column x[i] in the cost matrix.getResult in interface OutputAlgorithm<int[]>int[] array. This array is
re-instantiated upon calling process().public String resultToString()
Copyright © 2015–2021 Fiji. All rights reserved.