创建邻接矩阵的快捷方式

Question

我需要我编写的 python 代码的简短版本。所以基本上我拥有的是一个文本文件，其值如下：

x
a b c
d e f

第一行是节点数。从第二行开始，值被读入 NODE1、NODE2、Weight。我正在获取这些值并从中创建一个邻接矩阵。这将是一个无向图，因此 matrix[u][v] 将等于 matrix[v][u]。这是我的代码：

with open(filename, 'r') as textfile:
            firstLine = int(textfile.readline())
            for line in textfile:
                a, b, c = line.split()
                a = int(a)
                b = int(b)
                c = float(c)
                graph[a][b] = graph[b][a] = c

现在我需要将对角线填充为零，并将其他未分配的索引填充为无穷大。

Answer 1

with open(filename, 'r') as textfile:
    file_lines = text_file.readlines()

    # Initialize graph with -1 value, i.e. path do not exists representing infinite
    # Note: If negative weight is allowed, use the value which you want to symbolize infinte
    total_node = int(file_lines[0])
    my_graph = [[-1]*total_node]*total_node

    # Update weight based on available path
    for line in file_lines[1:]:
        s = line.split()
        u, v, w = int(s[0]), int(s[1]), float(s[2])
        my_graph[u][v] = my_graph[v][u] = w

    # Update diagonals to zero
    for i in range(total_node):
        my_graph[i][i] = my_graph[i][total_node - (i+1)] = 0

Answer 2

我不确定是否更简单，但是使用 numpy reshape 可以在填充权重之前创建默认矩阵，而无需显式循环。这里n是尺寸。

In [20]: n=4; np.reshape(np.array(([0]+[float("inf")]*n)*(n-1)+[0]),[n,n])
Out[20]:
array([[  0.,  inf,  inf,  inf],
       [ inf,   0.,  inf,  inf],
       [ inf,  inf,   0.,  inf],
       [ inf,  inf,  inf,   0.]])

创建邻接矩阵的快捷方式

Shortcut to creating an adjacency matrix

python

adjacency-matrix

minimum-spanning-tree