# 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)]
``````

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

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

#  Mark the edge between destination and source in adjacency matrix
# (since the graph is bidirectional)

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
print("For the following Edge list")
print(edge_list)
for edge_status in row:
print(edge_status, end=' ')
print()
``````

## 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
# Initialize an empty list to store the edge list
edge_list = []

# Iterate through the rows of the adjacency matrix
# Iterate through the columns of the adjacency matrix
# If the value in the adjacency matrix is 1
# Add an edge to the edge list from source to destinatoin
edge_list.append((source, destination))

# Return the edge list
return edge_list

[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]
]