scipy.sparse.csgraph.

reconstruct_path

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

从图和前驱列表构建一棵树。

Added in version 0.11.0.

参数:

csgraph类似数组或稀疏矩阵

表示有向或无向图的 N x N 矩阵，从中绘制前驱节点。

前身类数组，一维

长度为 N 的数组，表示树的前驱节点索引。节点 i 的父节点的索引由 predecessors[i] 给出。

有向的bool, 可选

如果为 True（默认），则在有向图上操作：仅沿路径 csgraph[i, j] 从点 i 移动到点 j。如果为 False，则在无向图上操作：算法可以从点 i 沿 csgraph[i, j] 或 csgraph[j, i] 移动到点 j。

返回:

cstreecsr 矩阵

从 csgraph 中绘制的树的 N x N 有向压缩稀疏表示，该树由前驱列表编码。

示例

Try it in your browser!

>>> 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)
<Compressed Sparse Row sparse matrix 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()
matrix([[0., 1., 2., 0.],
        [0., 0., 0., 1.],
        [0., 0., 0., 0.],
        [0., 0., 0., 0.]])

Go BackOpen In Tab