Graph Representations#

Welcome to Day 19 of our 60 Days of Coding Algorithm Challenge! Today, we’ll dive deeper into various ways of representing graphs in code, exploring their pros and cons, and discussing when to use each representation.

Overview of Graph Representations#

There are several ways to represent a graph in computer memory. The choice of representation depends on the type of graph and the algorithms you plan to use. The most common representations are:

1. Adjacency Matrix
2. Adjacency List
3. Edge List
4. Incidence Matrix

Let’s explore each of these in detail.

1. Adjacency Matrix#

An adjacency matrix is a 2D array of size V x V where V is the number of vertices in the graph. The entry matrix[i][j] is 1 (or the edge weight for weighted graphs) if there is an edge from vertex i to vertex j, and 0 otherwise.

Implementation:#

 1class GraphMatrix:
 2    def __init__(self, num_vertices, directed=False):
 3        self.num_vertices = num_vertices
 4        self.directed = directed
 5        self.matrix = [[0 for _ in range(num_vertices)] for _ in range(num_vertices)]
 6
 7    def add_edge(self, v1, v2, weight=1):
 8        self.matrix[v1][v2] = weight
 9        if not self.directed:
10            self.matrix[v2][v1] = weight
11
12    def remove_edge(self, v1, v2):
13        self.matrix[v1][v2] = 0
14        if not self.directed:
15            self.matrix[v2][v1] = 0
16
17    def print_matrix(self):
18        for row in self.matrix:
19            print(row)
20
21# Example usage
22g = GraphMatrix(4)
23g.add_edge(0, 1)
24g.add_edge(0, 2)
25g.add_edge(1, 2)
26g.add_edge(2, 3)
27g.print_matrix()

Pros:#

• Constant time O(1) to check if there is an edge between two vertices
• Simple for undirected graphs
• Efficient for dense graphs

Cons:#

• Uses O(V^2) space, which can be wasteful for sparse graphs
• O(V^2) time to add or remove a vertex

2. Adjacency List#

An adjacency list represents a graph as an array of lists. The array index corresponds to a vertex, and each element in its list represents the vertices that form an edge with it.

Implementation:#

 1from collections import defaultdict
 2
 3class GraphList:
 4    def __init__(self, directed=False):
 5        self.graph = defaultdict(list)
 6        self.directed = directed
 7
 8    def add_edge(self, v1, v2):
 9        self.graph[v1].append(v2)
10        if not self.directed:
11            self.graph[v2].append(v1)
12
13    def remove_edge(self, v1, v2):
14        self.graph[v1].remove(v2)
15        if not self.directed:
16            self.graph[v2].remove(v1)
17
18    def print_list(self):
19        for vertex in self.graph:
20            print(f"{vertex}: {self.graph[vertex]}")
21
22# Example usage
23g = GraphList()
24g.add_edge(0, 1)
25g.add_edge(0, 2)
26g.add_edge(1, 2)
27g.add_edge(2, 3)
28g.print_list()

Pros:#

• Space-efficient for sparse graphs
• Faster to iterate over all edges
• Efficient addition and removal of edges

Cons:#

• Slower to check if there is an edge between two vertices (O(E) in the worst case)
• More complex to implement compared to adjacency matrix

3. Edge List#

An edge list is a representation where we store the graph simply as an unordered list of edges. Each edge is a pair of vertices.

Implementation:#

 1class GraphEdgeList:
 2    def __init__(self, directed=False):
 3        self.edges = []
 4        self.directed = directed
 5
 6    def add_edge(self, v1, v2):
 7        self.edges.append((v1, v2))
 8        if not self.directed:
 9            self.edges.append((v2, v1))
10
11    def remove_edge(self, v1, v2):
12        self.edges.remove((v1, v2))
13        if not self.directed:
14            self.edges.remove((v2, v1))
15
16    def print_edges(self):
17        print(self.edges)
18
19# Example usage
20g = GraphEdgeList()
21g.add_edge(0, 1)
22g.add_edge(0, 2)
23g.add_edge(1, 2)
24g.add_edge(2, 3)
25g.print_edges()

Pros:#

• Simple and intuitive
• Space-efficient for sparse graphs
• Efficient for algorithms that work directly with edges

Cons:#

• Inefficient for checking if there’s an edge between two vertices or finding adjacent vertices

4. Incidence Matrix#

An incidence matrix is a 2D array of size V x E where V is the number of vertices and E is the number of edges. For each column representing an edge, we mark the vertices it connects with 1 (or -1 and 1 for directed graphs).

Implementation:#

 1class GraphIncidenceMatrix:
 2    def __init__(self, num_vertices, directed=False):
 3        self.num_vertices = num_vertices
 4        self.directed = directed
 5        self.matrix = []
 6        self.edge_count = 0
 7
 8    def add_edge(self, v1, v2):
 9        column = [0] * self.num_vertices
10        column[v1] = 1
11        column[v2] = -1 if self.directed else 1
12        self.matrix.append(column)
13        self.edge_count += 1
14
15    def print_matrix(self):
16        for i in range(self.num_vertices):
17            row = [self.matrix[j][i] for j in range(self.edge_count)]
18            print(row)
19
20# Example usage
21g = GraphIncidenceMatrix(4)
22g.add_edge(0, 1)
23g.add_edge(0, 2)
24g.add_edge(1, 2)
25g.add_edge(2, 3)
26g.print_matrix()

Pros:#

• Can represent multigraphs (graphs with multiple edges between the same vertices)
• Useful for some graph algorithms and in certain mathematical treatments of graphs

Cons:#

• Not as commonly used as adjacency matrix or adjacency list
• Can be space-inefficient, especially for sparse graphs

Choosing the Right Representation#

The choice of graph representation depends on several factors:

1. Density of the graph: For dense graphs, adjacency matrix might be preferred. For sparse graphs, adjacency list or edge list are more space-efficient.

2. Types of operations: If you need to quickly check if there’s an edge between two vertices, adjacency matrix is better. If you need to iterate over all edges quickly, adjacency list or edge list might be preferable.

3. Type of graph: For weighted graphs, adjacency matrix or a modified adjacency list can be used. For multigraphs, incidence matrix or a modified adjacency list might be suitable.

4. Memory constraints: If memory is a concern, consider using adjacency list for sparse graphs.

5. Algorithmic requirements: Some algorithms work better with certain representations. For example, Kruskal’s algorithm for minimum spanning trees works well with an edge list.

Exercise#

1. Implement a function to convert between adjacency matrix and adjacency list representations.
2. Create a method to find all isolated vertices (vertices with no incoming or outgoing edges) in a graph, using each of the representations we’ve discussed.
3. Implement a function to check if a graph is bipartite, using both adjacency matrix and adjacency list representations. Compare the time complexity of your implementations.

Summary#

Today, we explored various ways to represent graphs in code, including adjacency matrices, adjacency lists, edge lists, and incidence matrices. We discussed the pros and cons of each representation and provided guidelines for choosing the right representation based on the specific requirements of your problem.

Understanding these different representations is crucial for implementing graph algorithms efficiently and solving graph-related problems effectively. As we progress through this challenge, we’ll use these representations to implement various graph algorithms.

Tomorrow, we’ll dive into graph traversal algorithms, starting with Depth-First Search (DFS) and Breadth-First Search (BFS). Stay tuned!

Solution#

 1def matrix_to_list(matrix):
 2    adj_list = {i: [] for i in range(len(matrix))}
 3    for i, row in enumerate(matrix):
 4        for j, weight in enumerate(row):
 5            if weight != 0:
 6                adj_list[i].append((j, weight))
 7    return adj_list
 8
 9def list_to_matrix(adj_list, num_vertices):
10    matrix = [[0] * num_vertices for _ in range(num_vertices)]
11    for u, neighbors in adj_list.items():
12        for v, weight in neighbors:
13            matrix[u][v] = weight
14    return matrix
15
16# Example usage
17matrix = [
18    [0, 1, 1, 0],
19    [1, 0, 1, 0],
20    [1, 1, 0, 1],
21    [0, 0, 1, 0],
22]
23adj = matrix_to_list(matrix)
24print(adj)
25print(list_to_matrix(adj, 4) == matrix)  # True