Graph coloring in Java

Question

I'm solving the m-coloring problem using java. and I have following code that uses concept of recursion and backtracking.

import java.util.Arrays;

public class GraphColoring {

    static void graphColor(int k, int m, int n, int colors[], int graph[][]) {
        for (int c = 1; c <= m; c++) {
            if (isSafe(k, c, n, colors, graph)) {
                colors[k] = c;
                if (k + 1 < n)
                    graphColor(k + 1, m, n, colors, graph);
            }
        }
    }

    static boolean isSafe(int k, int c, int n, int[] colors, int graph[][]) {
        for (int i = 0; i < n; i++) {
            if (graph[k][i] == 1 && c == colors[i]) {
                return false;
            }
        }
        return true;
    }


    public static void main(String[] args) {

        int n = 4, m = 3;
        int[] colors = new int[n];
        int graph[][] = { { 1, 1, 0, 1 }, { 1, 1, 1, 1 }, { 0, 1, 1, 1 }, { 1, 1, 1, 1 } };
        graphColor(0, m, n, colors, graph);
        System.out.println(Arrays.toString(colors));

    }
}

OUTPUT

1 2 1 3

I would like review about its performance, time complexity and improvements. Also If I'm missing any corner cases please let me know as this code is tested on very few examples as I didn't find any online problem that checks its appropriate output.

Answer 1

Also If I'm missing any corner cases please let me know as this code is tested on very few examples as I didn't find any online problem that checks its appropriate output.

[emphasis mine]

Graph colouring is a relatively nice problem in that regard: you can easily check the validity of the result. The only conditions are that every vertex must have a color, the number of colors must be less-than-or-equal-to m, and neighboring vertices don't share a color. So as a test you could generate random graphs (or for small graphs, enumerate all symmetric graphs without self-loops), color them, and theck the results. Any valid coloring is appropriate. The main problem is testing whether graphs that your algorithm decides are not m-colorable are actually not m-colorable.

I suspected there was such an issue (as this algorithm never "uncolors" a vertex, it should be possible for it to get stuck) so I enumerated some graphs to find a concrete breaking test-case:

int n = 6, m = 3;
int[][] graph = {
    {0, 1, 0, 0, 1, 1},
    {1, 0, 1, 1, 0, 1},
    {0, 1, 0, 1, 0, 0},
    {0, 1, 1, 0, 0, 1},
    {1, 0, 0, 0, 0, 0},
    {1, 1, 0, 1, 0, 0}};

This algorithm results in [1, 2, 1, 3, 3, 0], the zero indicating that no valid coloring was found, but there actually are valid colorings, for example [1, 2, 3, 1, 2, 3]. Just to confirm that it's a valid coloring, here it is as a drawing:

Keep in mind though that if there is one valid coloring, there are almost always many more. Even if there are no fundamentally different colorings, the color-names can be permuted to yield a superficially different-looking coloring. So test-cases should not compare for equality with some coloring found by a different solver, that's too strict.

To find that case I had to implement an other graph colorer that is capable of coloring the graph above, I used this small rewrite of your code:

static int[] graphColor(int m, int[][] graph) {
    int[] colors = new int[graph.length];
    // the color of the first vertex is a free pick
    colors[0] = 1;
    if (graphColorInternal(1, m, colors, graph))
        return colors;
    else
        return null;
}

static boolean graphColorInternal(int k, int m, int colors[], int graph[][]) {
    for (int c = 1; c <= m; c++) {
        if (isSafe(k, c, colors, graph)) {
            colors[k] = c;
            if (k + 1 < colors.length) {
                if (graphColorInternal(k + 1, m, colors, graph))
                    return true;
                colors[k] = 0;
            }
            else
                return true;
        }
    }
    return false;
}

static boolean isSafe(int k, int c, int[] colors, int graph[][]) {
    for (int i = 0; i < colors.length; i++) {
        if (graph[k][i] == 1 && c == colors[i])
            return false;
    }
    return true;
}

In addition to the line colors[k] = 0; which gets the solver "unstuck" after backtracking, there are some more changes that I would like to highlight:

• The function graphColor that is supposed to be called returns its result, rather than modifying a function argument. Generally you should prefer that. Output-parameters should be avoided, unless there is a good enough reason not to.
• graphColor does not take redundant parameters (n, which it knows from the graph itself).
• The search indicates explicitly whether it found something or failed, so the wrapper does not have to inspect the coloring to find that out.
• The search returns immediately after finding a valid coloring. The original algorithm does not return immediately, it tries to fill in different colors though most of it fails because isSafe returns false a lot when given a filled coloring.

I would like review about its performance, time complexity and improvements.

Not much can be done about the time complexity, not for the worst case anyway: graph coloring is NP-complete after all.

But there are things that can be done.

• Rather than coloring the vertices simple in order of their index, color them in order of Most Constrained Variable (MCV) first, that is, color the vertex with the most colored neighbors first.
• Maintain a set of "possible colors" for every vertex. This makes it easy to detect early that the current partial-coloring is no good (if any vertex has an empty set of colors left, backtrack), and easy to find the MCV (uncolored vertex with the smallest set of possible colors). It also means that rather than checking isSafe for every color, the solver already has a list of possible colors - though of course it pays for that by maintaining those sets every time the color of a vertex is changed.
• Advanced: improve those sets of possible colors with the AC-3 Algorithm or similar.