Write a program for graph coloring algorithm

Question

Write a Python code of the Graph coloring algorithm ( Taking input from user )

Answer 1

Here's a Python code for the graph coloring algorithm that takes input from the user:

# Python code for Graph Coloring Algorithm

# function to check if the current color assignment

# is safe for vertex v

def isSafe(v, graph, color, c):

for i in range(len(graph)):

if graph[v][i] == 1 and color[i] == c:

return False

return True

# function to assign colors recursively to vertices

def assignColorsUtil(graph, color, v, num_colors):

# base case: if all vertices are assigned a color

if v == len(graph):

return True

# try all possible colors for vertex v

for c in range(1, num_colors+1):

# check if color assignment is safe

if isSafe(v, graph, color, c):

color[v] = c

# recur for next vertex

if assignColorsUtil(graph, color, v+1, num_colors):

return True

# backtrack: remove color assignment for vertex v

color[v] = 0

return False

# main function to assign colors to vertices of a graph

def assignColors(graph, num_colors):

# initialize color array with all colors as 0 (no color)

color = [0] * len(graph)

# assign colors recursively to vertices

if not assignColorsUtil(graph, color, 0, num_colors):

print("No solution exists.")

return False

# print the color assignment for each vertex

print("Color assignments for vertices:")

for i in range(len(graph)):

print("Vertex", i+1, "-> Color", color[i])

return True

# take user input for the number of vertices and edges

n = int(input("Enter the number of vertices: "))

m = int(input("Enter the number of edges: "))

# initialize an empty adjacency matrix for the graph

graph = [[0] * n for i in range(n)]

# take user input for the edges of the graph

print("Enter the edges of the graph:")

for i in range(m):

u, v = map(int, input().split())

graph[u-1][v-1] = 1

graph[v-1][u-1] = 1

# take user input for the number of colors

num_colors = int(input("Enter the number of colors: "))

# call the assignColors function to assign colors to vertices

assignColors(graph, num_colors)

In this code, we first define two helper functions: isSafe and assignColorsUtil. The isSafe function checks if the current color assignment is safe for a given vertex by iterating through its neighbors and checking if any of them have the same color. The assignColorsUtil function is a recursive function that assigns colors to vertices one by one. It first checks if all vertices have been assigned a color, and if so, it returns True. Otherwise, it tries all possible colors for the current vertex, checks if the color assignment is safe, and recurses for the next vertex. If no color assignment works, it backtracks and removes the color assignment for the current vertex.

The main function, assignColors, takes user input for the number of vertices, edges, and colors, and constructs an adjacency matrix for the graph based on the user input for edges. It then calls the assignColorsUtil function to assign colors to vertices and prints the color assignment for each vertex. If no solution exists, it prints a message saying so.

Note that this code assumes that the graph is undirected. If you need to handle directed graphs, you will need to modify the isSafe function to only check for outgoing edges, and modify the adjacency matrix accordingly.

Here's an example of how you can use this code:

Enter the number of vertices: 4

Enter the number of edges: 4

Enter the edges of the graph:

1 2

1 3

2 3

3 4

Enter the number of colors: 3

Color assignments for vertices:

Vertex 1 -> Color 1

Vertex 2 -> Color 2

Vertex 3 -> Color 3

Vertex 4 -> Color 1

In this example, we have a graph with 4 vertices and 4 edges. The user input for edges specifies that there is an edge between vertices 1 and 2, an edge between vertices 1 and 3, an edge between vertices 2 and 3, and an edge between vertices 3 and 4. The user input for the number of colors is 3. The output shows that the algorithm was able to assign colors to all vertices such that no two adjacent vertices have the same color. Vertex 1 is assigned color 1, vertex 2 is assigned color 2, vertex 3 is assigned color 3, and vertex 4 is assigned color 1.