如何从 python 中的字典生成图形的邻接矩阵？

Question

我有以下字典：

 g = {
'A': ['A', 'B', 'C'],
'B': ['A', 'C', 'E'],
'C': ['A', 'B', 'D'],
'D': ['C','E'],
'E': ['B','D']
}

它实现了一个图，每个列表包含图顶点的邻居（字典键是顶点本身）。我有麻烦了，我想不出一种从他们的邻居列表中获取图形邻接矩阵的方法，这可能很容易，但我是 python 的新手，我希望有人能帮助我！我正在使用 Python 3.5

我需要生成以下矩阵：

原文由 Patterson 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

没有熊猫

keys=sorted(g.keys())
size=len(keys)

M = [ [0]*size for i in range(size) ]

for a,b in [(keys.index(a), keys.index(b)) for a, row in g.items() for b in row]:
     M[a][b] = 2 if (a==b) else 1

M

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

解释

for a, row in g.items() 迭代键：字典中的值条目，以及 for b in row 迭代值。如果我们使用 (a,b)，这将给我们所有的对。

(keys.index(a), keys.index(b)) 但我们需要索引分配给相应的矩阵条目，

keys=sorted(g.keys()) 这就是我们提取和排序键的原因。

for a,b in... 获取索引条目并根据对角线元素或不分配值 1 或 2。

M = [ [0]*size for ... 初始化前不能使用矩阵。

原文由 karakfa 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

这是使用熊猫的解决方案。

 import pandas as pd

g = {
'A': [ 'A', 'B', 'C'],
'B': [ 'A', 'C', 'E'],
'C': [ 'A', 'B ',' D '], # I added a comma here
'D': [' C ',' E '],
'E': [' B ',' D ']
}

# clean up the example
g = {k: [v.strip() for v in vs] for k, vs in g.items()}

edges = [(a, b) for a, bs in g.items() for b in bs]

df = pd.DataFrame(edges)

adj_matrix = pd.crosstab(df[0], df[1])

# 1  A  B  C  D  E
# 0
# A  1  1  1  0  0
# B  1  0  1  0  1
# C  1  1  0  1  0
# D  0  0  1  0  1
# E  0  1  0  1  0

我不确定为什么在 (A, A) 位置的示例矩阵中有 2 个。

原文由 hilberts_drinking_problem 发布，翻译遵循 CC BY-SA 3.0 许可协议