Graph representation in python on Adjacency list

Graph representation
Spread the love

A Graph is a non-linear data structure consisting of nodes and edges. The nodes are sometimes also referred to as vertices and the edges are lines or arcs that connect any two nodes in the graph. We denote graph like this equation G(e,v).

We can input graphs on the computer in two ways. There are the Adjacency and the Adjacency matrix. In this tutorial, I will show you how to you input graph using python. To implement adjacency list in python,first you have to knowledge about dictionary and list data-structure in python.

Python Dictionaries

Dictionaries are used to store data values in key: value pairs. A dictionary is a collection that is ordered, changeable, and does not allow duplicates. Dictionary items are ordered, changeable, and does not allow duplicates.

person = {
  "name": "Shahin",
  "age": "22",
  "profession": "Teacher"
}

Python Lists

Lists are used to store multiple items in a single variable.Lists are one of 4 built-in data types in Python used to store collections of data, the other 3 are Tuple, Set, and Dictionary, all with different qualities and usage.Lists are created using square brackets

list = ["Shahin", "Omi", "Tanzim"]

Graph representation in python

Well, in this graph we can see that, it’s an indirect graph or we can say it’s a bidirectional graph.

Firstly, you have to write all nodes sequentially. Then add all nodes that are connected with the parent node. Let’s see the following code. You have to define it like this

"""
// simulation of a graph by adjacency list
------------------------
  A  -> B , D
------------------------
  B  -> A, C
------------------------
  C  -> B
------------------------
  D  -> E, F
------------------------
  E  -> D, F, G
------------------------
  F  -> D, E, H
------------------------
  G  -> E ,H
------------------------
  H  -> G ,F
------------------------
"""
Read More: Start a Django project from scratch and print hello world

Well, now let’s see the how to implement this graph in python. Let’s see the following code

class Graph:
    def __init__(self, nodes, is_directed=False):
        self.is_directed = is_directed
        self.nodes = nodes
        self.adj_list = {}

        for node in self.nodes:
            self.adj_list[node] = []

First, I created a class which name is Graph. This class has a constructor or init method, In this init method I pass two variables. There are nodes and is_directed. Initially is_directed’s value is equal to false, using this variable is you can add directed graph’s edges.

Well, inside the init method, I defined a couple of variables. They are a boolean another one is list and another one is a dictionary. After then I have executed a loop for initialize all nodes. Initially, all nodes don’t contain any edges.

Add New edge

Well, now I will show you how to add two nodes by an edge. Lets see this function.

def add_edge(self, u, v):
        self.adj_list[u].append(v)
        if not self.is_directed:
            self.adj_list[v].append(u)

Well, you can see this function takes two parameters. Inside the function, fist I append a new property in dictionary which I have defined in init method. After then check that this graph directed or not. If graph is’nt directed then append node each other.

Check this code

Now create an instance of this class then test the method.

nodes = ["A", "B", "C", "D", "E"]
graph = Graph(nodes)
graph.add_edge("A","B"):

Add Multiple Edges in Graph

Now create a method for add multiple edges in graph.

def add_multiple_edges(self, edges):
        for u, v in edges:
            self.add_edge(u, v)

This function takes a list that we have to pass when we call this function. Inside the function, I executed a loop then call add_edge method which I defined before. You may create a list which contain all edges

edges = [
    ("A", "C"),
    ("A", "B"),
    ("B", "D"),
    ("C", "D"),
    ("C", "E"),
    ("D", "E"),
]
graph.add_multiple_edges(edges)

Print Graph

Well, now time to print our graph. To do that create a function. Lets have a look following function.

def print_adj_list(self):
        for node in self.nodes:
            print("{} -> {}".format(node, self.adj_list[node]))

Well, In this function you can see that First I executed a loop. Inside this loop I print all nodes as well their edges.

Full code of Graph representation in Python


class Graph:
    def __init__(self, nodes, is_directed=False):
        self.is_directed = is_directed
        self.nodes = nodes
        self.adj_list = {}

        for node in self.nodes:
            self.adj_list[node] = []

    def print_adj_list(self):
        for node in self.nodes:
            print("{} -> {}".format(node, self.adj_list[node]))

    def add_edge(self, u, v):
        self.adj_list[u].append(v)
        if not self.is_directed:
            self.adj_list[v].append(u)

    def add_multiple_edges(self, edges):
        for u, v in edges:
            self.add_edge(u, v)

    def display(self):
        print("Ok!")


nodes = ["A", "B", "C", "D", "E"]
edges = [
    ("A", "C"),
    ("A", "B"),
    ("B", "D"),
    ("C", "D"),
    ("C", "E"),
    ("D", "E"),
]
graph = Graph(nodes)

graph.add_multiple_edges(edges)
graph.print_adj_list()

// Output
A -> ['C', 'B']
B -> ['A', 'D']
C -> ['A', 'D', 'E']
D -> ['B', 'C', 'E']
E -> ['C', 'D']
Read More: Implement Insertion Sort with Time complexity

Spread the love

About Anisur Rahman Shahin

Hello. My name is Shahin. I'm a tech enthusiast guy. Personally, I’m Optimistic and always in hurry kinda person. I'm a freelance web developer. I am working at Zakir Soft as Laravel Developer. My Portfolio website: https://devshahin.com/

View all posts by Anisur Rahman Shahin →

Leave a Reply

Your email address will not be published.