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.
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.