jdmoorman / laptools Goto Github PK
View Code? Open in Web Editor NEWFast Assignment Problem Solvers in Python
License: MIT License
Fast Assignment Problem Solvers in Python
License: MIT License
When calling an action from the marketplace such as actions/checkout@master
, it is recommended practice to pin the action to a particular version such as actions/checkout@v1
. This alleviates the risk of master
introducing a breaking change or vulnerability.
The relevant workflow files are in the .github/workflow
directory.
In particular, Thomas noticed that np.argsort takes up a lot of the time.
This way we will not need to take the same arguments into every single function.
Our code should be based on the fastest available with graphs to prove it.
Given the solution to an unconstrained problem, we should be able to solve the constrained problem super quickly. You can use the algorithm from the paper you showed me as a basis. https://www.ri.cmu.edu/pub_files/pub4/mills_tettey_g_ayorkor_2007_3/mills_tettey_g_ayorkor_2007_3.pdf
A clear description of the bug
What did you expect to happen instead?
A minimal example that exhibits the behavior.
Any additional information about your environment
Please provide a use case to help us understand your request in context
Please describe your ideal solution
Please describe any alternatives you've considered, even if you've dismissed them
A clear description of the bug
What did you expect to happen instead?
A minimal example that exhibits the behavior.
Any additional information about your environment
Currently nothing is explained in the docs. We should explain everything in the docs once the API settles down.
Please provide a use case to help us understand your request in context
Please describe your ideal solution
Please describe any alternatives you've considered, even if you've dismissed them
We are getting some datatype incompatibility issues on windows only, but none of the devs have windows machines. We have friends though, and once our friends come to the rescue we will bring back windows support.
Apparently the solvers break if there is a row or maybe a column of all infinity. We should test for this and handle it somehow.
laptools.lap.solve(cost_matrix)
laptools.lap.solve(cost_matrix, return_duals=True)
laptools.clap.costs(cost_matrix)
A clear description of the bug
Based on my understanding of the clap.costs() definition, it should solve a constrained linear assignment problem. Therefore, I believe the output of clap.costs() should be consistent with the output of the following naive_cost() function for the same input. However, I don't understand why my test code below fails to pass.
A minimal example that exhibits the behavior.
import numpy as np
from laptools import lap
from laptools import clap
def one_hot(idx, length):
one_hot = np.zeros(length, dtype=np.bool)
one_hot[idx] = True
return one_hot
def naive_costs(cost_matrix):
"""An naive algorithm of solving all constraint LAPs. """
n_rows, n_cols = cost_matrix.shape
total_costs = np.full(cost_matrix.shape, np.inf)
for i in range(n_rows):
for j in range(n_cols):
if cost_matrix[i,j] == np.inf:
continue
sub_row_ind = ~one_hot(i, n_rows)
sub_col_ind = ~one_hot(j, n_cols)
sub_cost_matrix = cost_matrix[sub_row_ind, :][:, sub_col_ind]
row_idx, col_idx = lap.solve(sub_cost_matrix)
sub_total_cost = sub_cost_matrix[row_idx, col_idx].sum()
total_costs[i, j] = cost_matrix[i, j] + sub_total_cost
return total_costs
cost = [[0. , np.inf, np.inf],
[np.inf, 0. , 0.5],
[np.inf, 1. , 0. ]]
cost = np.array(cost)
cost_clap1 = clap.costs(cost)
cost_clap2 = naive_costs(cost)
assert np.array_equal(cost_clap1, cost_clap2)
We have an implementation of costs
that computes the constrained cost for every possible constraint. This should move over here.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.