如何将节点和边列表转换为邻接矩阵？

Question

我正在构建一个包含 dash_cytoscape 的 Dash 应用程序，用户可以在其中连接和断开给定网络中的节点。现在我想编写一个函数，从该网络的边和节点列表中重建邻接矩阵。我发现大致朝着正确的方向发展，除了我的情况似乎是这个问题的边缘情况，不是每个节点都必须连接到另一个节点。例如，网络可能如下所示：

此网络的正确邻接矩阵可能如下所示：

A = np.array([[0,1,0,0,0],
              [1,0,0,0,0],
              [0,0,0,0,0],
              [0,0,0,0,2],
              [0,0,0,2,0]])

我能够从网络中获取节点列表和边列表：

edges = [('3', '4', 2),('0', '1', 1)]
nodes = ['0', '1', '2', '3', '4']

但是如何从那里得到正确的邻接矩阵？

Answer 1

您只需创建一个大小为 V x V 的矩阵 M，其中 V 是您的节点总数，并用零填充它。然后对于 edges 列表中的每个元素（比如 (i, j, w)），您知道 i, j 是要在邻接矩阵中修改的索引。因此只需设置 M[i, j] = w.

注意：如果你的图是无向的，请记住从节点 i 到节点 j 的边与从节点 j 到节点 i 的边相同，所以你还必须设置 M[j,i]=w.

Answer 2

您可以遍历 edges 并使用权重更新预填充列表：

edges = [('3', '4', 2),('0', '1', 1)]
nodes = ['0', '1', '2', '3', '4']
m = max(map(int, nodes))
d = [[0 for _ in range(m+1)] for _ in range(m+1)]
for x, y, w in edges:
   d[int(x)][int(y)] = w
   d[int(y)][int(x)] = w

输出：

[[0, 1, 0, 0, 0], 
 [1, 0, 0, 0, 0], 
 [0, 0, 0, 0, 0], 
 [0, 0, 0, 0, 2], 
 [0, 0, 0, 2, 0]]

Answer 3

根据用户Fonzie的建议：

n_nodes = len(nodes)
A = np.zeros((n_nodes,n_nodes))

for edge in edges:
    i = int(edge[0])
    j = int(edge[1])
    weight = edge[2]
    A[i,j] = weight
    A[j,i] = weight

如何将节点和边列表转换为邻接矩阵？

How to convert a list of nodes and edges to an adjacency matrix?

python

graph-theory

networkx

adjacency-matrix

cytoscape