scipy.sparse.csgraph.reconstruct_path¶
-
scipy.sparse.csgraph.reconstruct_path(csgraph, predecessors, directed=True)¶ Construct a tree from a graph and a predecessor list.
New in version 0.11.0.
- Parameters
- csgrapharray_like or sparse matrix
The N x N matrix representing the directed or undirected graph from which the predecessors are drawn.
- predecessorsarray_like, one dimension
The length-N array of indices of predecessors for the tree. The index of the parent of node i is given by predecessors[i].
- 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 operate 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 tree drawn from csgraph which is encoded by the predecessor list.
Examples
>>> from scipy.sparse import csr_matrix >>> from scipy.sparse.csgraph import reconstruct_path
>>> graph = [ ... [0, 1 , 2, 0], ... [0, 0, 0, 1], ... [0, 0, 0, 3], ... [0, 0, 0, 0] ... ] >>> graph = csr_matrix(graph) >>> print(graph) (0, 1) 1 (0, 2) 2 (1, 3) 1 (2, 3) 3
>>> pred = np.array([-9999, 0, 0, 1], dtype=np.int32)
>>> cstree = reconstruct_path(csgraph=graph, predecessors=pred, directed=False) >>> cstree.todense() matrix([[ 0., 1., 2., 0.], [ 0., 0., 0., 1.], [ 0., 0., 0., 0.], [ 0., 0., 0., 0.]])