src-d / src-d/lapjv

LAPJV is not giving the correct result.

Open
#83 5 comments 0 reactions 0 assignees View on GitHub

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

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.