`scipy.sparse.csgraph._tools:reconstruct_path`

Signature

def reconstruct_path(csgraph, predecessors, directed = True)

Summary

Construct a tree from a graph and a predecessor list.

Extended Summary

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

Aliases

scipy.sparse.csgraph.reconstruct_path