Module « scipy.sparse.csgraph »

Fonction breadth_first_tree - module scipy.sparse.csgraph

Signature de la fonction breadth_first_tree

Description

breadth_first_tree.__doc__

    breadth_first_tree(csgraph, i_start, directed=True)

    Return the tree generated by a breadth-first search

    Note that a breadth-first tree from a specified node is unique.

    .. 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.
    i_start : int
        The index of starting node.
    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].

    Returns
    -------
    cstree : csr matrix
        The N x N directed compressed-sparse representation of the breadth-
        first tree drawn from csgraph, starting at the specified node.

    Examples
    --------
    The following example shows the computation of a depth-first tree
    over a simple four-component graph, starting at node 0::

         input graph          breadth first tree from (0)

             (0)                         (0)
            /   \                       /   \
           3     8                     3     8
          /       \                   /       \
        (3)---5---(1)               (3)       (1)
          \       /                           /
           6     2                           2
            \   /                           /
             (2)                         (2)

    In compressed sparse representation, the solution looks like this:

    >>> from scipy.sparse import csr_matrix
    >>> from scipy.sparse.csgraph import breadth_first_tree
    >>> X = csr_matrix([[0, 8, 0, 3],
    ...                 [0, 0, 2, 5],
    ...                 [0, 0, 0, 6],
    ...                 [0, 0, 0, 0]])
    >>> Tcsr = breadth_first_tree(X, 0, directed=False)
    >>> Tcsr.toarray().astype(int)
    array([[0, 8, 0, 3],
           [0, 0, 2, 0],
           [0, 0, 0, 0],
           [0, 0, 0, 0]])

    Note that the resulting graph is a Directed Acyclic Graph which spans
    the graph.  A breadth-first tree from a given node is unique.