Python : Adjacency list implementation for storing graph

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

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 in Python.

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. Implemented using list of lists in Python3

class Graph:

    def __init__(self, nodes) :
        # Store the adjacency list as a dictionary
        # 0 : { 1, 2 }
        # 1 : { 3, 4 }
        self.adjlist = {}
        self.nodes = nodes

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

        if src not in self.adjlist :
            self.adjlist[src] = []

        if dst not in self.adjlist :
            self.adjlist[dst] = []

        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 in Python

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 implemented in Python 3.7


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

class Node :

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

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

class Graph :

    def __init__(self, adjlist, nodes) :
        # Store the adjacency list as a dictionary
        # 0 : { 1, 2 }
        # 1 : { 3, 4 }
        self.adjlist = adjlist
        self.nodes = nodes

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

        if src_node not in self.adjlist :
            self.adjlist[src_node] = []

        if dst_node not in self.adjlist :
            self.adjlist[dst_node] = []

        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() :

    adjlist = {}
    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(adjlist, 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")
    g.Display_AdjList()

if __name__ == "__main__" :
    main()

Output of Adjacency List implementation in Python

Adjacency list for storing graph
(Yo 5, [Pi 3])
(Cod 2, [Alfa 1, Ram 4])
(Ram 4, [Alfa 1, Cod 2, Pi 3])
(Alfa 1, [Cod 2, Pi 3, Ram 4])
(Pi 3, [Alfa 1, Ram 4, Yo 5])

Copyright © 2020, Algotree.org.
All rights reserved.