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:
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.
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(edge_list)
print("Below is the Adjacency Matrix")
for row in adj_mat:
for edge_status in row:
print(edge_status, end=' ')
print()
#include <iostream>
#include <vector>
// Function to convert edge list to adjacency matrix
std::vector<std::vector<bool>> convert_to_adjacency_matrix(const std::vector<std::pair<int, int>>& edge_list, int num_vertices) {
// Initialize the adjacency matrix with all false
std::vector<std::vector<bool>> adj_mat(num_vertices, std::vector<bool>(num_vertices, false));
// Iterate through all the edges
for (const auto& edge : edge_list) {
// Get the source and destination nodes
int source = edge.first;
int destination = edge.second;
// Mark the edge between source and destination in adjacency matrix
adj_mat[source][destination] = true;
// Mark the edge between destination and source in adjacency matrix
// (since the graph is bidirectional)
adj_mat[destination][source] = true;
}
return adj_mat;
}
int main() {
// Example usage
std::vector<std::pair<int, int>> edge_list = {{0, 1}, {0, 2}, {1, 2}, {1, 3}, {2, 4}, {2, 5}};
int num_vertices = 6;
std::vector<std::vector<bool>> adj_mat = convert_to_adjacency_matrix(edge_list, num_vertices);
std::cout << "For the following Edge list" << std::endl;
for (const auto& edge : edge_list) {
std::cout << "(" << edge.first << ", " << edge.second << ") ";
}
std::cout << std::endl << std::endl << "Below is the Adjacency Matrix" << std::endl;
for (const auto& row : adj_mat) {
for (bool edge_status : row) {
std::cout << edge_status << " ";
}
std::cout << std::endl;
}
return 0;
}
// Function to convert edge list to adjacency matrix
function convertToAdjacencyMatrix(edgeList, numVertices) {
// Initialize the adjacency matrix with all zeros
let adjMat = Array.from({ length: numVertices }, () => Array(numVertices).fill(0));
// Iterate through all the edges
for (let edge of edgeList) {
// Get the source and destination nodes
let source = edge[0];
let destination = edge[1];
// Mark the edge between source and destination in adjacency matrix
adjMat[source][destination] = 1;
// Mark the edge between destination and source in adjacency matrix
// (since the graph is bidirectional)
adjMat[destination][source] = 1;
}
return adjMat;
}
let edgeList = [[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
let numVertices = 6;
let adjMat = convertToAdjacencyMatrix(edgeList, numVertices);
console.log("For the following Edge list");
console.log(edgeList);
console.log("Below is the Adjacency Matrix");
for (let row of adjMat) {
console.log(row.join(" "));
}
import java.util.List;
import java.util.ArrayList;
public class Main {
// Function to convert edge list to adjacency matrix
public static int[][] convertToAdjacencyMatrix(List<int[]> edgeList, int numVertices) {
// Initialize the adjacency matrix with all zeros
int[][] adjMat = new int[numVertices][numVertices];
// Iterate through all the edges
for (int[] edge : edgeList) {
// Get the source and destination nodes
int source = edge[0];
int destination = edge[1];
// Mark the edge between source and destination in adjacency matrix
adjMat[source][destination] = 1;
// Mark the edge between destination and source in adjacency matrix
// (since the graph is bidirectional)
adjMat[destination][source] = 1;
}
return adjMat;
}
public static void main(String[] args) {
// Sample edge list
List<int[]> edgeList = new ArrayList<>();
edgeList.add(new int[] {0, 1});
edgeList.add(new int[] {0, 2});
edgeList.add(new int[] {1, 2});
edgeList.add(new int[] {1, 3});
edgeList.add(new int[] {2, 4});
edgeList.add(new int[] {2, 5});
// Number of vertices/nodes
int numVertices = 6;
// Convert edge list to adjacency matrix
int[][] adjMat = convertToAdjacencyMatrix(edgeList, numVertices);
// Print the edge list and adjacency matrix
System.out.println("For the following Edge list");
System.out.println(edgeList);
System.out.println("Below is the Adjacency Matrix");
for (int[] row : adjMat) {
for (int edgeStatus : row) {
System.out.print(edgeStatus + " ");
}
System.out.println();
}
}
}
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()
print("Below is the Edge List")
print(edge_list)
#include <iostream>
#include <vector>
// Function to convert adjacency matrix to edge list
std::vector<std::pair<int, int>> convert_to_edge_list(const std::vector<std::vector<bool>>& adjacency_matrix) {
// Initialize an empty list to store the edge list
std::vector<std::pair<int, int>> edge_list;
// Iterate through the rows of the adjacency matrix
for (int source = 0; source < adjacency_matrix.size(); source++) {
// Iterate through the columns of the adjacency matrix
for (int destination = 0; destination < adjacency_matrix[source].size(); destination++) {
// If the value in the adjacency matrix is 1
// Add an edge to the edge list from source to destination
if (adjacency_matrix[source][destination]) {
edge_list.emplace_back(source, destination);
}
}
}
// Return the edge list
return edge_list;
}
int main() {
// Example adjacency matrix
std::vector<std::vector<bool>> 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}
};
// Convert adjacency matrix to edge list
std::vector<std::pair<int, int>> edge_list = convert_to_edge_list(adj_mat);
// Print the adjacency matrix
std::cout << "For the following Adjacency Matrix" << std::endl;
for (const auto& row : adj_mat) {
for (bool edge_status : row) {
std::cout << edge_status << " ";
}
std::cout << std::endl;
}
// Print the edge list
std::cout << "Below is the Edge List" << std::endl;
for (const auto& edge : edge_list) {
std::cout << "(" << edge.first << ", " << edge.second << ")" << std::endl;
}
return 0;
}
// Function to convert adjacency matrix to edge list
function convert_to_edge_list(adjacency_matrix) {
// Initialize an empty list to store the edge list
let edge_list = [];
// Iterate through the rows of the adjacency matrix
for (let source = 0; source < adjacency_matrix.length; source++) {
// Iterate through the columns of the adjacency matrix
for (let destination = 0; destination < adjacency_matrix[source].length; destination++) {
// If the value in the adjacency matrix is 1
// Add an edge to the edge list from source to destination
if (adjacency_matrix[source][destination] === 1) {
edge_list.push([source, destination]);
}
}
}
// Return the edge list
return edge_list;
}
let 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]
];
let edge_list = convert_to_edge_list(adj_mat);
console.log("For the following Adjacency Matrix");
for (let row of adj_mat) {
console.log(row.join(" "));
}
console.log("Below is the Edge List");
console.log(edge_list);
import java.util.ArrayList;
import java.util.List;
public class Main {
// Function to convert adjacency matrix to edge list
public static List<Pair<Integer, Integer>> convertToEdgeList(int[][] adjacencyMatrix) {
// Initialize an empty list to store the edge list
List<Pair<Integer, Integer>> edgeList = new ArrayList<>();
// Iterate through the rows of the adjacency matrix
for (int source = 0; source < adjacencyMatrix.length; source++) {
// Iterate through the columns of the adjacency matrix
for (int destination = 0; destination < adjacencyMatrix[source].length; destination++) {
// If the value in the adjacency matrix is 1
// Add an edge to the edge list from source to destination
if (adjacencyMatrix[source][destination] == 1) {
edgeList.add(new Pair<>(source, destination));
}
}
}
// Return the edge list
return edgeList;
}
public static void main(String[] args) {
int[][] adjMat = {
{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}
};
List<Pair<Integer, Integer>> edgeList = convertToEdgeList(adjMat);
System.out.println("For the following Adjacency Matrix");
for (int[] row : adjMat) {
for (int edgeStatus : row) {
System.out.print(edgeStatus + " ");
}
System.out.println();
}
System.out.println("Below is the Edge List");
System.out.println(edgeList);
}
// Pair class to represent an edge
public static class Pair<T, U> {
private T first;
private U second;
public Pair(T first, U second) {
this.first = first;
this.second = second;
}
public T getFirst() {
return first;
}
public U getSecond() {
return second;
}
}
}