Converting between Edge List and Adjacency List Graph Representation

In this article, we will explore on how to convert from edge list representation of a graph to adjacency list 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 List?

An adjacency list is another way of representing a graph, where each node is associated with a list of its neighboring nodes (the nodes it is connected to). This representation is often more efficient for sparse graphs, where each node has only a few connections.

For the same example graph above, the adjacency list would be:

A: [B]
B: [A, C]
C: [B, D]
D: [C]

Refer to this article for more information: Adjacency List 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 List

To convert an edge list to an adjacency list, iterate through each edge in the edge list and build the adjacency list by adding the destination node to the neighbors list of the source node. If the graph is bidirectional, add the reverse edge as well, so an edge [source, destination] also implies that an edge [destination, source] is present. In the case of a directed graph, only add the edge as specified without the reverse.

# Function to convert edge representation to adjacency list
def convert_to_adjacency_list(edges, num_vertices):
  # Initialize an empty list of size "num_vertices"
  # To store the adjacency list of each vertex
  adjacency_list = [[] for _ in range(num_vertices)]
  # Iterate through the edges
  for edge in edges:
    # Get the source and destination nodes
    source = edge[0]
    destination = edge[1]
    # Add the destination node to the source node's list
    # Add the source node to the destination node's list
    # (since the graph is bidirectional)
  # Return the adjacency list
  return adjacency_list
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_list = convert_to_adjacency_list(edge_list, 6)
print("For the following Edge list:")
print("Below is the Adjacency list:")
for vertex in range(num_vertices):
  print(f"{vertex} : {adj_list[vertex]}")

Converting from Adjacency List to Edge List

To convert from an adjacency list to an edge list, we iterate through each node and its list of neighbors in the adjacency list. For each neighbor of a node, we create an edge pair [source, destination] and add it to the edge list. Here source refers to the for which neighbors are being iterated and destination refers to the current neighbor.

# Function to convert adjacency list to edge representation
def convert_to_edge_list(adjacency_list):
  # Initialize an empty list to store the edges
  edges = []
  # Iterate through the adjacency list
  for vertex, neighbors in enumerate(adjacency_list):
    # Iterate through the vertices reachable from the current vertex
    for neighbor in neighbors:
      # Add the edge (vertex, neighbor) to the edges list
      edges.append((vertex, neighbor))
  # Return the list of edges
  return edges

adj_list = [[1, 2], [0, 2, 3], [0, 1, 4, 5], [1], [2], [2]]
edge_list = convert_to_edge_list(adj_list)
print("For the following Adjacency list:")
for vertex in range(len(adj_list)):
  print(f"{vertex} : {adj_list[vertex]}")
print("Below is the Edge list:")