如何将对称矩阵转换为邻接表

Question

我该如何转换对称矩阵：

  A B C D
A 1 2 3 4
B 2 1 2 3
C 3 2 1 2
D 4 3 2 1

如何将数据转换成邻接矩阵？

A A 1
A B 2
A C 3 
A D 4
B A 3
B B 1
B C 2
B D 3
C A 3
C C 1
C D 2
D A 4
D B 3
D C 2
D D 1

有任何函数吗？

- gh1222

Answer 1

假设输入的是一个pandas数据框，你可以使用numpy来获取triu_indices：

import pandas as pd
import numpy as np

l = [[1, 2, 3, 4], [2, 1, 2, 3], [3, 2, 1, 2], [4, 3, 2, 1]]
df = pd.DataFrame(l, index=list('ABCD'), columns=list('ABCD'))

#    A  B  C  D
# A  1  2  3  4
# B  2  1  2  3
# C  3  2  1  2
# D  4  3  2  1

a = df.to_numpy()
x,y = np.triu_indices(len(df))

out = pd.DataFrame({'x': df.index[x], 'y':  df.columns[y], 'value': a[x,y]})

输出：

   x  y  value
0  A  A      1
1  A  B      2
2  A  C      3
3  A  D      4
4  B  B      1
5  B  C      2
6  B  D      3
7  C  C      1
8  C  D      2
9  D  D      1

所有组合

df.reset_index().melt('index', var_name='column')

输出：

   index column  value
0      A      A      1
1      B      A      2
2      C      A      3
3      D      A      4
4      A      B      2
5      B      B      1
6      C      B      2
7      D      B      3
8      A      C      3
9      B      C      2
10     C      C      1
11     D      C      2
12     A      D      4
13     B      D      3
14     C      D      2
15     D      D      1

或者，按照不同的顺序：

df.stack().rename_axis(['index', 'columns']).reset_index(name='value')

输出：

   index columns  value
0      A       A      1
1      A       B      2
2      A       C      3
3      A       D      4
4      B       A      2
5      B       B      1
6      B       C      2
7      B       D      3
8      C       A      3
9      C       B      2
10     C       C      1
11     C       D      2
12     D       A      4
13     D       B      3
14     D       C      2
15     D       D      1

- mozway

---

谢谢，但这并不能防止你例如得到A B和B A。 - gh1222

@gh1222 是的，它只获取上三角（对角线以上）的元素。可以查看输出结果。 - mozway

好的，在我的例子中是这样的。 - gh1222

您能详细说明一下吗？在这里，重塑纯粹是根据位置而非名称完成的。如有必要，请提供反例。 - mozway

是的，你说得对，我写错了我的问题。我需要获取所有可能的配对，因此必须有16行。 - gh1222

@gh1222 那么你需要一个简单的 df.reset_index().melt('index') 或者 df.stack() :p - mozway

Answer 2

另一种解决方案是使用 pandas.stack() 并重置索引值：

import pandas as pd
import numpy as np

l = [[1, 2, 3, 4], [2, 1, 2, 3], [3, 2, 1, 2], [4, 3, 2, 1]]
df = pd.DataFrame(l, index=list('ABCD'), columns=list('ABCD'))

#    A  B  C  D
# A  1  2  3  4
# B  2  1  2  3
# C  3  2  1  2
# D  4  3  2  1

df = df.stack().reset_index()
df['ordered-name'] = df.apply(lambda x: '-'.join(sorted([x['level_0'],x['level_1']])),axis=1)
df = df.drop_duplicates(['ordered-name'])
df.drop(['ordered-name'], axis=1, inplace=True)
#    level_0  level_1  0
# 0        A        A  1
# 1        A        B  2
# 2        A        C  3
# 3        A        D  4
# 4        B        B  1
# 5        B        C  2
# 6        B        D  3
# 7        C        C  1
# 8        C        D  2
# 9        D        D  1

您可以根据需要更改列的名称。

- T C Molenaar

---

这不是stack的正确输出，stack应该给出所有的(A,B)和(B,A)对，因此应该有16行，而不是10行。 - mozway

啊，你说得完全正确，可以通过删除“重复项”来更改它，但是你的解决方案更加优雅。 - T C Molenaar

Answer 3

实际上它已经是一个邻接矩阵了（正如您在有向图中使用它一样）。 我想你正在寻找邻接表，或者考虑你的例子作为邻接映射（用于无向图）。 我不确定是否有内置函数可以进行这种转换（假设您正在使用pandas数据帧考虑所使用的标记）。 最简单的方法就是读取矩阵的顶部（或仅底部）三角形，这不应该在循环中占用太多迭代次数，然后按照这种方式构建它。

- David Hutter

---

你的回答可以通过提供更多支持信息来改进。请编辑以添加进一步的细节，例如引用或文档，以便他人可以确认你的答案是正确的。您可以在帮助中心中找到有关如何编写良好答案的更多信息。 - KiynL