breadth_first_tree#
- scipy.sparse.csgraph.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.
Added in version 0.11.0.
- Parameters:
- csgrapharray_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_startint
The index of starting node.
- directedbool, 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:
- cstreecsr matrix
The N x N directed compressed-sparse representation of the breadth- first tree drawn from csgraph, starting at the specified node.
Notes
If multiple valid solutions are possible, output may vary with SciPy and Python version.
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.