In this assignment, you are going to write a Java program to do the first part o
ID: 3588689 • Letter: I
Question
In this assignment, you are going to write a Java program to do the first part of the coloring algorithm. 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 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);
}
}
}