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

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

有什么功能吗?

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

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

您可以随意更改列的名称。

Answer 3

它实际上已经是一个邻接矩阵(就像你将它用于有向图一样)。我猜你正在寻找一个邻接表或考虑你的例子邻接图(无向图)。我不确定是否有用于这种转换的内置函数(假设您使用的是pandas数据框架，考虑到使用的标签)。最简单的方法是读取矩阵的顶部(或底部)三角形，在循环中不应该占用太多迭代，并按照这种方式构建它。