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: 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]. 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