scipy.sparse.csgraph.

reconstruct_path#

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

從圖和前導節點列表建構樹狀結構。

在版本 0.11.0 中新增。

參數:

csgraph類陣列或稀疏陣列或矩陣: 代表有向或無向圖的 N x N 矩陣，前導節點由此圖繪製。
predecessors類陣列，一維: 樹狀結構的前導節點索引之長度為 N 的陣列。節點 i 的父節點索引由 predecessors[i] 給定。
directed布林值，選填: 若為 True (預設值)，則對有向圖進行操作：僅沿著路徑 csgraph[i, j] 從點 i 移動到點 j。若為 False，則對無向圖進行操作：演算法可以沿著 csgraph[i, j] 或 csgraph[j, i] 從點 i 進展到 j。

傳回值:

cstreecsr 矩陣: 從 csgraph 繪製的樹狀結構之 N x N 有向壓縮稀疏表示，由前導節點列表編碼。

範例

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