Document

depth_first_tree(csgraph, i_start, directed=True)

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.

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

Returns

cstree : csr matrix: The N x N directed compressed-sparse representation of the depth- first tree drawn from csgraph, starting at the specified node.

Return a tree generated by a depth-first search.

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)

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.

See :

Local connectivity graph

Hover to see nodes names; edges to Self not shown, Caped at 50 nodes.

Using a canvas is more power efficient and can get hundred of nodes ; but does not allow hyperlinks; , arrows or text (beyond on hover)

SVG is more flexible but power hungry; and does not scale well to 50 + nodes.

All aboves nodes referred to, (or are referred from) current nodes; Edges from Self to other have been omitted (or all nodes would be connected to the central node "self" which is not useful). Nodes are colored by the library they belong to, and scaled with the number of references pointing them

GitHub : None#None
type: <class 'builtin_function_or_method'>
Commit: