Converting between Edge List and Adjacency Matrix Graph Representation

In this article, we will explore on how to convert from edge list representation of a graph to adjacency matrix representation and vice versa.

What is an Edge List?

An edge list is a way of representing a graph by listing all the edges (connections) between the nodes (vertices) of the graph. Each edge is represented as a pair of node IDs, indicating the two nodes that are connected by that edge. The edge list is typically stored as a list or array of these node pairs.

For example, if we have a graph with nodes A, B, C, and D, and the edges (A, B), (B, C), and (C, D), the edge list would be:

[(A, B), (B, C), (C, D)]

Refer to this article for more information: Edge List representation of a Graph

What is an Adjacency Matrix?

An Adjacency Matrix is another way of representing a graph. It is a square matrix where the rows and columns represent the nodes of the graph, and the values in the matrix indicate whether there is an edge between the corresponding nodes.

For example, if we have the same graph as before, with nodes A, B, C, and D, and the edges (A, B), (B, C), and (C, D), the adjacency matrix would look like this:

  A B C D
A 0 1 0 0
B 1 0 1 0
C 0 1 0 1
D 0 0 1 0

In this matrix, a value of 1 indicates that there is an edge between the corresponding row and column nodes, and a value of 0 indicates that there is no edge. This representation is more suitable for dense graphs where the number of edges are more.

Refer to this article for more information: Adjacency Matrix representation of a Graph

Example Graph Used For Conversion

For the examples below, a graph with the following nodes/vertices and edges is considered:

vertices = ['A', 'B', 'C', 'D', 'E', 'F']

edges = [['A','B'], ['A','C'], ['B','C'], ['B','D'], ['C','E'], ['C','F']]

In programmatic representation of a graph, each node or vertex is typically assigned a number between 0 and N-1, where N is the total number of nodes in the graph. This numbering is efficient in terms of storage and also allows us to use an array to represent the adjacency list or matrix, rather than a dictionary or hash table. This approach is more efficient because accessing elements in an array using the node ID/number as index is generally faster than accessing elements in a hash table or dictionary. Below is how the vertices and edges look like after optimizing the representation:

            A  B  C  D  E  F
vertices = [0, 1, 2, 3, 4, 5]

edges = [[0,1], [0,2], [1,2], [1,3], [2,4], [2,5]]

Converting from Edge List to Adjacency Matrix

To convert from an edge list to an adjacency matrix, we first initialize an N x N matrix with all elements set to 0, where N is the number of nodes. Then, we iterate through each edge in the edge list and set the corresponding elements in the matrix to 1 (or the weight of the edge, if applicable). For a bi-directional graph, we set both [source, destination] and [destination, source] entries in the matrix. For a directed graph, we only set the [source, destination] entry.

# Function to convert edge list to adjacency matrix
def convert_to_adjacency_matrix(edge_list, num_vertices):
  # Initialize the adjacency matrix with all zeros
  adj_mat = [[0 for _ in range(num_vertices)] for _ in range(num_vertices)]
  # Iterate through all the edges
  for edge in edge_list:
    # Get the source and destination nodes
    source = edge[0]
    destination = edge[1]
    # Mark the edge between source and destination in adjacency matrix
    adj_mat[source][destination] = 1
    #  Mark the edge between destination and source in adjacency matrix
    # (since the graph is bidirectional)
    adj_mat[destination][source] = 1
  return adj_mat

edge_list = [[0, 1], [0, 2], [1, 2], [1, 3], [2, 4], [2, 5]]
# There are 6 vertices/nodes in total
# The first vertex/node is labelled as 0
# And the last vertex/node is labelled as 5
num_vertices = 6
adj_mat = convert_to_adjacency_matrix(edge_list, num_vertices)
print("For the following Edge list")
print("Below is the Adjacency Matrix")
for row in adj_mat:
  for edge_status in row:
    print(edge_status, end=' ')

Converting from Adjacency Matrix to Edge List

To convert from an adjacency matrix to an edge list, we iterate through each element in the N x N matrix. For each non-zero element at position [i, j], we add the edge pair [i, j] to the edge list. In the code below, source variable refers to index i and destination variable refers to index j.

# Function to convert adjacency matrix to edge list
def convert_to_edge_list(adjacency_matrix):
  # Initialize an empty list to store the edge list
  edge_list = []

  # Iterate through the rows of the adjacency matrix
  for source in range(len(adjacency_matrix)):
    # Iterate through the columns of the adjacency matrix
    for destination in range(len(adjacency_matrix[source])):
      # If the value in the adjacency matrix is 1
      # Add an edge to the edge list from source to destinatoin
      if adjacency_matrix[source][destination] == 1:
        edge_list.append((source, destination))

  # Return the edge list
  return edge_list

adj_mat = [
  [0, 1, 1, 0, 0, 0],
  [1, 0, 1, 1, 0, 0],
  [1, 1, 0, 0, 1, 1],
  [0, 1, 0, 0, 0, 0],
  [0, 0, 1, 0, 0, 0],
  [0, 0, 1, 0, 0, 0]

edge_list = convert_to_edge_list(adj_mat)
print("For the following Adjacency Matrix")
for row in adj_mat:
  for edge_status in row:
    print(edge_status, end=' ')
print("Below is the Edge List")