Python中的邻接矩阵
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/29464252/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Adjacency matrix in Python
提问by buydadip
I cannot find any clear explanation as to how to create an adjacency matrix in Python, with weights taken into consideration. I assume it should be relatively simple to create.
我找不到关于如何在 Python 中创建邻接矩阵并考虑了权重的任何明确解释。我认为创建起来应该相对简单。
I have the following matrix...
我有以下矩阵...
1 2 3 4 5 6
1 0 15 0 7 10 0
2 15 0 9 11 0 9
3 0 9 0 0 12 7
4 7 11 0 0 8 14
5 10 0 12 8 0 8
6 0 9 7 14 8 0
The numbers 1 through 6 are vertices, and the numbers within are the weights between each neighbouring vertex. For example, edge 1-2 has weight 15.
数字 1 到 6 是顶点，里面的数字是每个相邻顶点之间的权重。例如，边 1-2 的权重为 15。
How would I implement this in python? I just need a simple example, not necessarily using the one I provided.
我将如何在 python 中实现它？我只需要一个简单的例子，不一定使用我提供的那个。
I know how to create an adjacency list...
我知道如何创建邻接列表...
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'}]}
but I need an adjacency matrix.
但我需要一个邻接矩阵。
采纳答案by enpenax
I think the most common and simplest concept to store an adjacency matrix is to use a 2D array, which in python corresponds to nested lists
我认为存储邻接矩阵最常见和最简单的概念是使用二维数组，它在python中对应于嵌套列表
mat = [[0, 15, 0, 7, 10, 0], [15, 0, ...], [...], [...]]
m[0][1] # = 15 (weight of 1-2)
If the values are read only, you can use nested tuples, instead :)
如果值是只读的，您可以使用嵌套元组，而不是 :)
Of course you can go as crazy as you want with that and use dictionaries or write a class and redefine __getattr__to be more efficient on access times and storage as the matrix is symmetrical.
当然，您可以随心所欲地使用字典或编写一个类并重新定义__getattr__以提高访问时间和存储效率，因为矩阵是对称的。
回答by jwilner
I like tupled keys for 2d structures like this in python.
我喜欢 python 中像这样的二维结构的元组键。
{(1, 1): 0, (3, 2): 9... }
I think it's conceptually clearest since it drops the intermediary data structure in the above solution. Nonetheless, that intermediary data structure -- the inner list or row / column-- can be useful if you intend to access your structure either row or column wise.
我认为它在概念上最清晰，因为它删除了上述解决方案中的中间数据结构。尽管如此，如果您打算以行或列方式访问结构，则该中间数据结构（内部列表或行/列）可能很有用。
for x, row in enumerated(matrix, 1):
# process whole row
for y in enumerate(row, 1):
# process cell...
If cell-wise data access is your game though, it's hard to beat the following for expressive simplicity:
但是，如果您的游戏是按单元格进行数据访问，那么为了表达的简单性，很难击败以下内容：
for (x, y), value in matrix.iteritems():
# act on cell
Sort it if you want.
如果您愿意，请对其进行排序。
# (1, 1), (1, 2)...
for (x, y), value in sorted(matrix.iteritems()):
# act on cell
回答by dbliss
This converts your "adjacency list" (really a dict, not a list) into a genuine matrix:
这将您的“邻接列表”（实际上是一个字典，而不是一个列表）转换为一个真正的矩阵：
import networkx as nx
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'}]}
new_graph = nx.Graph()
for source, targets in graph.iteritems():
for inner_dict in targets:
assert len(inner_dict) == 1
new_graph.add_edge(int(source) - 1, int(inner_dict.keys()[0]) - 1,
weight=inner_dict.values()[0])
adjacency_matrix = nx.adjacency_matrix(new_graph)
(The format of your graphis not particularly convenient for use in networkx.) networkxsupports all kinds of operations on graphs and their adjacency matrices, so having the graph in this format should be very helpful for you. Note also that I've shifted your graph to use Python indices (i.e., starting at 0).
（你的格式graph在networkx..中使用不是特别方便。） networkx支持对图及其邻接矩阵的各种操作，所以拥有这种格式的图应该对你很有帮助。另请注意，我已将您的图形转换为使用 Python 索引（即从 0 开始）。
In [21]: adjacency_matrix
Out[21]:
matrix([[ 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.]])
回答by egnha
As mentioned previously, the standard way to deal with matrices in Python is to use NumPy. Here's a function that simply reads the adjacency matrix off of the adjacency list. (The implicit ordering of the nodes is made explicit by the parameter nodes.)
如前所述，在 Python 中处理矩阵的标准方法是使用NumPy。这是一个简单地从邻接表中读取邻接矩阵的函数。（节点的隐式排序由参数 明确nodes。）
import numpy
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()
In this case, weighted_adjmatrix(graph, nodes=list('123456'))gives the NumPy array
在这种情况下，weighted_adjmatrix(graph, nodes=list('123456'))给出 NumPy 数组
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]])
If a regular list is desired, the method tolist()can be called.
如果需要常规列表，则tolist()可以调用该方法。
