Generate a graph using Dictionary in Python
By Prashanth Gowda R SIn this tutorial, we will learn to generate a graph using a dictionary in Python. We will generate a graph using a dictionary and find out all the edges of the graph. And also, all possible paths from source to destination and the shortest path from source to the destination of the graph.
Generating a Graph using Dictionary
The keys of the dictionary are the nodes of the graph and the corresponding values are the list of its adjacent nodes.
from collections import defaultdict
class Graph:
def __init__(graph):
graph.dict = defaultdict(list)
def add(graph,node,adjacent_node):
graph.dict[node].append(adjacent_node)
graph.dict[adjacent_node].append(node)
graph = Graph()
graph.add('1','2')
graph.add('2','5')
graph.add('2','3')
graph.add('4','5')
graph.add('4','3')
graph.add('6','4')
graph.add('6','5')
print('Dictionary:',graph.dict)Output:
Dictionary: defaultdict(<class 'list'>, {'1': ['2'], '2': ['1', '5', '3'], '5': ['2', '4', '6'], '3': ['2', '4'], '4': ['5', '3', '6'], '6': ['4', '5']})- We have used the defaultdict which is present inside the collections module. Since we need the values to be a list, we have assigned the default_factory = list.
- For a directed graph, we will append only the adjacent nodes of the node. Where we can’t traverse in the opposite direction.
def add(graph,node,adjacent_node): graph.dict[node].append(adjacent_node)
Edges of the Graph
from collections import defaultdict
class Graph:
def __init__(graph):
graph.dict = defaultdict(list)
def add(graph,node,adjacent_node):
graph.dict[node].append(adjacent_node)
graph.dict[adjacent_node].append(node)
def edges(graph):
graph_edges = []
for node in graph.dict:
for adjacent_node in graph.dict[node]:
if (adjacent_node, node) not in graph_edges :
graph_edges.append((node, adjacent_node))
return graph_edges
graph = Graph()
graph.add('1','2')
graph.add('2','5')
graph.add('2','3')
graph.add('4','5')
graph.add('4','3')
graph.add('6','4')
graph.add('6','5')
print('Dictionary:',graph.dict)
print('Edges of the Graph:',graph.edges())Output:
Dictionary: defaultdict(<class 'list'>, {'1': ['2'], '2': ['1', '5', '3'], '5': ['2', '4', '6'], '3': ['2', '4'], '4': ['5', '3', '6'], '6': ['4', '5']})
Edges of the Graph: [('1', '2'), ('2', '5'), ('2', '3'), ('5', '4'), ('5', '6'), ('3', '4'), ('4', '6')]- Each node and its adjacent node is considered as an edge.
- We have used an if condition to avoid repetition.
All possible paths from source to destination
from collections import defaultdict
class Graph:
def __init__(graph):
graph.dict = defaultdict(list)
def add(graph,node,adjacent_node):
graph.dict[node].append(adjacent_node)
graph.dict[adjacent_node].append(node)
def all_paths(self, start, end, path =[]):
path = path + [start]
if( start == end ):
return [path]
all_paths = []
paths = []
for node in graph.dict[start]:
if( node not in path ):
paths = graph.all_paths(node, end, path)
for new in paths:
if (new not in all_paths):
all_paths.append(new)
return all_paths
graph = Graph()
graph.add('1','2')
graph.add('2','5')
graph.add('2','3')
graph.add('4','5')
graph.add('4','3')
graph.add('6','4')
graph.add('6','5')
print('Dictionary:',graph.dict)
print('All possible paths:',graph.all_paths('1','6'))
Output:
Dictionary: defaultdict(<class ‘list’>, {‘1’: [‘2’], ‘2’: [‘1’, ‘5’, ‘3’], ‘5’: [‘2’, ‘4’, ‘6’], ‘3’: [‘2’, ‘4’], ‘4’: [‘5’, ‘3’, ‘6’], ‘6’: [‘4’, ‘5’]})
All possible paths: [[‘1’, ‘2’, ‘5’, ‘4’, ‘6’], [‘1’, ‘2’, ‘5’, ‘6’], [‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’], [‘1’, ‘2’, ‘3’, ‘4’, ‘6’]]
- Using a recursive function, we will traverse the graph.
- We will keep a track of the path. If we reach the destination, we will add that path list.
- Use if condition to avoid repetition.
The shortest path from source to destination
from collections import defaultdict
class Graph:
def __init__(graph):
graph.dict = defaultdict(list)
def add(graph,node,adjacent_node):
graph.dict[node].append(adjacent_node)
graph.dict[adjacent_node].append(node)
def shortest_path(graph, start, end, path =[]):
path = path + [start]
if( start == end ):
return path
short_path = None
for node in graph.dict[start]:
if( node not in path ):
new_path = graph.shortest_path(node, end, path)
if( new_path ):
if( not short_path or len(new_path) < len(short_path) ):
short_path = new_path
return short_path
graph = Graph()
graph.add('1','2')
graph.add('2','5')
graph.add('2','3')
graph.add('4','5')
graph.add('4','3')
graph.add('6','4')
graph.add('6','5')
print('Dictionary:',graph.dict)
print('Shortest path:',graph.shortest_path('1','6'))
Output:
Dictionary: defaultdict(<class 'list'>, {'1': ['2'], '2': ['1', '5', '3'], '5': ['2', '4', '6'], '3': ['2', '4'], '4': ['5', '3', '6'], '6': ['4', '5']})
Shortest path: ['1', '2', '5', '6']- This is similar to the above function. We will traverse the graph using a recursive function and keep the track of the path.
- If we reach the destination, we will compare the length of the path with the shortest path.
- The shortest path is initially None. If the length of the new path is less than the shortest path and not None, it is considered as the shortest path.
- If there is no path from source to destination, the function will return None.
Here is how the complete code should look like
from collections import defaultdict
class Graph:
def __init__(graph):
graph.dict = defaultdict(list)
def add(graph,node,adjacent_node):
graph.dict[node].append(adjacent_node)
graph.dict[adjacent_node].append(node)
def edges(graph):
graph_edges = []
for node in graph.dict:
for adjacent_node in graph.dict[node]:
if (adjacent_node, node) not in graph_edges :
graph_edges.append((node, adjacent_node))
return graph_edges
def all_paths(self, start, end, path =[]):
path = path + [start]
if start == end:
return [path]
all_paths = []
paths = []
for node in graph.dict[start]:
if node not in path:
paths = graph.all_paths(node, end, path)
for new in paths:
all_paths.append(new)
return all_paths
def shortest_path(graph, start, end, path =[]):
path = path + [start]
if( start == end ):
return path
short_path = None
for node in graph.dict[start]:
if( node not in path ):
new_path = graph.shortest_path(node, end, path)
if( new_path ):
if( not short_path or len(new_path) < len(short_path) ):
short_path = new_path
return short_path
graph = Graph()
graph.add('1','2')
graph.add('2','5')
graph.add('2','3')
graph.add('4','5')
graph.add('4','3')
graph.add('6','4')
graph.add('6','5')
print('Dictionary:',graph.dict)
print('Edges of the Graph:',graph.edges())
print('All possible paths:',graph.all_paths('1','6'))
print('Shortest path:',graph.shortest_path('1','6'))
Output:
Dictionary: defaultdict(<class 'list'>, {'1': ['2'], '2': ['1', '5', '3'], '5': ['2', '4', '6'], '3': ['2', '4'], '4': ['5', '3', '6'], '6': ['4', '5']})
Edges of the Graph: [('1', '2'), ('2', '5'), ('2', '3'), ('5', '4'), ('5', '6'), ('3', '4'), ('4', '6')]
All possible paths: [['1', '2', '5', '4', '6'], ['1', '2', '5', '6'], ['1', '2', '3', '4', '5', '6'], ['1', '2', '3', '4', '6']]
Shortest path: ['1', '2', '5', '6']I hope you have understood the code..!
If you have any queries, please feel free to drop in your comments.
Also read: Reverse a queue in Python.
Thank you…😊
Leave a Reply