scipy.sparse.csgraph.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.
New 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.
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.