如何从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

---

键/值对中额外的空格是否有意？您想如何访问结果？嵌套列表可以吗？如果可以，您希望列表按字母顺序排列吗？（字典中的键不保证顺序。） - Jared Goguen

不，空格是无意的，我会编辑问题来解决这个问题！我可以使用以下代码获取已排序的键：sorted(g) - Patterson

Answer 1

这里有一个使用pandas的解决方案。

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

---

我认为在这个加权图中，指向自身的节点的权重为2。这只是一种假设。 - Vedang Mehta

2是因为顶点'A'有一条指向自身的边。 - Patterson

我无法导入pandas。 ImportError：没有名为“pandas”的模块。 - Patterson

您需要安装pandas或使用其他方法。请参考此处http://pandas.pydata.org/ 关于矩阵：我们可以计算出度、入度或两者。在前两种情况下，(A,A)指向一个，在第三种情况下，矩阵的其余部分应该加倍。如果我漏掉了什么，请告诉我。 - hilberts_drinking_problem

@Yakym Pirozhenko，感谢您的解决方案。我有一个巨大的数据集，需要4M列和1M行的adj_matrix。因此，我在服务器上收到了MemoryError错误。您有什么解决方案吗？ - YNR

@YNr 你可以尝试使用Scipy稀疏矩阵，或者使用Networkx包中的图形，其中权重表示边缘计数。 - hilberts_drinking_problem

Answer 2

没有pandas

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

---

太好了，你帮了我很多！但是你能解释一下这段代码吗？我没有很好地理解填充数组的循环那一行，我知道你使用了“Python comprehensions”，但对我来说这很复杂，我是 Python 的新手，非常感谢！ - Patterson

谢谢您的解释！现在看起来太容易了！ - Patterson

Answer 3

import numpy as np
mat = np.zeros(shape = (len(g), len(g)))
for k, vs in g.items():
    for v in vs:
        if v in g[k]:
            mat[k][v] = 1

- vic

---

请添加一些解释。 - Sean