在 python 中将图形权重转换为矩阵

Question

我有以下形式的数据：

A=B=11
A=C=6
A=D=5
B=C=19
B=D=17
C=D=6

但我想将其转换成这种格式：

graph= [[ 0, 10, 15, 20 ],
            [ 10, 0, 35, 25 ],
            [ 15, 35, 0, 30 ],
            [ 20, 25, 30, 0 ]]

这是如何实现的？我知道多维数组是如何工作的，但是使用 python 构造这个矩阵非常令人困惑

Answer 1

你可以这样做：

import pandas as pd
import numpy as np

# Change to your filename.
filename = 'graph.csv'

# Lines to skip.
skip_rows = 1

# Whether the graph is undirected. 
undirected = True

# Read file and convert vertex names to integer indices. Names are sorted. 
# I.e., A=0, B=1, etc. (like in your example).
df = pd.read_csv(filename, sep='=', header=None, names=['n1', 'n2', 'weight'], skiprows=skip_rows)
cat_type = pd.CategoricalDtype(categories=sorted(np.unique(np.concatenate((df['n1'].unique(), df['n2'].unique())))), ordered=True)
df['n1'] = df['n1'].astype(cat_type).cat.codes
df['n2'] = df['n2'].astype(cat_type).cat.codes

n_nodes = len(cat_type.categories)
graph = np.full((n_nodes, n_nodes), np.nan)

for n1, n2, w in zip(df['n1'], df['n2'], df['weight']):
    graph[n1, n2] = w
    if undirected:
        graph[n2, n1] = w

np.fill_diagonal(graph, 0)

print(graph)

[[ 0. 11.  6.  5.]
 [11.  0. 19. 17.]
 [ 6. 19.  0.  6.]
 [ 5. 17.  6.  0.]]

如果graph[i, j] == NaN，则表示根据您的文件，从节点i到节点j没有边（长度为1的路径）。

Answer 2

您可以使用字典来制作邻接表。然后枚举该字典的键，为每个键定义一个索引。然后最后将权重复制到最终的矩阵结构中：

nodes = {}
for line in open("input.txt").read().splitlines():
    a, b, weight = line.split("=")
    nodes.setdefault(a, []).append((b, int(weight)))
    nodes.setdefault(b, []).append((a, int(weight)))

n = len(nodes)
key2index = { key: i for i, key in enumerate(nodes.keys()) }
graph = [[0] * n for _ in range(n)]
for a, edges in nodes.items():
    row = graph[key2index[a]]
    for b, weight in edges:
        row[key2index[b]] = weight

print(graph)

矩阵中的零表示没有边，就像您在矩阵主对角线上的示例中的情况（即您的示例图没有“循环”）。

nodes = {}
lines = open("input.txt").read().splitlines()
for line in lines[1:]:
    a, b, weight = line.split("=")
    nodes.setdefault(a, []).append((b, int(weight)))
    nodes.setdefault(b, []).append((a, int(weight)))

n = len(nodes)
key2index = { key: i for i, key in enumerate(nodes.keys()) }
graph = [[0] * n for _ in range(n)]
for a, edges in nodes.items():
    row = graph[key2index[a]]
    for b, weight in edges:
        row[key2index[b]] = weight

print(graph)

在 python 中将图形权重转换为矩阵

Converting Graph weights to Matrix in python

python

algorithm

graph

matrix

multidimensional-array

评论