Algotree > Algorithms > Adjacency Lists > Python : Creating adjacency list for storing graph

Python : Creating adjacency list for storing graph

Storing graph as an adjacency list using a list of the lists

Below is a simple example of a graph where each node has a number that uniquely identifies it and differentiates it from other nodes in the graph. Such a graph can be stored in an adjacency list where each node has a list of all the adjacent nodes that it is connected to.
An adjacency list can be implemented as a dictionary.

Example : In the below adjacency list we can see
a) Node 0 has a list storing adjacent nodes 1 and 2.
b) Node 1 has a list storing adjacent nodes 0, 3 and 4.

Storing graph using list of lists

Python : Storing graph in an adjacency list using list of lists.

from collections import defaultdict

class Graph:

    def __init__(self, nodes : int) :
        # Store the adjacency list as a dictionary
        # { 0 : [ 1, 2 ], 1 : [ 3, 4 ] }
        
        # The default dictionary would create an empty list as a default (value)
        # for the nonexistent keys.
        self.adjlist = defaultdict(list) 
        self.nodes = nodes

    # Assuming that the edge is bidirectional
    def AddEdge (self, src : int, dst : int) :

        self.adjlist[src].append(dst)
        self.adjlist[dst].append(src)

    def Display_AdjList(self) :
        for item in self.adjlist.items() :
            print (item)

def main():

    nodes = 7 

    g = Graph(nodes)

    g.AddEdge(0, 1)
    g.AddEdge(0, 2)
    g.AddEdge(1, 3)
    g.AddEdge(1, 4)
    g.AddEdge(2, 3)
    g.AddEdge(3, 5)
    g.AddEdge(4, 6)
    g.AddEdge(5, 6)

    print("Adjacency list for storing graph")
    g.Display_AdjList()

if __name__ == "__main__" :
    main()

Output of Adjacency List implementation in Python

Adjacency list for storing graph
(0, [1, 2])
(1, [0, 3, 4])
(2, [0, 3])
(3, [1, 2, 5])
(4, [1, 6])
(5, [3, 6])
(6, [4, 5])

Storing graph as an adjacency list using a map of node and list of nodes

Below is an example of a graph where each node has a name (string) and an id (number) that uniquely identifies it and differentiates it from other nodes in the graph. Such a graph can be stored in an adjacency list where each node has a list of all the adjacent nodes that it is connected to.
An adjacency list for such a graph can be implemented as a dictionary in Python.

Example : In the below adjacency list we can see
a) Node ( Alfa, 1 ) has a list storing adjacent nodes ( Cod, 2 ), ( Pi, 3 ) and ( Ram , 4)

Storing graph using map

Python 3.7

Python : Storing graph in an adjacency list using dataclass

Python : Storing graph in an adjacency list using map of string and list of string.

from collections import defaultdict

class Node :

    def __init__(self, name : str, id_num : int) :
        self.name = name
        self.id_num = id_num

    def __repr__(self) :
        return self.name + " " + str(self.id_num)

class Graph :

    def __init__(self, nodes : int) :
        # Store the adjacency list as a dictionary
        # The default dictionary would create an empty list as a default (value)
        # for the nonexistent keys.
        self.adjlist = defaultdict(list)
        self.nodes = nodes

    # Assuming that the edge is bidirectional
    def AddEdge (self, src_node : Node(str,int), dst_node : Node(str,int)) :

        self.adjlist[src_node].append(dst_node)
        self.adjlist[dst_node].append(src_node)

    def Display_AdjList (self) :
        for item in self.adjlist.items() :
            print (str(item))

def main() :

    nodes = 7

    node_alfa = Node("Alfa", 1)
    node_cod  = Node("Cod", 2)
    node_pi   = Node("Pi", 3)
    node_ram  = Node("Ram", 4)
    node_yo  = Node("Yo", 5)

    g = Graph(nodes)

    g.AddEdge(node_alfa, node_cod)
    g.AddEdge(node_alfa, node_pi)
    g.AddEdge(node_alfa, node_ram)
    g.AddEdge(node_cod, node_ram)
    g.AddEdge(node_pi, node_ram)
    g.AddEdge(node_pi, node_yo)

    print("Adjacency list for storing graph\n")
    g.Display_AdjList()

if __name__ == "__main__" :
    main()

Output

Adjacency list for storing graph

(Alfa 1, [Cod 2, Pi 3, Ram 4])
(Cod 2, [Alfa 1, Ram 4])
(Pi 3, [Alfa 1, Ram 4, Yo 5])
(Ram 4, [Alfa 1, Cod 2, Pi 3])
(Yo 5, [Pi 3])