gpt4 book ai didi

python - 如何在 Python 中将加权边列表转换为邻接矩阵?

转载 作者:行者123 更新时间:2023-12-05 09:16:58 26 4
gpt4 key购买 nike

数据存在于 excel 文件中,第一列代表第一个节点,第二列代表第二个节点,第三列包含权重。

节点是字符串。

例如:

Apple Banana 65
Orange Apple 32

最佳答案

首先要做的是导入 Excel 文件。最直接的方法是使用 pandas:

import pandas
data = pandas.read_excel("path/to/edgelist", header=None)

这将返回表单的数据框

In [2]: data  
Out[2]:
0 1 2
0 Apple Banana 65
1 Orange Apple 32

捷径:使用 networkx

让我们先加载networkx包

import networkx

然后,根据 data,我们将边缘列表作为列表的列表:

edgeList = data.values.tolist()

这样,我们得到

In [19]: edgeList
Out[19]: [['Apple', 'Banana', 65], ['Orange', 'Apple', 32]]

让我们创建一个空(有向)图 G:

G = networkx.DiGraph()

然后我们用一个简单的 for 循环添加边:

for i in range(len(edgeList)):
G.add_edge(edgeList[i][0], edgeList[i][1], weight=edgeList[i][2])

我们可以很容易地检索邻接矩阵作为

A = networkx.adjacency_matrix(G).A

读作一个简单明了的 numpy 数组

In [30]: A
Out[30]:
array([[ 0, 65, 0],
[ 0, 0, 0],
[32, 0, 0]], dtype=int64)

注意:上述邻接矩阵指的是带权有向图(即Apple到Banana有边,Banana到Apple无边)。如果需要一个加权的无向图(即,如果从 Apple 到 Banana 存在一条边,那么从 Banana 到 Apple 也存在一条边),只需使用

G = networkx.Graph()

代替

G = networkx.DiGraph()

漫漫长路:手动

让我们使用第一列和第二列来收集节点 ID

nodes = data.iloc[:, 0].tolist() + data.iloc[:, 1].tolist()

因此

In [4]: nodes
Out[4]: [u'Apple', u'Orange', u'Banana', u'Apple']

让我们排序并删除重复项(反正排序不是强制性的)

nodes = sorted(list(set(nodes)))

nodes现在有形式

In [8]: nodes
Out[8]: [u'Apple', u'Banana', u'Orange']

让我们用连续的数字 ID 映射每个节点(字符串)以提供邻接矩阵

nodes = [(i,nodes[i]) for i in range(len(nodes))]

nodes现在有形式

In [10]: nodes
Out[10]: [(0, u'Apple'), (1, u'Banana'), (2, u'Orange')]

现在字符串到整数的映射已经完成,让我们用对应的 ID 替换原始数据帧 (data) 中的每个字符串

In [15]: for i in range(len(nodes)):
...: data = data.replace(nodes[i][1], nodes[i][0])

现在 data 的形式是

In [16]: data
Out[16]:
0 1 2
0 0 1 65
1 2 0 32

所以你看到每次出现的Apple都被替换为0,每次出现的Banana都被替换为1并且每次出现od Orange 已替换为 2(根据变量 nodes)。

为了构建邻接矩阵,让我们导入另一个著名的包(scipy)

from scipy.sparse import coo_matrix 

并创建一个 coordinate-based sparse matrix

M = coo_matrix((data.iloc[:,2], (data.iloc[:,0],data.iloc[:,1])), shape=(len(nodes), len(nodes)))

这将创建一个稀疏邻接矩阵(对于具有许多节点和少量边缘的图形,内存占用更少)。如果你需要一个密集的邻接矩阵,那么

M = M.todense()

其中 M 最终具有形式

matrix([[ 0, 65,  0],
[ 0, 0, 0],
[32, 0, 0]])

注意:上述邻接矩阵指的是带权有向图(即Apple到Banana有边,Banana到Apple无边)。如果需要一个带权无向图(即苹果到香蕉有边,香蕉到苹果也有边),只需转置上述邻接矩阵即可

M_symmetric = M + M.T 

在哪里

In [38]: M_symmetric
Out[38]:
matrix([[ 0, 65, 32],
[65, 0, 0],
[32, 0, 0]])

关于python - 如何在 Python 中将加权边列表转换为邻接矩阵?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/49095067/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com