+

Create a graph using a dictionary in Python

In this article, we will see how to implement graph in python using dictionary data structure in python.
Keys of the used dictionary — these are the nodes of our graph, and the corresponding values ​​— lists with each node that are connected by an edge.
This simple graph has six nodes (af) and five arcs:

 a - & gt; cb - & gt; cb - & gt; ec - & gt; ac - & gt; bc - & gt; dc - & gt; ed - & gt; ce - & gt; ce - & gt; b 

It can be represented by the following Python data structure. It is a dictionary whose keys are the nodes of the graph. For each key, the corresponding value is a list containing the nodes that are connected by a direct arc from this node.

 graph = {"a": ["c"], "b": ["c", " e "]," c ": [" a "," b "," d "," e "]," d ": [" c "]," e ": [" c "," b "], "f": []} 

Graphic representation of the above example:

defaultdict : Usually Python dictionary will throw KeyError if you try to get an element with a key that is not currently in the dictionary. defaultdict allows that if the key is not found in the dictionary, then a new entry is created instead of the generated KeyError. The type of this new entry is specified by the defaultdict argument.
Python function to generate a graph:

 # definition of function def generate_edges (graph): edges = [] # for each node in graph for node in graph: # for each neighbor node of a single node for neighbor in graph [node]: # if edge exists then append edges.append ((node, neighbor)) return edges 

# Python program for
# checking the graph

 
# import of the graph dictionary

from collections import defaultdict

  
# function to add an edge to the graph

graph = defaultdict ( list )

def addEdge (graph, u, v):

  graph [u] .append (v)

 
# function definition

def generate_edges (graph):

edges = []

 

# for each node in the column

for node in graph:

 

  # for each adjacent node of one node

for neighbor in graph [node ]:

 

# if an edge exists, add

edges.append ((node, neighbor ))

return edges

 
# declaring the graph as a dictionary

addEdge (graph, `a` , ` c` )

addEdge (graph, `b` , ` c` )

addEdge (graph, `b` , `e` )

addEdge (graph, `c` , ` d` )

addEdge (graph, `c` , `e` )

addEdge (graph, `c` , `a` )

addEdge (graph, ` c` , `b` )

addEdge (graph, `e` , ` b` )

addEdge (graph, ` d` , ` c` )

addEdge (graph, `e` , ` c` )

 
# Function call drivers
# print the generated graph

print (generate_edges (graph)) 

Output:

 [(`a`,` c`), (`c`,` d`), (`c`,` e`), (`c`,` a`), (`c `,` b`), (`b`,` c`), (`b`,` e`), (`e`,` b`), (`e`,` c`), (`d `,` c`)] 

As we took the example of an undirected graph, we printed the same reb po twice, say, like (& # 39; a & # 39;, & # 39; c & # 39;) and (& # 39; c & # 39;, & # 39; a & # 39;). We can overcome this with a directed graph.

Here are some more graphical programs in Python:

  1. To generate a path from one node to another node :
    Using a Python dictionary, we can find the path from one node to another in a graph. The idea is similar to

    # Python program for generating the first
    # graph path from the provided nodes

     

    graph = {

    ` a` : [ `c` ],

    `b` : [ ` d` ],

    `c` : [ ` e` ],

    `d` : [ `a` , ` d` ] ,

    `e` : [ ` b` , `c` ]

    }

     
    # function to find the path

    def find_path (graph, start, end, path = []):

    path = path + [start]

    if start = = end:

    return path

    for node in graph [start]:

      if node not in path:

    newpath = find_path (graph, node, end, path)

    if newpath: 

    return newpath

      return None

      
    # Call driver function to print the path

    print (find_path (graph, `d` , ` c` ))

    Output:

     [`d`,` a`, `c`] 
  2. Program for generating all possible paths from one node to another. :
    In the above program, we generated the first possible path. Now let`s generate all possible paths from the start node to the end node. The basic functioning works the same as the above code. Where the difference occurs, instead of immediately returning the first path, it stores that path in a list with the name "path" in the example below. Finally, after iterating over all possible paths, it returns a list of paths. If there is no path from start node to end node, it returns None.

    # Python program to generate everything possible
    # graph path from the provided nodes

    graph = {

    ` a` : [ `c` ],

    ` b` : [ ` d` ],

    ` c` : [ `e` ],

    `d` : [ ` a` , `d` ],

    `e` : [ ` b` , `c` ]

    }

     
    # function to generate all possible paths

    def find_all_paths (graph, start, end, path = []):

    path = path + [start]

    if start = = end:

    r eturn [path]

    paths = []

    for node in graph [start ]:

    if node not in path:

    newpaths = find_all_paths (graph, node, end, path)

    for newpath in newpaths:

    paths.append (newpath)

      return paths

     
    # Call the driver function to print all
    # generated paths

    print ( find_all_paths (graph, `d` , ` c` ))

    Exit :

     [[`d`,` a`, `c`], [` d`, `a`,` c`]] 
  3. Program for generating the shortest path. :
    To get to the shortest of all paths, we use a slightly different approach, as shown below. In this, when we get the path from the start node to the end node, we compare the length of the path with a variable called shortest, which is initialized to None. If the length of the generated path is less than the length of the shortest, if the shortest is not None, the newly generated path is set to the value of the shortest. Again, if there is no path, None is returned

    # Python shortcut generator

     

    graph = {

    `a` : [ ` c` ],

    `b` : [ `d` ],

    ` c` : [ `e` ],

    `d` : [ ` a` , `d` ],

    ` e` : [ ` b` , `c` ]

    }

     
    # function to find the shortest path

    def find_shortest_path (graph, start, end, path = []):

    path = path + [start]

    if start = = end:

    return path

      shortest = None

    for node in graph [start]:

    if node not in path:

    newpath = find_shortest_path (graph, node, end, path)

      if newpath:

    if not shortest or len (newpath) & lt; len (shortest):

    shortest = newpath

    return shortest

      
    # Call driver function for printing
    # shortest path

    print (find_shortest_path (graph, `d` , `c` ))

    Output:

     [`d`,` a`, `c`] 

This article is updated Shivov Pradkhan (anuj_charm) and Rishabh Bansal . If you are as Python.Engineering and would like to contribute, you can also write an article using contribute.python.engineering or by posting an article contribute @ python.engineering. See my article appearing on the Python.Engineering homepage and help other geeks.

Please post comments if you find anything wrong or if you would like to share more information on the topic discussed above.

Get Solution for free from DataCamp guru