linear_sum_assignment(cost_matrix, maximize=False)
The linear sum assignment problem is also known as minimum weight matching in bipartite graphs. A problem instance is described by a matrix C, where each C[i,j] is the cost of matching vertex i of the first partite set (a "worker") and vertex j of the second set (a "job"). The goal is to find a complete assignment of workers to jobs of minimal cost.
Formally, let X be a boolean matrix where $X[i,j] = 1$ iff row i is assigned to column j. Then the optimal assignment has cost
$$\min \sum_i \sum_j C_{i,j} X_{i,j}$$where, in the case where the matrix X is square, each row is assigned to exactly one column, and each column to exactly one row.
This function can also solve a generalization of the classic assignment problem where the cost matrix is rectangular. If it has more rows than columns, then not every row needs to be assigned to a column, and vice versa.
This implementation is a modified Jonker-Volgenant algorithm with no initialization, described in ref. .
The cost matrix of the bipartite graph.
Calculates a maximum weight matching if true.
An array of row indices and one of corresponding column indices giving the optimal assignment. The cost of the assignment can be computed as cost_matrix[row_ind, col_ind].sum()
. The row indices will be sorted; in the case of a square cost matrix they will be equal to numpy.arange(cost_matrix.shape[0])
.
Solve the linear sum assignment problem.
scipy.sparse.csgraph.min_weight_full_bipartite_matching
for sparse inputs
>>> cost = np.array([[4, 1, 3], [2, 0, 5], [3, 2, 2]])
... from scipy.optimize import linear_sum_assignment
... row_ind, col_ind = linear_sum_assignment(cost)
... col_ind array([1, 0, 2])
>>> cost[row_ind, col_ind].sum() 5See :
The following pages refer to to this document either explicitly or contain code examples using this.
scipy.optimize._lsap.linear_sum_assignment
scipy.sparse.csgraph._matching.min_weight_full_bipartite_matching
Hover to see nodes names; edges to Self not shown, Caped at 50 nodes.
Using a canvas is more power efficient and can get hundred of nodes ; but does not allow hyperlinks; , arrows or text (beyond on hover)
SVG is more flexible but power hungry; and does not scale well to 50 + nodes.
All aboves nodes referred to, (or are referred from) current nodes; Edges from Self to other have been omitted (or all nodes would be connected to the central node "self" which is not useful). Nodes are colored by the library they belong to, and scaled with the number of references pointing them