I am just about done with my program. I am determining the minimum number of colors needed to color a graph. I am using recursion and basically the algorithm is as such: If I can color a vertex with 1 and there are no conflicts, then colors the next vertex with 1. But there is a conflict so cheese 2. Keep doing this until you have maximized your possibilities starting with 1 color.
The recursion works well but the problem is this: If all is well, instead of making a recursive call realizing the computation need not be suspended once I maximized my color options and realize I am done and need to return back to the method caller, there are some suspended computations I need shut down but don't know how. If the recursion is left to its' own devices, it will mess up all the good it did in working the problem. I realize this seems more implementable as a simple iteration but I think recursion is just as applicable and I should be able to dump the stack on my way out to the calling program.
public class ChromaticNum
{
/**
* Colors a graph beginning with the minimum number possible (1)
*
* @param adjMatrix The undirected, unweighted graph to be colored
* @param vertex Starting vertex which is always 1
* @return chromNum The minimum number of colors used to color the graph
*/
public int colorGraph(int[][] adjMatrix, int vertex)
{
int xColors, chromNum = 1;
int[] colorsUsed = new int[adjMatrix.length]; // color used array
// If adjMatrix can be colored using i colors starting at vertex 1
for(xColors = 1; xColors < adjMatrix.length - 1; xColors++ )
{
if (colorGraph(adjMatrix, vertex, xColors, colorsUsed) == true)
{
System.out.println("Debug");
return chromNum;
}
else
{
chromNum += 1; // Ok, try plus one colors then
colorsUsed = new int[adjMatrix.length]; // reset colorsUsed
System.out.println("Debug");
}
}
return chromNum; // keep compiler happy
}
private boolean colorGraph(int[][] adjMatrix, int vertex, int xColors,
int[] colorsUsed)
{
int i = 0, j, chosenColor;
boolean colorsConflict = false;
if (vertex > adjMatrix.length - 1)
{
System.out.println("Debug");
return true; // all vertices have been colored, success
}
else
{
for (i = 0; i < xColors; i++)
{
chosenColor = i + 1;
System.out.println("Debug");
// assign color i to vertex v
colorsUsed[vertex - 1] = chosenColor;
System.out.println("Debug");
// check whether colorsUsed of vertex and its neighbors conflict
for (j = 0; j < adjMatrix.length; j++)
{
if (adjMatrix[vertex - 1][j] == 1 &
colorsUsed[j] != chosenColor)
{
// colors do not conflict
}
else if (adjMatrix[vertex - 1][j] == 1 &
colorsUsed[j] == chosenColor)
{
// colors conflict
System.out.println("Debug");
colorsConflict = true; // conflict flag set
j = adjMatrix.length - 1; // exit loop speed increase
}
}
// Test conflict flag
if (colorsConflict == true)
{
// If true, go back and try another color
colorsConflict = false; // Reset flag and try again
}
else // conflict flag not set
{
// Since colors do not conflict, color the rest of adjMatrix
//using xColors starting at vertex + 1
colorGraph(adjMatrix, vertex + 1, xColors, colorsUsed);
}
}
return false; // fail, none of the xColors can be
// assigned to the vertex
}
}
}
Any assistance or if I am just that dumb as not to see the simple solution is appreciated.