NAME :- KANISHQ MALHOTRA ROLL NO.
:- 23UCC554
Q 1)Python Code for A star algorithm:
import networkx as nx
def MinNumColors(Graph,colors):
color_map={}
def isSafe(node,color):
for neighbor in Graph[node]:
if neighbor in color_map and
color_map[neighbor]==color:
return False
return True
def solve(node):
if node is None:
return True
for color in colors:
if isSafe(node,color):
color_map[node]=color
next_node=next((n for n in Graph if n not in
color_map),None)
if solve(next_node):
return True
del color_map[node]
return False
start_node=next(iter(Graph))
if solve(start_node):
return color_map ,len(set(color_map.values()))
else:
return None,
Graph={
'SH':['MV','N'],
'MV':['SH','N','BRAN'],
'N':['MV','SH','BRAN','T','HES','NW'],
'BRAN':['MV','N','SACH'],
'SACH':['BRAN','BAY'],
'T':['N','HES','BAY'],
'HES':['N','T','NW','BAY','BW','RP'],
'NW':['HES','N','RP'],
'BW':['HES','RP','BAY'],
'RP':['NW','BW','HES','SAAR'],
'BAY':['HES','T','SACH','BW'],
'SAAR':['RP']
}
colors=['Green','Red','Pink','White','Black','Blue']
colorSolution,minColors=MinNumColors(Graph,colors)
if colorSolution:
print("Minimum color:",minColors)
print("Colored Graph:",colorSolution)
else:
print("No solution found”)
OUTPUT:
Minimum color: 4
Colored Graph: {'SH': 'Green', 'MV': 'Red', 'N': 'Pink', 'BRAN':
'White', 'SACH': 'Green', 'T': 'Red', 'HES': 'White', 'NW': 'Pink',
'BW': 'Red', 'RP': 'Green', 'BAY': 'Pink', 'SAAR': ‘White'}
EXPLAINATION:
This code solves a graph coloring problem, where the task is to
color the nodes of a graph so that no two adjacent nodes share the
same color, using the minimum number of colors possible from a
given set
The MinNumColors function tries to assign colors to each node,
ensuring that no two connected nodes have the same color.
• color_map: Stores the color assigned to each node.
• isSafe(node, color): Checks if assigning a color to a node is
valid by ensuring none of its neighbors have the same color.
• solve(node): A recursive backtracking function that attempts to
color the entire graph by trying different colors for each node.
The algorithm successfully assigns colors to all nodes using 4
colors (Green, Red, Pink, and White)
The solution ef ciently nds a valid con guration and demonstrates
how backtracking can be used to solve graph problems like this.
Q 2)ALGORITHM FOR GRID-BASED PATHFINDING:
!pip install python-constraint
from constraint import *
adjList = {
"SH" : ['N',"MV"],
"MV" : ["SH",'N',"BRAN"],
fi
fi
fi
'N' : ["NW",'T',"HES","BRAN","MV","SH"],
"BRAN" : ['N',"SACH","MV"],
"NW" : ["HES","RP",'N'],
'T' : ['N',"HES","BAY"],
"HES" : ['N',"RP","BAY","NW",'T',"BW"],
"BW" : ["RP","BAY","HES"],
"RP" : ["BW","NW","SAAR","HES"],
"SAAR" : ["RP"],
"BAY" : ['T',"SACH","HES","BW"],
"SACH" : ["BAY","BRAN"]
};
inbuilt_AdjList = nx.Graph(adjList);
inbuilt_answer = nx.coloring.greedy_color(inbuilt_AdjList);
print("Assigned colors to nodes are : ")
print(inbuilt_answer);
inbuilt_total = max(inbuilt_answer.values())+1;
print("Max colors used are :",inbuilt_total); # due to 0 - based
indexing
OUTPUT:
{'SH': 0, 'N': 2, 'MV': 1, 'BRAN': 3, 'SACH': 0, 'NW': 1, 'T': 1,
'HES': 3, 'BW': 2, 'RP': 0, 'SAAR': 1, 'BAY': 2}
Max colors used are: 4
EXPLAINATION:
This code solves a graph coloring problem using NetworkX, a popular
Python library for working with graphs. The graph is represented by an
adjacency list where each node is connected to its neighbors. After
de ning the graph, the code uses NetworkX’s greedy_color()
function to assign colors to nodes. The greedy approach assigns the
smallest possible color to each node while ensuring no two connected
nodes share the same color. The output shows the color assigned to each
node, like 'SH': 0 and 'MV': 1, where numbers represent colors.
Since colors are indexed from zero, the total number of colors used is
calculated by adding one to the highest color value. In this case, it uses
four colors ef ciently to color the entire graph without con icts. This
approach showcases how built-in functions can solve complex graph
problems quickly and effectively.
fi
fi
fl
