scipy.sparse.csgraph.maximum_bipartite_matching¶
- scipy.sparse.csgraph.maximum_bipartite_matching()¶
Returns an array of row or column permutations that makes the diagonal of a nonsingular square CSC sparse matrix zero free.
Such a permutation is always possible provided that the matrix is nonsingular. This function looks at the structure of the matrix only. The input matrix will be converted to CSC matrix format if necessary.
Parameters: graph : sparse matrix
Input sparse in CSC format
perm_type : str, {‘row’, ‘column’}
Type of permutation to generate.
Returns: perm : ndarray
Array of row or column permutations.
Notes
This function relies on a maximum cardinality bipartite matching algorithm based on a breadth-first search (BFS) of the underlying graph.
New in version 0.15.0.
References
I. S. Duff, K. Kaya, and B. Ucar, “Design, Implementation, and Analysis of Maximum Transversal Algorithms”, ACM Trans. Math. Softw. 38, no. 2, (2011).