Module « scipy.sparse.csgraph »

Fonction maximum_bipartite_matching - module scipy.sparse.csgraph

Signature de la fonction maximum_bipartite_matching

Description

maximum_bipartite_matching.__doc__

    maximum_bipartite_matching(graph, perm_type='row')

    Returns a matching of a bipartite graph whose cardinality is as least that
    of any given matching of the graph.

    Parameters
    ----------
    graph : sparse matrix
        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.
    perm_type : str, {'row', 'column'}
        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 :math:`j`'th element is the row matched to the
        :math:`j`'th column. Conversely, if ``perm_type`` is ``'column'``, this
        returns the columns matched to each row.

    Returns
    -------
    perm : ndarray
        A matching of the vertices in one of the two partitions. Unmatched
        vertices are represented by a ``-1`` in the result.

    Notes
    -----
    This function implements the Hopcroft--Karp algorithm [1]_. Its time
    complexity is :math:`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.

    References
    ----------
    .. [1] John E. Hopcroft and Richard M. Karp. "An n^{5 / 2} Algorithm for
           Maximum Matchings in Bipartite Graphs" In: SIAM Journal of Computing
           2.4 (1973), pp. 225--231. :doi:`10.1137/0202019`

    Examples
    --------
    >>> 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]]
    >>> 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]]