Menu
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.
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.
How would I implement this in python? I just need a simple example, not necessarily using the one I provided.
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.
867
In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph. In the special case of a finite simple graph, the adjacency matrix is a (0,1)-matrix with zeros on its diagonal.
Using an adjacency matrix The following code implements a graph using an adjacency matrix: add_vertex(v) adds new vertex v to the graph, and add_edge(v1, v2, e) adds an edge with weight e between vertices v1 and v2 . print("Vertex ", v1, " does not exist. ") print("Vertex ", v2, " does not exist.
The adjacency matrix [55, 56] is a matrix used to represent finite graphs. The values in the matrix show whether pairs of nodes are adjacent to each other in the graph structure. If the graph is undirected, then the adjacency matrix will be a symmetric one.
Adjacency Matrix of a Graph To fill the adjacency matrix, we look at the name of the vertex in row and column. If those vertices are connected by an edge or more, we count number of edges and put this number as matrix element. The matrix to represent a graph in this way is called Adjacency matrix .
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 graph is not particularly convenient for use in networkx.) networkx supports 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).
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.]])
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
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.
21
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
