Write a Java program to implement the 2 part K-coloring problem described below:
ID: 3597588 • Letter: W
Question
Write a Java program to implement the 2 part K-coloring problem described below:
First step: After you read data, you are going to determine whether the graph is colorable using K colors where K is the second parameter from the command line. The following is the part of the algorithm that you need to implement in this assignment. • Sort all the nodes based on the number of edges connected to that node • If the minimum number of connected edges is larger than K, then output a message “The graph is not K colorable” and terminate the program; otherwise • Push the node that has the fewest connected edges to a stack • Remove the node that has the fewest connected edges • Print out the updated graph • Repeat until the graph is empty Using the first data file as an example, we have the input file as 6 0 0 1 0 0 1 0 0 1 0 1 1 1 1 0 1 1 1 0 0 1 0 1 1 0 1 1 1 0 1 1 1 1 1 1 0 >> java Color data1.txt 2 The output should be like 000000 001011 010111 001011 011101 011110 The graph is not 2 colorable ... >> java Color data1.txt 4 The output may look like the following 000000 001011 010111 001011 011101 011110 000000 000000 000111 001011 001101 001110 000000 000000 000000 000011 000101 000110 000000 000000 000000 000000 000001 000010 000000 000000 000000 000000 000000 000000. Once you have done that move on to the second step: After you push all the nodes to a stack, you still need to determine whether the graph is colorable using K colors and assign colors to nodes. The following is the part of the algorithm that you need to implement in this assignment. • Pop the node from the stack • Put the node back to the graph • Check assigned colors • Use an existing color if nodes are not connected; otherwise use a new color • If the number of used colors is larger than K+1 (Our color index starts from 1), then output a message “The graph is not K colorable” and terminate the program; otherwise • Repeat until the stack is empty Using the first data file as an example, we have the input file as 6 0 0 1 0 0 1 0 0 1 0 1 1 1 1 0 1 1 1 0 0 1 0 1 1 0 1 1 1 0 1 1 1 1 1 1 0 >> java Color data1.txt 3 The output should be like The graph is not 3 colorable ... >> java Color data1.txt 4 The output may look like the following Node = 0 Color = C3 Node = 1 Color = C3 Node = 2 Color = C4 Node = 3 Color = C3 Node = 4 Color = C2 Node = 5 Color = C1 Please note that the assignment of the colors is not unique. As long as it does not violate the constraint, the solution will be considered as a valid solution.
Explanation / Answer
* Java program for solution of M Coloring problem
using backtracking */
public class mColoringProblem {
final int V = 4;
int color[];
/* A utility function to check if the current
color assignment is safe for vertex v */
boolean isSafe(int v, int graph[][], int color[],
int c)
{
for (int i = 0; i < V; i++)
if (graph[v][i] == 1 && c == color[i])
return false;
return true;
}
/* A recursive utility function to solve m
coloring problem */
boolean graphColoringUtil(int graph[][], int m,
int color[], int v)
{
/* base case: If all vertices are assigned
a color then return true */
if (v == V)
return true;
/* Consider this vertex v and try different
colors */
for (int c = 1; c <= m; c++)
{
/* Check if assignment of color c to v
is fine*/
if (isSafe(v, graph, color, c))
{
color[v] = c;
/* recur to assign colors to rest
of the vertices */
if (graphColoringUtil(graph, m,
color, v + 1))
return true;
/* If assigning color c doesn't lead
to a solution then remove it */
color[v] = 0;
}
}
/* If no color can be assigned to this vertex
then return false */
return false;
}
/* This function solves the m Coloring problem using
Backtracking. It mainly uses graphColoringUtil()
to solve the problem. It returns false if the m
colors cannot be assigned, otherwise return true
and prints assignments of colors to all vertices.
Please note that there may be more than one
solutions, this function prints one of the
feasible solutions.*/
boolean graphColoring(int graph[][], int m)
{
// Initialize all color values as 0. This
// initialization is needed correct functioning
// of isSafe()
color = new int[V];
for (int i = 0; i < V; i++)
color[i] = 0;
// Call graphColoringUtil() for vertex 0
if (!graphColoringUtil(graph, m, color, 0))
{
System.out.println("Solution does not exist");
return false;
}
// Print the solution
printSolution(color);
return true;
}
/* A utility function to print solution */
void printSolution(int color[])
{
System.out.println("Solution Exists: Following" +
" are the assigned colors");
for (int i = 0; i < V; i++)
System.out.print(" " + color[i] + " ");
System.out.println();
}
// driver program to test above function
public static void main(String args[])
{
mColoringProblem Coloring = new mColoringProblem();
/* Create following graph and test whether it is
3 colorable
(3)---(2)
| / |
| / |
| / |
(0)---(1)
*/
int graph[][] = {{0, 1, 1, 1},
{1, 0, 1, 0},
{1, 1, 0, 1},
{1, 0, 1, 0},
};
int m = 3; // Number of colors
Coloring.graphColoring(graph, m);
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.