maximum_bipartite_matching(graph, perm_type='row')
This function implements the Hopcroft--Karp algorithm . Its time complexity is $O(\lvert E \rvert \sqrt{\lvert V \rvert})$ , and its space complexity is linear in the number of rows. In practice, this asymmetry between rows and columns means that it can be more efficient to transpose the input if it contains more columns than rows.
By Konig's theorem, the cardinality of the matching is also the number of vertices appearing in a minimum vertex cover of the graph.
Note that if the sparse representation contains explicit zeros, these are still counted as edges.
The implementation was changed in SciPy 1.4.0 to allow matching of general bipartite graphs, where previous versions would assume that a perfect matching existed. As such, code written against 1.4.0 will not necessarily work on older versions.
Input sparse in CSR format whose rows represent one partition of the graph and whose columns represent the other partition. An edge between two vertices is indicated by the corresponding entry in the matrix existing in its sparse representation.
Which partition to return the matching in terms of: If 'row'
, the function produces an array whose length is the number of columns in the input, and whose $j$
'th element is the row matched to the $j$
'th column. Conversely, if perm_type
is 'column'
, this returns the columns matched to each row.
A matching of the vertices in one of the two partitions. Unmatched vertices are represented by a -1
in the result.
Returns a matching of a bipartite graph whose cardinality is as least that of any given matching of the graph.
>>> from scipy.sparse import csr_matrix
... from scipy.sparse.csgraph import maximum_bipartite_matching
As a simple example, consider a bipartite graph in which the partitions contain 2 and 3 elements respectively. Suppose that one partition contains vertices labelled 0 and 1, and that the other partition contains vertices labelled A, B, and C. Suppose that there are edges connecting 0 and C, 1 and A, and 1 and B. This graph would then be represented by the following sparse matrix:
>>> graph = csr_matrix([[0, 0, 1], [1, 1, 0]])
Here, the 1s could be anything, as long as they end up being stored as elements in the sparse matrix. We can now calculate maximum matchings as follows:
>>> print(maximum_bipartite_matching(graph, perm_type='column')) [2 0]
>>> print(maximum_bipartite_matching(graph, perm_type='row')) [ 1 -1 0]
The first output tells us that 1 and 2 are matched with C and A respectively, and the second output tells us that A, B, and C are matched with 1, nothing, and 0 respectively.
Note that explicit zeros are still converted to edges. This means that a different way to represent the above graph is by using the CSR structure directly as follows:
>>> data = [0, 0, 0]
... indices = [2, 0, 1]
... indptr = [0, 1, 3]
... graph = csr_matrix((data, indices, indptr))
... print(maximum_bipartite_matching(graph, perm_type='column')) [2 0]
>>> print(maximum_bipartite_matching(graph, perm_type='row')) [ 1 -1 0]
When one or both of the partitions are empty, the matching is empty as well:
>>> graph = csr_matrix((2, 0))
... print(maximum_bipartite_matching(graph, perm_type='column')) [-1 -1]
>>> print(maximum_bipartite_matching(graph, perm_type='row')) []
When the input matrix is square, and the graph is known to admit a perfect matching, i.e. a matching with the property that every vertex in the graph belongs to some edge in the matching, then one can view the output as the permutation of rows (or columns) turning the input matrix into one with the property that all diagonal elements are non-empty:
>>> a = [[0, 1, 2, 0], [1, 0, 0, 1], [2, 0, 0, 3], [0, 1, 3, 0]]See :
... graph = csr_matrix(a)
... perm = maximum_bipartite_matching(graph, perm_type='row')
... print(graph[perm].toarray()) [[1 0 0 1] [0 1 2 0] [0 1 3 0] [2 0 0 3]]
The following pages refer to to this document either explicitly or contain code examples using this.
scipy.sparse.csgraph._matching.maximum_bipartite_matching
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