Есть ли короткий путь в сети x (Python) для вычисления матрицы достижимости?

Question

Представьте, что я дал ориентированный граф и мне нужна матрица numpy достижимости, существует ли путь, поэтому R (i, j) = 1 тогда и только тогда, когда существует путь от i до j;

networkx имеет функцию has_path (G, source, target), однако она предназначена только для указанных c узлов source и taget; Поэтому я до сих пор делал это:

import networkx as nx
R=np.zeros((d,d))
for i in range(d):
   for j in range(d):
      if nx.has_path(G, i, j):
         R[i,j]=1

Есть ли лучший способ добиться этого?

Вот минимальный пример с действительными числами:

import networkx as nx
import numpy as np

c=np.random.rand(4,4)
G=nx.DiGraph(c)
A=nx.minimum_spanning_arborescence(G)

adj=nx.to_numpy_matrix(A)

Здесь мы можем видеть, что это будет матрица смежности, а не матрицы достижимости - в моем примере с номером я получу

adj=
matrix([[0.        , 0.        , 0.        , 0.        ],
        [0.        , 0.        , 0.47971056, 0.        ],
        [0.        , 0.        , 0.        , 0.        ],
        [0.16101491, 0.04779295, 0.        , 0.        ]])

Таким образом, существует путь от 4 до 2 (adj (4,2 )> 0) и от 2 до 3 (прил. (2,3)> 0), поэтому также будет путь от 4 до 3, но прил. (4,3) = 0

Answer 1

Одним из подходов может быть поиск всех потомков каждого узла и установка соответствующих строк, которые достижимы, равными 1:

a = np.zeros((len(A.nodes()),)*2)

for node in A.nodes():
    s = list(nx.descendants(A, node))
    a[s, node] = 1

---

print(a)

array([[0., 0., 1., 0.],
       [1., 0., 1., 0.],
       [0., 0., 0., 0.],
       [1., 1., 1., 0.]])

Answer 2

Вы можете использовать all_pairs_shortest_path_length :

import networkx as nx
import numpy as np

np.random.seed(42)

c = np.random.rand(4, 4)
G = nx.DiGraph(c)
length = dict(nx.all_pairs_shortest_path_length(G))

R = np.array([[length.get(m, {}).get(n, 0) > 0 for m in G.nodes] for n in G.nodes], dtype=np.int32)

print(R)

Выход

[[1 1 1 1 1]
 [0 1 1 1 1]
 [0 0 1 1 1]
 [0 0 0 1 1]
 [0 0 0 0 1]]