LAPJV is not giving the correct result.
Nobody has claimed this yet.
- Dominant language
- C++
- Stars
- 278
- Forks
- 36
- PR merge metrics
- No merged PRs in 30d
Description
I followed the instructions and installed the package using pip3 install lapjv. However, when I test it with a simple matrix, the results are incorrect. I compared the results with scipy linear_sum_assignment.
from lapjv import lapjv
from scipy.optimize import linear_sum_assignment as lsa
import numpy as np
# cost_matrix = np.array([[9.0, 7.6, 7.5,100.0],[3.5, 8.5, 5.5,100.0],[12.5, 9.5, 9.0,100.0],[4.5, 11.0, 9.5,100.0]])
cost_matrix = np.array([[9.0, 7.6, 7.5,7.0],[3.5, 8.5, 5.5,6.5],[12.5, 9.5, 9.0,10.5],[4.5, 11.0, 9.5,11.5]])
row_ind, col_ind, _ = lapjv(cost_matrix)
cost_tot = 0
print("===LAPJV sol: ")
for id in range (len(row_ind)):
i = row_ind[id]
j = col_ind[id]
print (f"track {i} match det {j} cost {cost_matrix[i,j]}")
cost_tot += cost_matrix[i,j]
print (f"cost total = {cost_tot}")
row_ind1, col_ind1= lsa(cost_matrix)
print("===LSA sol: ")
cost_tot = 0
for id in range (len(row_ind)):
i = row_ind1[id]
j = col_ind1[id]
print (f"track {i} match det {j} cost {cost_matrix[i,j]}")
cost_tot += cost_matrix[i,j]
print (f"cost total = {cost_tot}")
I get
===LAPJV sol:
track 3 match det 3 cost 11.5
track 2 match det 2 cost 9.0
track 1 match det 1 cost 8.5
track 0 match det 0 cost 9.0
cost total = 38.0
===LSA sol:
track 0 match det 3 cost 7.0
track 1 match det 2 cost 5.5
track 2 match det 1 cost 9.5
track 3 match det 0 cost 4.5
cost total = 26.5
I also took the cpp code in the repo created a main. The project is here lapjv-cpp.zip and run the same squared matrix and I get this
9.000000 7.600000 7.500000 7.000000
3.500000 8.500000 5.500000 6.500000
12.500000 9.500000 9.000000 10.500000
4.500000 11.000000 9.500000 11.500000
start
Beginning lapjv method.
AVX2: enabled
lapjv: COLUMN REDUCTION finished
lapjv: REDUCTION TRANSFER finished
lapjv: AUGMENTING ROW REDUCTION 1 / 2
lapjv: AUGMENTING ROW REDUCTION 2 / 2
lapjv: AUGMENT SOLUTION finished
lapjv: optimal cost calculated
Track 2 assigned to detect 3. Cost: 10.5
Track 1 assigned to detect 1. Cost: 8.5
Track 3 assigned to detect 0. Cost: 4.5
Track 0 assigned to detect 2. Cost: 7.5
Total cost = 31
dim 4 - lap cost 3.500 - runtime 0.017 ms
Something is up with this code. I would appreciate any help with it. Am I missing something?
Contributor guide
No contributing guide indexed for this repository
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start by running the Python example from the issue and the attached C++ main, then compare both assignments and total costs with scipy.optimize.linear_sum_assignment. Trace the lapjv entry point and the native implementation used by the package; done means the Python and C++ results agree with the reference assignment for this matrix.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp, numpy, python
- Domain
- tooling
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100