Skip to main content
`Ctrl`+`K`
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:
    csgraph array_like or sparse array or matrix

      The N x N matrix representing the directed or undirected graph from which the predecessors are drawn.

    predecessors array_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]`.

    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 operate 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 tree drawn from csgraph which is encoded by the predecessor list.

  Examples

      >>> import numpy as np
      >>> from scipy.sparse import csr_array
      >>> 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_array(graph)
      >>> print(graph)
      <Compressed Sparse Row sparse array of dtype 'int64'
          with 4 stored elements and shape (4, 4)>
          Coords  Values
          (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()
      array([[0., 1., 2., 0.],
             [0., 0., 0., 1.],
             [0., 0., 0., 0.],
             [0., 0., 0., 0.]])