# 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
graphsparse matrix

Input sparse in CSC format

perm_typestr, {‘row’, ‘column’}

Type of permutation to generate.

Returns
permndarray

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)


#### Previous topic

scipy.sparse.csgraph.reverse_cuthill_mckee

#### Next topic

scipy.sparse.csgraph.structural_rank