Module « scipy.sparse.csgraph »

Fonction connected_components - module scipy.sparse.csgraph

Signature de la fonction connected_components

Description

connected_components.__doc__

    connected_components(csgraph, directed=True, connection='weak',
                         return_labels=True)

    Analyze the connected components of a sparse graph

    .. versionadded:: 0.11.0

    Parameters
    ----------
    csgraph : array_like or sparse matrix
        The N x N matrix representing the compressed sparse graph.  The input
        csgraph will be converted to csr format for the calculation.
    directed : bool, optional
        If True (default), then operate on a directed graph: only
        move from point i to point j along paths csgraph[i, j].
        If False, then find the shortest path on an undirected graph: the
        algorithm can progress from point i to j along csgraph[i, j] or
        csgraph[j, i].
    connection : str, optional
        ['weak'|'strong'].  For directed graphs, the type of connection to
        use.  Nodes i and j are strongly connected if a path exists both
        from i to j and from j to i. A directed graph is weakly connected
        if replacing all of its directed edges with undirected edges produces
        a connected (undirected) graph. If directed == False, this keyword
        is not referenced.
    return_labels : bool, optional
        If True (default), then return the labels for each of the connected
        components.

    Returns
    -------
    n_components: int
        The number of connected components.
    labels: ndarray
        The length-N array of labels of the connected components.

    References
    ----------
    .. [1] D. J. Pearce, "An Improved Algorithm for Finding the Strongly
           Connected Components of a Directed Graph", Technical Report, 2005

    Examples
    --------
    >>> from scipy.sparse import csr_matrix
    >>> from scipy.sparse.csgraph import connected_components

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

    >>> n_components, labels = connected_components(csgraph=graph, directed=False, return_labels=True)
    >>> n_components
    2
    >>> labels
    array([0, 0, 0, 1, 1], dtype=int32)