scipy.sparse.csgraph.maximum_bipartite_matching

scipy.sparse.csgraph.maximum_bipartite_matching(graph, perm_type='row')

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).

Examples

>>> from scipy.sparse import csr_matrix
>>> from scipy.sparse.csgraph import maximum_bipartite_matching

>>> graph = [
... [0, 1 , 2, 0],
... [1, 0, 0, 1],
... [2, 0, 0, 3],
... [0, 1, 3, 0]
... ]
>>> graph = csr_matrix(graph)
>>> print(graph)
  (0, 1)    1
  (0, 2)    2
  (1, 0)    1
  (1, 3)    1
  (2, 0)    2
  (2, 3)    3
  (3, 1)    1
  (3, 2)    3

>>> maximum_bipartite_matching(graph, perm_type='row')
array([1, 0, 3, 2], dtype=int32)