scipy.sparse.csgraph.

reconstruct_path

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

Konstruiert einen Baum aus einem Graphen und einer Vorgängerliste.

Hinzugefügt in Version 0.11.0.

Parameter:

csgrapharray_like oder dünnbesetzte Array oder Matrix

Die N x N Matrix, die den gerichteten oder ungerichteten Graphen darstellt, aus dem die Vorgänger stammen.

predecessorsarray_like, eindimensional

Das N-dimensionale Array von Indizes der Vorgänger für den Baum. Der Index des Elternknotens von Knoten i ist gegeben durch predecessors[i].

directedbool, optional

Wenn True (Standardwert), dann auf einem gerichteten Graphen operieren: nur von Punkt i zu Punkt j entlang der Pfade csgraph[i, j] bewegen. Wenn False, dann auf einem ungerichteten Graphen operieren: der Algorithmus kann sich von Punkt i zu j entlang csgraph[i, j] oder csgraph[j, i] bewegen.

Rückgabe:

cstreecsr matrix

Die N x N gerichtete komprimierte spärliche Darstellung des Baumes, der aus csgraph gezogen wird und durch die Vorgängerliste kodiert ist.

Beispiele

Probieren Sie es in Ihrem Browser aus!

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

ZurückIn Tab öffnen