networkx(Python) 中是否有一种计算可达性矩阵的捷径？

Question

假设我已经给出了一个有向图并且我想要一个numpy可达性矩阵是否存在路径，所以当且仅当存在从i到j的路径时R(i,j)=1；

networkx 具有函数has_path(G, source, target)，但它仅针对特定的源节点和目标节点；因此，到目前为止我一直在这样做：

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 (adj(2,3)>0) 的路径所以也有一条从 4 到 3 的路径但是 adj(4,3)=0

Answer 1

您可以使用 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]]

Answer 2

一种方法是找到每个节点的所有后代，并将可到达的相应行设置为 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.]])

networkx(Python) 中是否有一种计算可达性矩阵的捷径？

Is there a short way in networkx(Python) to calculate the reachability matrix?

python

numpy

networkx