Hacktoberfest 2026: the issues maintainers tagged for October, open and beginner-friendly. Browse Hacktoberfest issues

LAPJV is not giving the correct result.

Open
  • Is something wrong?
#83 5 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Assessment

Difficulty
4/5
Estimated time
3-5 days
Newbie friendliness
35/100
Issue type
Bug
Clarity
Mostly clear
Activity status
Stale
Tech stack
cpp, numpy, python
Domain
tooling

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.

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?

Dominant language
C++
Stars
278
Forks
36
Avg merge
1h 29m
Merged PRs (30d)
1

Getting set up

This project ships no dev container, Dockerfile or contributing guide, so setting up is up to you: start from its README, and see our first-contribution guide for the general steps.

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.

More from src-d/lapjv

All issues in src-d/lapjv

Similar issues

More C++ issues

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.