scipy.sparse.csgraph.

depth_first_order#

scipy.sparse.csgraph.depth_first_order(csgraph, i_start, directed=True, return_predecessors=True)#

Return a depth-first ordering starting with specified node.

Note that a depth-first order is not unique. Furthermore, for graphs with cycles, the tree generated by a depth-first search is not unique either.

Added in version 0.11.0.

Parameters:
csgrapharray_like or sparse matrix

The N x N 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].

return_predecessorsbool, optional

If True (default), then return the predecessor array (see below).

Returns:
node_arrayndarray, one dimension

The depth-first list of nodes, starting with specified node. The length of node_array is the number of nodes reachable from the specified node.

predecessorsndarray, one dimension

Returned only if return_predecessors is True. The length-N list of predecessors of each node in a depth-first tree. If node i is in the tree, then its parent is given by predecessors[i]. If node i is not in the tree (and for the parent node) then predecessors[i] = -9999.

Notes

If multiple valid solutions are possible, output may vary with SciPy and Python version.

Examples

>>> from scipy.sparse import csr_matrix
>>> from scipy.sparse.csgraph import depth_first_order
>>> graph = [
... [0, 1, 2, 0],
... [0, 0, 0, 1],
... [2, 0, 0, 3],
... [0, 0, 0, 0]
... ]
>>> graph = csr_matrix(graph)
>>> print(graph)
(np.int32(0), np.int32(1))  1
(np.int32(0), np.int32(2))  2
(np.int32(1), np.int32(3))  1
(np.int32(2), np.int32(0))  2
(np.int32(2), np.int32(3))  3
>>> depth_first_order(graph,0)
(array([0, 1, 3, 2], dtype=int32), array([-9999,     0,     0,     1], dtype=int32))