DSAGraphs Implementation

A Basic Graph Implementation

Before we can run algorithms on a Graph, we must first implement it somehow.

To implement a Graph we will use anAdjacency Matrix, like the one below.

To store data for each vertex, in this case the letters A, B, C, and D, the data is put in a separate array that matches the indexes in the adjacency matrix, like this:

vertexData = [ 'A', 'B', 'C', 'D']

For an undirected and not weighted Graph, like in the image above, an edge between verticesi andj is stored with value1. It is stored as1 on both places(j,i) and(i,j) because the edge goes in both directions. As you can see, the matrix becomes diagonally symmetric for such undirected Graphs.

Let's look at something more specific. In the adjacency matrix above, vertex A is on index0, and vertex D is on index3, so we get the edge between A and D stored as value1 in position(0,3) and(3,0), because the edge goes in both directions.

Below is a basic implementation of the undirected Graph from the image above.

vertexData = ['A', 'B', 'C', 'D']adjacency_matrix = [    [0, 1, 1, 1],  # Edges for A    [1, 0, 1, 0],  # Edges for B    [1, 1, 0, 0],  # Edges for C    [1, 0, 0, 0]   # Edges for D]def print_adjacency_matrix(matrix):    print("\nAdjacency Matrix:")    for row in matrix:        print(row)print('vertexData:',vertexData)print_adjacency_matrix(adjacency_matrix)

This implementation is basically just a two dimensional array, but to get a better sense of how the vertices are connected by edges in the Graph we have just implemented, we can run this function:

def print_connections(matrix, vertices):    print("\nConnections for each vertex:")    for i in range(len(vertices)):        print(f"{vertices[i]}: ", end="")        for j in range(len(vertices)):            if matrix[i][j]:  # if there is a connection                print(vertices[j], end=" ")        print()  # new line

Graph Implementation Using Classes

A more proper way to store a Graph is to add an abstraction layer using classes so that a Graph's vertices, edges, and relevant methods, like algorithms that we will implement later, are contained in one place.

Programming languages with built-in object-oriented functionality like Python and Java, make implementation of Graphs using classes much easier than languages like C, without this built-in functionality.

Here is how the undirected Graph above can be implemented using classes.

class Graph:    def __init__(self, size):        self.adj_matrix = [[0] * size for _ in range(size)]        self.size = size        self.vertex_data = [''] * size      def add_edge(self, u, v):        if 0<= u< self.size and 0<= v< self.size:            self.adj_matrix[u][v] = 1            self.adj_matrix[v][u] = 1    def add_vertex_data(self, vertex, data):        if 0<= vertex< self.size:            self.vertex_data[vertex] = data    def print_graph(self):        print("Adjacency Matrix:")        for row in self.adj_matrix:            print(' '.join(map(str, row)))        print("\nVertex Data:")        for vertex, data in enumerate(self.vertex_data):            print(f"Vertex {vertex}: {data}")g = Graph(4)g.add_vertex_data(0, 'A')g.add_vertex_data(1, 'B')g.add_vertex_data(2, 'C')g.add_vertex_data(3, 'D')g.add_edge(0, 1)  # A - Bg.add_edge(0, 2)  # A - Cg.add_edge(0, 3)  # A - Dg.add_edge(1, 2)  # B - Cg.print_graph()

In the code above, the matrix symmetry we get for undirected Graphs is provided for on line 9 and 10, and this saves us some code when initializing the edges in the Graph on lines 29-32.

Implementation of Directed and Weighted Graphs

To implement a Graph that is directed and weighted, we just need to do a few changes to previous implementation of the undirected Graph.

To create directed Graphs, we just need to remove line 10 in the previous example code, so that the matrix is not automatically symmetric anymore.

The second change we need to do is to add aweight argument to theadd_edge() method, so that instead of just having value1 to indicate that there is an edge between two vertices, we use the actual weight value to define the edge.

Below is the implementation of the directed and weighted Graph above.

class Graph:    def __init__(self, size):        self.adj_matrix = [[None] * size for _ in range(size)]        self.size = size        self.vertex_data = [''] * size      def add_edge(self, u, v, weight):        if 0<= u< self.size and 0<= v< self.size:            self.adj_matrix[u][v] = weightself.adj_matrix[v][u] = weight    def add_vertex_data(self, vertex, data):        if 0<= vertex< self.size:            self.vertex_data[vertex] = data    def print_graph(self):        print("Adjacency Matrix:")        for row in self.adj_matrix:            print(' '.join(map(lambda x: str(x) if x is not None else '0', row)))        print("\nVertex Data:")        for vertex, data in enumerate(self.vertex_data):            print(f"Vertex {vertex}: {data}")g = Graph(4)g.add_vertex_data(0, 'A')g.add_vertex_data(1, 'B')g.add_vertex_data(2, 'C')g.add_vertex_data(3, 'D')g.add_edge(0, 1, 3)  # A -> B with weight 3g.add_edge(0, 2, 2)  # A -> C with weight 2g.add_edge(3, 0, 4)  # D -> A with weight 4g.add_edge(2, 1, 1)  # C -> B with weight 1g.print_graph()

Line 3:All edges are set toNone initially.

Line 7:The weight can now be added to an edge with the additionalweight argument.

Line 10: By removing line 10, the Graph can now be set up as being directed.

On the next page we will see how Graphs can be traversed, and on the next pages after that we will look at different algorithms that can run on the Graph data structure.

The edges, and edge weights, in a graph are normally implemented in an matrix.