assignment

Write a program that will compute the chromatic number of a graph and color the vertices using the chromatic number of colors. The input to the program is a file containing the graph. The input file contains the number of vertices and the number of edges at the top and the list of edges at in the subsequent lines. The output file contains the chromatic number at the top and the coloring of vertices using the chromatic number of colors in the subsequent lines. The vertices are named 1,2,3... and the colors are also named 1,2,3...
A brute force algorithm to solve the coloring problem is given. Translate the algorithm into a Java program. The program must be based on the algorithm.
pseudo code is pasted below
//graph G, vertices n, vertices are numbered 0,1..n-1
//G is stored in adjacency matrix p (MUST BE STORED IN ADJACENCY MATRIX)
//colors are stored in array q
//q[i] has color of vertex i, initially all 0

//color G using minimum number of colors, returns chromatic number
int color()
{
for(i=1 to n)
{
//if G can be colored using i colors starting at vertex 0
if (color(0,i))
chromatic number is i, return it
}
}

//colors G using m colors starting at vertex v
boolean color(v, m)
{
if (v exceeds n-1)
all vertices have been colored, success
else
{
for (i=1 to m)
{
assign color i to vertex v

check whether colors of v and its neighbors conflict

if (colors do not conflict)
{
color the rest of G using m colors starting at vertex v+1, done by recursive call color(v+1, m)

if (the rest of G can be colored)
all vertices have been colored, success
}
}
assign color 0 to vertex v and fail, this happens when none of the m colors can be assigned to vertex v
}
}

//in color() method chromatic numbers can be tried in ascending order
//(i=1 to n) or descending order (i=n to 1) and both orders can be
//used to find a range of possible values of the chromatic number

the input file (a .txt file) -----> output file

5 7                                 3

4 2                                 1 1

1 5                                 2 2

2 3                                 3 3

4 3                                 4 1

5 4                                 5 3

1 2

2 5