Adjacency Matrix in Python

Adjacency Matrix in Python

  1. Create an Adjacency Matrix
  2. Create an Adjacency Matrix in Python Using 2D Lists
  3. Create an Adjacency Matrix in Python Using the NumPy Module
  4. Conclusion

A graph data structure is used in Python to represent various real-life objects like networks and maps. We can represent a graph using an adjacency matrix.

This article will discuss different ways to implement the adjacency matrix in Python.

Create an Adjacency Matrix

Consider the following graph.

Python Adjacency Matrix Undirected Unweighted Graph

In the graph, there are 6 nodes numbered from 1 to 6. There are 7 edges in the graph connecting the nodes; an edge eij connects node i and node j.

To represent the graph, we use an adjacency matrix.

  1. An adjacency matrix consists of a two-dimensional grid.
  2. Each row or column in the grid represents a node.
  3. For an unweighted graph, as shown above, if the value at the position (i,j) is 1 in the grid, it means that node i and node j are connected.
  4. If the value at position (i,j) is 0, node i and node j are not connected.

If you want to create an adjacency matrix for the graph in the image above, it will look as follows.

| 0    | 1    | 0    | 0    | 0    | 0    |
| 1    | 0    | 1    | 1    | 0    | 0    |
| 0    | 1    | 0    | 1    | 0    | 1    |
| 0    | 1    | 1    | 0    | 1    | 0    |
| 0    | 0    | 0    | 1    | 0    | 1    |
| 0    | 0    | 1    | 0    | 1    | 0    |

The above table shows that the value at position (i,j) is also present at position (j,i). This is due to the reason that the edge eij is the same as the edge eji.

This also results in an adjacency matrix that is symmetrical along its diagonal.

In an unweighted graph, the edges have no weight. In other words, all the edges have equal weights.

Due to this, the adjacency matrix contains only the values 0 and 1.

Now, consider the following weighted graph.

Python Adjacency Matrix Weighted Graph

For a weighted graph, everything remains the same except for the weights for the edges. You can observe that each edge has been assigned a value in the image.

Therefore, in the adjacency matrix, the value at position (i,j) is the weight of the edge eij in the graph.

The adjacency matrix for the above image looks as follows.

| 0    | 5    | 0    | 0    | 0    | 0    |
| 5    | 0    | 1    | 12   | 0    | 0    |
| 0    | 1    | 0    | 8    | 0    | 4    |
| 0    | 12   | 8    | 0    | 7    | 0    |
| 0    | 0    | 0    | 7    | 0    | 2    |
| 0    | 0    | 4    | 0    | 2    | 0    |

Again, you can observe that the value at position (i,j) in the matrix is also present at position (j,i). This is due to the reason that the edge eij is the same as the edge eji.

Again, this results in a symmetrical adjacency matrix along its diagonal.

Create an Adjacency Matrix in Python Using 2D Lists

To create an adjacency matrix for an unweighted graph with n nodes, we will first create a two-dimensional list containing n inner lists. Additionally, each inner list contains n zeros.

After creating a 2-dimensional list containing zeros, we will assign 1 to the positions (i,j) where the edge eij exists in the graph. For this task, we will use the following steps.

  • First, we will create an empty list named adjacency_matrix. After that, we will convert it into a 2-dimensional list using a for loop and the append() method.
  • Inside the for loop, we will create an empty list named row. Then, we will populate the empty list with zeros using another for loop, and finally, we will append row into the adjacency_matrix.
  • In the code, we have represented the set of edges using a list of tuples. Each tuple contains 2 values that represent the connected nodes of the graph.
  • After defining the edges, we will assign the value 1 to the positions where edges are present in the graph using a for loop.

Code:

import pprint
row_num = 6
col_num = 6
adjacency_matrix = []
for i in range(row_num):
    row = []
    for j in range(col_num):
        row.append(0)
    adjacency_matrix.append(row)
edges = [(1, 2), (2, 4), (2, 3), (3, 4), (4, 5), (3, 6), (5, 6)]
for edge in edges:
    row = edge[0]
    col = edge[1]
    adjacency_matrix[row - 1][col - 1] = 1
    adjacency_matrix[col - 1][row - 1] = 1

print("The edges in the graph are:")
print(edges)
print("The adjacency matrix is:")
pprint.pprint(adjacency_matrix)

Output:

The edges in the graph are:
[(1, 2), (2, 4), (2, 3), (3, 4), (4, 5), (3, 6), (5, 6)]
The adjacency matrix is:
[[0, 1, 0, 0, 0, 0],
 [1, 0, 1, 1, 0, 0],
 [0, 1, 0, 1, 0, 1],
 [0, 1, 1, 0, 1, 0],
 [0, 0, 0, 1, 0, 1],
 [0, 0, 1, 0, 1, 0]]

In the code, you can observe that we have 0-based indexing. Due to this, each node (i,j) is represented by the position (i-1,j-1) in the adjacency matrix.

To create an adjacency matrix for a weighted graph, we will first create an n x n 2-dimensional list having 0s. After that, we will assign the weight of edge eij at the position (i,j) in the matrix.

You can observe this in the following example.

import pprint

row_num = 6
col_num = 6
adjacency_matrix = []
for i in range(row_num):
    row = []
    for j in range(col_num):
        row.append(0)
    adjacency_matrix.append(row)
weighted_edges = [(1, 2, 5), (2, 4, 12), (2, 3, 1), (3, 4, 8), (4, 5, 7), (3, 6, 4), (5, 6, 2)]
for edge in weighted_edges:
    row = edge[0]
    col = edge[1]
    weight = edge[2]
    adjacency_matrix[row - 1][col - 1] = weight
    adjacency_matrix[col - 1][row - 1] = weight

print("The edges in the graph are:")
print(weighted_edges)
print("The adjacency matrix is:")
pprint.pprint(adjacency_matrix)

Output:

The edges in the graph are:
[(1, 2, 5), (2, 4, 12), (2, 3, 1), (3, 4, 8), (4, 5, 7), (3, 6, 4), (5, 6, 2)]
The adjacency matrix is:
[[0, 5, 0, 0, 0, 0],
 [5, 0, 1, 12, 0, 0],
 [0, 1, 0, 8, 0, 4],
 [0, 12, 8, 0, 7, 0],
 [0, 0, 0, 7, 0, 2],
 [0, 0, 4, 0, 2, 0]]

In the above code, the edges have been represented using a triplet of numbers. The first 2 numbers represent the nodes of the graph that are connected by the edge.

The third number represents the weight of the edge.

Create an Adjacency Matrix in Python Using the NumPy Module

To make an adjacency matrix for a graph using the NumPy module, we can use the np.zeros() method.

The np.zeros() method takes a tuple in the form of (row_num,col_num) as its input argument and returns a two-dimensional matrix of shape row_num x col_num. Here, row_num and col_num are the number of rows and columns in the matrix.

We will use the following steps to create an adjacency matrix using the np.zeros() method.

  • First, we will create a size n x n matrix by passing a tuple (n,n) to the zeros() method.
  • Then, we will update the values to 1 at the position (i-1,j-1) for every edge eij in the graph; here, we use 0-based indexing. Due to this, the node (i,j) is represented by the position (i-1,j-1) in the code.

After executing the above steps, we will get the adjacency matrix, as shown in the following example.

import pprint
import numpy as np

row_num = 6
col_num = 6
adjacency_matrix = np.zeros((row_num, col_num),dtype=int)
edges = [(1, 2), (2, 4), (2, 3), (3, 4), (4, 5), (3, 6), (5, 6)]
for edge in edges:
    row = edge[0]
    col = edge[1]
    adjacency_matrix[row - 1][col - 1] = 1
    adjacency_matrix[col - 1][row - 1] = 1

print("The edges in the graph are:")
print(edges)
print("The adjacency matrix is:")
pprint.pprint(adjacency_matrix)

Output:

The edges in the graph are:
[(1, 2), (2, 4), (2, 3), (3, 4), (4, 5), (3, 6), (5, 6)]
The adjacency matrix is:
array([[0, 1, 0, 0, 0, 0],
       [1, 0, 1, 1, 0, 0],
       [0, 1, 0, 1, 0, 1],
       [0, 1, 1, 0, 1, 0],
       [0, 0, 0, 1, 0, 1],
       [0, 0, 1, 0, 1, 0]])

To create the adjacency matrix for the weighted graphs, we will update the values at the position (i,j) to the weight of the edge eij as shown below.

import pprint
import numpy as np
row_num = 6
col_num = 6
adjacency_matrix = np.zeros((row_num, col_num), dtype=int)
weighted_edges = [(1, 2, 5), (2, 4, 12), (2, 3, 1), (3, 4, 8), (4, 5, 7), (3, 6, 4), (5, 6, 2)]
for edge in weighted_edges:
    row = edge[0]
    col = edge[1]
    weight = edge[2]
    adjacency_matrix[row - 1][col - 1] = weight
    adjacency_matrix[col - 1][row - 1] = weight

print("The edges in the graph are:")
print(weighted_edges)
print("The adjacency matrix is:")
pprint.pprint(adjacency_matrix)

Output:

The edges in the graph are:
[(1, 2, 5), (2, 4, 12), (2, 3, 1), (3, 4, 8), (4, 5, 7), (3, 6, 4), (5, 6, 2)]
The adjacency matrix is:
array([[ 0,  5,  0,  0,  0,  0],
       [ 5,  0,  1, 12,  0,  0],
       [ 0,  1,  0,  8,  0,  4],
       [ 0, 12,  8,  0,  7,  0],
       [ 0,  0,  0,  7,  0,  2],
       [ 0,  0,  4,  0,  2,  0]])

Conclusion

This article discusses two ways to implement an adjacency matrix in Python. We suggest you implement an adjacency matrix with the NumPy module as it is much more efficient in terms of storage requirements.

Also, performing different operations on a NumPy array is much more efficient regarding time and memory requirements.

Related Article - Python Matrix

  • Create Identity Matrix With Python
  • Diagonal Matrix in Python
  • Sparse Matrix in Python
  • Transpose a Matrix in Python
  • Print Matrix in Python