scipy.sparse.csgraph.

reconstruct_path#

scipy.sparse.csgraph.reconstruct_path(csgraph, predecessors, directed=True)#

Construct a tree from a graph and a predecessor list.

Added 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

>>> import numpy as np
>>> 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)
   (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(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.]])
On this page