Java library for a clique cover of a graph

Question

Does anyone know of a library or some code (preferably Java) that solves the clique cover problem?

I found an OCaml version, but I would like to use something I can more easily integrate with.

I've also found Java code and C code to find the maximum clique in a graph, but I don't know of a way to leverage this code to find a clique cover (e.g., iteratively removing maximum cliques until no nodes are left does not yield an optimum solution).

Answer 1

A Java program that determines if there is a 3-clique in a graph:

The problem defined:

https://en.wikipedia.org/wiki/Clique_problem

Input format:

The input to the method called three_clique is a String encoding representing an undirected graph that is represented like this:

(1,2,3)((1,2);(2,3);(3,1))

This encoding denotes an undirected graph with three nodes: 1,2,3. There are edges between 1 and 2, 2 and 3 and 3 and 1. It looks like a triangle. Clearly this undirected graph contains a 3 clique.

This encoding of an undirected graph does not contain a 3-clique:

(1,2,3)((1,2);(3,4))

The code:

import java.util.AbstractMap.SimpleEntry;
import java.util.Map;
import java.util.AbstractMap;
import java.util.ArrayList;

public class Main{
    public static boolean three_clique(String encoding){
        if (encoding.length() == 0){
            return false;
        }
        String[] elements = encoding.substring(1, encoding.indexOf(")")).split(",");
        encoding = encoding.substring(encoding.indexOf(")")+2); 
        encoding = encoding.substring(0, encoding.length()-1);
        ArrayList<Map.Entry<Integer, Integer>> arr = new ArrayList<Map.Entry<Integer, Integer>>();
        String[] pairs = encoding.split(";");
        if (pairs.length == 1){
            return false;
        } 
        for(int x = 0; x < pairs.length; x++){
            String str = pairs[x].substring(1, pairs[x].length()-1);
            String[] items = str.split(",");
            int left = Integer.parseInt(items[0]);
            int right = Integer.parseInt(items[1]);
            arr.add(new AbstractMap.SimpleEntry(left, right));
        }
        for(int x = 0; x < elements.length; x++){
            for(int y = 0; y < elements.length; y++){
                for(int z = 0; z < elements.length; z++){
                    if (x != y && y != z && z != x){
                        int one = Integer.parseInt(elements[x]);
                        int two = Integer.parseInt(elements[y]);
                        int three = Integer.parseInt(elements[z]);
                        if (is_connected(arr, one, two) &&
                            is_connected(arr, two, three) &&
                            is_connected(arr, three, one)){
                                return true;
                        }
                    }
                }
            }
        }
        return false;
    }
    public static boolean is_connected(ArrayList<Map.Entry<Integer, Integer>> arr, int left, int right){
        for(int x = 0; x < arr.size(); x++){
            if (left == arr.get(x).getKey() && arr.get(x).getValue() == right){
                return true;
            }
            if (right == arr.get(x).getKey() && arr.get(x).getValue() == left){
                return true;
            }
        }
        return false;
    }
    public static void main(String[] args){
        tests();
    }

    public static void tests(){
        String encoding = "";
        boolean expected;
        String msg = "";

        encoding = "";
        expected = false;
        msg = "expected '" + encoding + "' encoding to be false";
        doTest(encoding, expected, msg);

        encoding = "(1)()";
        expected = false;
        msg = "expected '" + encoding + "' encoding to be " + expected;
        doTest(encoding, expected, msg);

        encoding = "(1,2)((1,2))";
        expected = false;
        msg = "expected '" + encoding + "' encoding to be " + expected;
        doTest(encoding, expected, msg);

        encoding = "(1,2,3)((1,2);(2,3);(3,1))";
        expected = true;
        msg = "expected '" + encoding + "' encoding to be " + expected;
        doTest(encoding, expected, msg);

        encoding = "(1,2,3)((1,2);(3,4))";
        expected = false;
        msg = "expected '" + encoding + "' encoding to be " + expected;
        doTest(encoding, expected, msg);

        encoding = "(1,2,3,4)((1,2);(2,3);(3,1);(1,4))";
        expected = true;
        msg = "expected '" + encoding + "' encoding to be " + expected;
        doTest(encoding, expected, msg);

        encoding = "(1,2,3)((1,2);(2,3);(1,3))";
        expected = true;
        msg = "expected '" + encoding + "' encoding to be " + expected;
        doTest(encoding, expected, msg);
    }
    public static void doTest(String encoding, boolean expected, String msg){
        boolean result = three_clique(encoding);
        if (result == expected){
            System.out.print(".");
        }
        else{
            System.out.println("\n" + msg);
        }
    }
}

Output

The program outputs a series of seven dots on the screen which means all the unit tests pass. To prove it works, add some more unit test cases for large undirected graphs like this one: (1,2,3,4,5)((1,5);(1,4);(1,3);(1,2);(1,1);) And see if it returns false.

Runtime complexity:

Computational complexity is Polynomial, specifically O(n^3). So it's very inefficient and is certainly not the optimal algorithm for this problem. But it demonstrates the starting point how to approach and solve the clique problem in Java.