scipy.sparse.csgraph.depth_first_tree¶
- scipy.sparse.csgraph.depth_first_tree(csgraph, i_start, directed=True)¶
Return a tree generated by a depth-first search.
Note that a tree generated by a depth-first search is not unique: it depends on the order that the children of each node are searched.
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 depth- 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 depth first tree from (0) (0) (0) / \ \ 3 8 8 / \ \ (3)---5---(1) (3) (1) \ / \ / 6 2 6 2 \ / \ / (2) (2)
In compressed sparse representation, the solution looks like this:
>>> from scipy.sparse import csr_matrix >>> from scipy.sparse.csgraph import depth_first_tree >>> X = csr_matrix([[0, 8, 0, 3], ... [0, 0, 2, 5], ... [0, 0, 0, 6], ... [0, 0, 0, 0]]) >>> Tcsr = depth_first_tree(X, 0, directed=False) >>> Tcsr.toarray().astype(int) array([[0, 8, 0, 0], [0, 0, 2, 0], [0, 0, 0, 6], [0, 0, 0, 0]])
Note that the resulting graph is a Directed Acyclic Graph which spans the graph. Unlike a breadth-first tree, a depth-first tree of a given graph is not unique if the graph contains cycles. If the above solution had begun with the edge connecting nodes 0 and 3, the result would have been different.