如何将邻接矩阵转换为关联矩阵

Question

我从邻接列表创建了一个邻接矩阵，但我不知道如何从这些数据创建关联矩阵。

我的代码是：

import numpy
graph = {'1': [{'2':'15'}, {'4':'7'}, {'5':'10'}],
'2': [{'3':'9'}, {'4':'11'}, {'6':'9'}],
'3': [{'5':'12'}, {'6':'7'}],
'4': [{'5':'8'}, {'6':'14'}],
'5': [{'6':'8'}]}
def weighted_adjmatrix(adjlist, nodes):
'''Returns a (weighted) adjacency matrix as a NumPy array.'''
matrix = []
for node in nodes:
weights = {endnode:int(weight)
for w in adjlist.get(node, {})
for endnode, weight in w.items()}
matrix.append([weights.get(endnode, 0) for endnode in nodes])
matrix = numpy.array(matrix)
return matrix + matrix.transpose()

weighted_adjmatrix(graph, nodes=list('123456'))´

当我运行它时，它抛出这个数组：

array([[ 0, 15,  0,  7, 10,  0],
[15,  0,  9, 11,  0,  9],
[ 0,  9,  0,  0, 12,  7],
[ 7, 11,  0,  0,  8, 14],
[10,  0, 12,  8,  0,  8],
[ 0,  9,  7, 14,  8,  0]])

Answer 1

根据我的理解(根据维基百科(，关联矩阵应该有表示边的列和表示顶点的行。

现在，在您的输入数据中没有显式的边缘索引。让我们来看一个作为顶点和边列表给出的平凡图：

import numpy
vertices = {0, 1, 2}
edges = [(0, 1), (0, 2), (1, 2)]
assert all(l in vertices and r in vertices for l, r in edges)
incidence_matrix = numpy.zeros([max(vertices) + 1, len(edges)], dtype="int")
for i, edge in enumerate(edges):
l, r = edge
incidence_matrix[l][i] = 1
incidence_matrix[r][i] = 1
print(incidence_matrix)

这导致以下关联矩阵：

[[1 1 0]
[1 0 1]
[0 1 1]]

翻译到您的示例(边缘索引根据图dict的顺序推断，假设它像Python 3.7+中那样排序(，结果如下：

def weighted_incidence_matrix(graph, nodes):
edges = [
(left, right, weight)
for left in graph
for edge in graph[left]
# edge is actually a dict {target: weight}
for right, weight in edge.items()
]
assert all(l in nodes and r in nodes for l, r, _ in edges)
incidence_matrix = numpy.zeros([len(nodes), len(edges)], dtype="int")
for i, edge in enumerate(edges):
l, r, weight = edge
l = nodes.index(l)
r = nodes.index(r)
incidence_matrix[l][i] = weight
incidence_matrix[r][i] = weight
return incidence_matrix
print(weighted_incidence_matrix(graph, "123456"))

带有输出矩阵

[[15  7 10  0  0  0  0  0  0  0  0]
[15  0  0  9 11  9  0  0  0  0  0]
[ 0  0  0  9  0  0 12  7  0  0  0]
[ 0  7  0  0 11  0  0  0  8 14  0]
[ 0  0 10  0  0  0 12  0  8  0  8]
[ 0  0  0  0  0  9  0  7  0 14  8]]

我希望这就是你想要的。