scipy.sparse.csgraph.

reconstruct_path

scipy.sparse.csgraph.reconstruct_path(csgraph, предшественники, направленный=True)

Построить дерево из графа и списка предшественников.

Добавлено в версии 0.11.0.

Параметры:

csgrapharray_like или разреженный массив или матрица

Матрица N x N, представляющая ориентированный или неориентированный граф, из которого извлекаются предшественники.

предшественникиarray_like, одно измерение

Массив индексов предшественников длины N для дерева. Индекс родителя узла i задается как predecessors[i].

направленныйbool, необязательно

Если True (по умолчанию), то работает с ориентированным графом: движение только от точки i к точке j по путям csgraph[i, j]. Если False, то работает с неориентированным графом: алгоритм может переходить от точки i к j по csgraph[i, j] или csgraph[j, i].

Возвращает:

cstreecsr matrix

Направленное сжато-разреженное представление размера N x N дерева, построенного из csgraph, которое кодируется списком предшественников.

Примеры

Попробуйте в вашем браузере!

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

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

НазадОткрыть во вкладке