In this assignment, you are going to write a Java program to do the second part
ID: 3599298 • Letter: I
Question
In this assignment, you are going to write a Java program to do the second part of the coloring algorithm. 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 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.
YOUR TASKS • Write a Java program called “Color” • The program should read two parameters from the command line
o The first parameter is a data filename
o The second parameter is the number of colors (K)
o Implement this part of the algorithm described above
o Write a note to describe how I can “javac” your program
Explanation / Answer
// color.java
import java.util.Scanner;
import java.io.File;
import java.io.FileNotFoundException;
public class Color{
public static int findmin(int arr[], int nodes, int k)
{
int i,count,maxcount = 0, maxindex=-1, j;
for(i=0;i<nodes;i++)
{
count = 0;
for(j=0;j<nodes;j++)
{
if(arr[i*nodes + j] == 0)
count++;
}
if(count > maxcount)
{
if(count != nodes)
{
maxcount = count;
maxindex = i;
}
}
}
if((nodes - maxcount) > k && maxindex != -1)
maxindex = -2;
return maxindex;
}
public static void print_arr(int arr[], int nodes)
{
int i, j;
for(i=0;i<nodes;i++)
{
for(j=0;j<nodes;j++)
System.out.print(arr[i*nodes+j]);
System.out.print(" ");
}
}
public static void main(String[] args) {
File file = new File(args[0]);
int nodes=0;
int i=0, j;
int arr[] = new int[10000];
try{
Scanner sc = new Scanner(file);
nodes = sc.nextInt();
while(sc.hasNextInt()){
arr[i++] = sc.nextInt();
}
sc.close();
} catch (FileNotFoundException e) {
}
int k=0;
//k = Integer.parseInt(args[2]);
try{
k = Integer.parseInt(args[1]);
}
catch(Exception e1)
{
System.out.println("Error");
}
int mindegree = findmin(arr, nodes, k);
if(mindegree == -2)
{
print_arr(arr,nodes);
System.out.println(" The graph is not " + k + " colorable");
mindegree = -1;
}
while(mindegree != -1)
{
//System.out.println(" mindegree is=" + mindegree);
if(mindegree == -2 )
{
//flag= 1;
System.out.println(" The graph is not " + k + " colorable");
break;
}
else
{
j = 0;
for(j=0;j<nodes;j++)
arr[mindegree*nodes+j] = 0;
for(j=0;j<nodes;j++)
arr[j*nodes + mindegree] = 0;
print_arr(arr,nodes);
}
mindegree = findmin(arr, nodes, k);
}
}
}