1
\$\begingroup\$

Introduction

A graph clique is a set of nodes \$\mathcal{C}\$ in which each node is connected to all other nodes in \$\mathcal{C}\$.

I have this small program for finding largest cliques from undirected graphs. I have two algorithms:

  • SparseGraphLargestCliqueFinder: it begins with trivial clique candidates of size 1. It moves towards clique candidates of size \$k + 1\$ after all candidates of size \$k\$ are found. If the largest clique known so far is of size \$k\$, and we get to size \$k + 2\$, we know that the best known clique is largest. If that would not be the case, we would have found a clique of size \$k + 1\$.

  • DenseGraphLargestCliqueFinder: This one moves in "opposite direction". It starts from checking the clique candidates of size \$n\$ and proceeds towards smaller clique candidates. The very first clique found is, thus, guaranteed to be the largest.

Code

AbstractIntCombinationIterator.java

package net.coderodde.graph.clique;

import java.util.List;
import java.util.Objects;

/**
 * This abstract class defines the API and common internals for integer array
 * combination iterator.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Jul 24, 2017)
 */
public abstract class AbstractIntCombinationIterator {

    /**
     * The integer array from which to build the combinations.
     */
    protected final int[] allInts;

    /**
     * The array of indices into {@code allInts}.
     */
    protected final int[] indices;

    /**
     * The current combination size.
     */
    protected int currentCombinationSize;

    /**
     * Constructs an iterator from the input integer array.
     * 
     * @param allInts the array of integers to combine.
     */
    public AbstractIntCombinationIterator(int[] allInts) {
        this.allInts = Objects.requireNonNull(
                        allInts,
                        "The input integer array is null.");
        this.indices = new int[allInts.length];
    }

    /**
     * Returns the current size of combinations.
     * 
     * @return combination size.
     */
    public int combinationSize() {
        return currentCombinationSize;
    }

    /**
     * Attempts to build and load the next combination.
     * 
     * @param list the list into which to store the integer combination.
     * 
     * @return {@code true} only if building the next combination was 
     *         successful.
     */
    public boolean loadNextCombination(List<Integer> list) {
        if (done()) {
            return false;
        }

        // Load 'list' with the next combination:
        loadCombination(list);

        // Now update the indices:
        updateIndices();
        return true;
    }

    /**
     * Loads the current combination into the input list.
     * 
     * @param list the list holding the combination.
     */
    private void loadCombination(List<Integer> list) {
        list.clear();

        for (int i = 0; i < currentCombinationSize; ++i) {
            list.add(allInts[indices[i]]);
        }
    }

    /**
     * Iterates towards the next combination.
     */
    protected abstract void updateIndices();

    /**
     * Returns {@code true} only if there is no more combinations to iterate.
     * 
     * @return {@code true} only if there is more combinations to build.
     */
    protected abstract boolean done();
}

AbstractLargestCliqueFinder.java

package net.coderodde.graph.clique;

import java.util.List;

/**
 * This abstract class defines the API and common internals of largest clique
 * finding algorithms.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Jul 24, 2017)
 */
public abstract class AbstractLargestCliqueFinder {

    /**
     * Returns the first found largest clique.
     * 
     * @param graph the graph to search.
     * @return an array of nodes belonging to a largest clique.
     */
    public abstract int[] computeLargestClique(UndirectedGraph graph);

    /**
     * Checks whether the nodes in {@code clique} form a clique.
     * 
     * @param graph  the graph.
     * @param clique the list of nods of the graph.
     * @return {@code true} only if the node list is a clique in the graph.
     */
    protected boolean isClique(UndirectedGraph graph,
                               List<Integer> clique) {
        for (int i = 0; i < clique.size(); ++i) {
            for (int j = i + 1; j < clique.size(); ++j) {
                if (!graph.edgeExists(clique.get(i), clique.get(j))) {
                    return false;
                }
            }
        }

        return true;
    }

    /**
     * Converts the entire graph to an array of nodes.
     * 
     * @param graph the graph to convert.
     * @return the node array.
     */
    protected int[] getNodeArray(UndirectedGraph graph) {
        int[] nodeArray = new int[graph.size()];
        int index = 0;

        for (int node : graph.nodeSet()) {
            nodeArray[index++] = node;
        }

        return nodeArray;
    }

    /**
     * Checks that the graph is not empty.
     * 
     * @param graph the graph to check.
     */
    protected void checkGraphNotEmpty(UndirectedGraph graph) {
        if (graph.size() == 0) {
            throw new IllegalArgumentException("The input graph is empty.");
        }
    }

    /**
     * Converts an integer list to an integer array.
     * 
     * @param list the list to convert.
     * @return the array of integers.
     */
    protected int[] intListToIntArray(List<Integer> list) {
        int[] array = new int[list.size()];
        int index = 0;

        for (int i : list) {
            array[index++] = i;
        }

        return array;
    }
}

UndirectedGraph.java

package net.coderodde.graph.clique;

import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public final class UndirectedGraph {

    private final Map<Integer, Set<Integer>> adjacencyMap = new HashMap<>();

    public void addNode(int node) {
        if (!adjacencyMap.containsKey(node)) {
            adjacencyMap.put(node, new HashSet<>());
        }
    }

    public void connect(int node1, int node2) {
        addNode(node1);
        addNode(node2);
        adjacencyMap.get(node1).add(node2);
        adjacencyMap.get(node2).add(node1);
    }

    public Set<Integer> nodeSet() {
        return Collections.<Integer>unmodifiableSet(adjacencyMap.keySet());
    }

    public boolean edgeExists(int node1, int node2) {
        if (!adjacencyMap.containsKey(node1)) {
            return false;
        }

        if (!adjacencyMap.containsKey(node2)) {
            return false;
        }

        return adjacencyMap.get(node1).contains(node2);
    }

    public int size() {
        return adjacencyMap.size();
    }
}

ForwardIntCombinationIterator.java

package net.coderodde.graph.clique.support;

import net.coderodde.graph.clique.AbstractIntCombinationIterator;

public final class ForwardIntCombinationIterator 
        extends AbstractIntCombinationIterator {

    public ForwardIntCombinationIterator(int[] allInts) {
        super(allInts);
        this.currentCombinationSize = 1;
    }

    @Override
    protected boolean done() {
        return currentCombinationSize == allInts.length + 1;
    }

    @Override
    protected void updateIndices() {
        if (indices[currentCombinationSize - 1] < indices.length - 1) {
            indices[currentCombinationSize - 1]++;
            return;
        }

        for (int i = currentCombinationSize - 2; i >= 0; --i) {
            if (indices[i] < indices[i + 1] - 1) {
                indices[i] ++;

                for (int j = i + 1; j < currentCombinationSize; ++j) {
                    indices[j] = indices[j - 1] + 1;
                }

                return;
            }
        }

        ++currentCombinationSize;

        if (currentCombinationSize <= allInts.length) {
            for (int i = 0; i < currentCombinationSize; ++i) {
                indices[i] = i;
            }
        }
    }
}

BackwardIntCombinationIterator.java

package net.coderodde.graph.clique.support;

import net.coderodde.graph.clique.AbstractIntCombinationIterator;

public final class BackwardIntCombinationIterator 
extends AbstractIntCombinationIterator {

    public BackwardIntCombinationIterator(int[] allInts) {
        super(allInts);
        super.currentCombinationSize = allInts.length;

        for (int i = 0; i < indices.length; ++i) {
            indices[i] = i;
        }
    }

    @Override
    protected void updateIndices() {
        if (indices[currentCombinationSize - 1] < indices.length - 1) {
            indices[currentCombinationSize - 1]++;
            return;
        }

        for (int i = currentCombinationSize - 2; i >= 0; --i) {
            if (indices[i] < indices[i + 1] - 1) {
                indices[i] ++;

                for (int j = i + 1; j < currentCombinationSize; ++j) {
                    indices[j] = indices[j - 1] + 1;
                }

                return;
            }
        }

        --currentCombinationSize;

        for (int i = 0; i < currentCombinationSize; ++i) {
            indices[i] = i;
        }
    }

    @Override
    protected boolean done() {
        return currentCombinationSize == 0;
    }
}

SparseGraphLargestCliqueFinder.java

package net.coderodde.graph.clique.support;

import java.util.ArrayList;
import java.util.List;
import java.util.Objects;
import net.coderodde.graph.clique.UndirectedGraph;
import net.coderodde.graph.clique.AbstractLargestCliqueFinder;

/**
 * This clique finder starts to search trivial cliques of one node. The 
 * algorithm caches the largest tentative clique of size {@code k}. If at some
 * point it cannot find a clique of size {@code k + 1}, it returns the cached
 * clique. Needless to say, this is algorithm is best applied to sparse graphs.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Jul 24, 2017)
 */
public final class SparseGraphLargestCliqueFinder
        extends AbstractLargestCliqueFinder {

    @Override
    public int[] computeLargestClique(UndirectedGraph graph) {
        Objects.requireNonNull(graph, "The input graph is null.");
        checkGraphNotEmpty(graph);

        int[] nodes = getNodeArray(graph);
        List<Integer> clique = new ArrayList<>(graph.size());
        List<Integer> bestClique = new ArrayList<>(graph.size());
        ForwardIntCombinationIterator iterator =
                new ForwardIntCombinationIterator(nodes);

        while (iterator.loadNextCombination(clique)) {
            if (iterator.combinationSize() > clique.size() + 1) {
                break;
            }

            if (isClique(graph, clique) && bestClique.size() < clique.size()) {
                bestClique.clear();
                bestClique.addAll(clique);
            }
        }

        return intListToIntArray(bestClique);
    }
}

DenseGraphLargestCliqueFinder.java

package net.coderodde.graph.clique.support;

import java.util.ArrayList;
import java.util.List;
import java.util.Objects;
import net.coderodde.graph.clique.AbstractLargestCliqueFinder;
import net.coderodde.graph.clique.UndirectedGraph;

/**
 * This class implements a clique-finding algorithm that proceeds from larger
 * cliques candidates towards smaller. By construction, the very first clique 
 * found is guaranteed to be the largest.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Jul 24, 2017)
 */
public class DenseGraphLargestCliqueFinder extends AbstractLargestCliqueFinder {

    @Override
    public int[] computeLargestClique(UndirectedGraph graph) {
        Objects.requireNonNull(graph, "The input graph is null.");
        checkGraphNotEmpty(graph);

        int[] nodes = getNodeArray(graph);
        BackwardIntCombinationIterator iterator = 
                new BackwardIntCombinationIterator(nodes);
        List<Integer> clique = new ArrayList<>(graph.size());

        while (iterator.loadNextCombination(clique)) {
            if (isClique(graph, clique)) {
                break;
            }
        }

        return intListToIntArray(clique);
    }
}

Demo.java

package net.coderodde.graph.clique;

import java.util.Arrays;
import java.util.Random;
import net.coderodde.graph.clique.support.DenseGraphLargestCliqueFinder;
import net.coderodde.graph.clique.support.SparseGraphLargestCliqueFinder;

public class Demo {

    public static void main(String[] args) {
        System.out.println("--- Dense graph ---");
        UndirectedGraph denseGraph = getDenseGraph();

        long start = System.currentTimeMillis();
        int[] clique1 = new SparseGraphLargestCliqueFinder()
                           .computeLargestClique(denseGraph);
        long end = System.currentTimeMillis();

        System.out.println("SparseGraphLargestCliqueFinder in " +
                (end - start) + " milliseconds. Clique: " + 
                Arrays.toString(clique1) + ", clique size: " + clique1.length);

        start = System.currentTimeMillis();
        int[] clique2 = new DenseGraphLargestCliqueFinder()
                           .computeLargestClique(denseGraph);
        end = System.currentTimeMillis();

        System.out.println("DenseGraphLargestCliqueFinder in " +
                (end - start) + " milliseconds. Clique: " + 
                Arrays.toString(clique2) + ", clique size: " + clique2.length);

        System.out.println("--- Sparse graph ---");
        UndirectedGraph sparseGraph = getSparseGraph();

        start = System.currentTimeMillis();
        clique1 = new SparseGraphLargestCliqueFinder()
                           .computeLargestClique(sparseGraph);
        end = System.currentTimeMillis();

        System.out.println("SparseGraphLargestCliqueFinder in " +
                (end - start) + " milliseconds. Clique: " + 
                Arrays.toString(clique1) + ", clique size: " + clique1.length);

        start = System.currentTimeMillis();
        clique2 = new DenseGraphLargestCliqueFinder()
                           .computeLargestClique(sparseGraph);
        end = System.currentTimeMillis();

        System.out.println("DenseGraphLargestCliqueFinder in " +
                (end - start) + " milliseconds. Clique: " + 
                Arrays.toString(clique2) + ", clique size: " + clique2.length);
    }

    private static UndirectedGraph getDenseGraph() {
        UndirectedGraph graph = new UndirectedGraph();
        Random random = new Random();
        int nodes = 25;
        int edges = nodes * nodes / 3;

        for (int i = 0; i < nodes; ++i) {
            graph.addNode(i);
        }

        for (int i = 0; i < edges; ++i) {
            graph.connect(random.nextInt(nodes), random.nextInt(nodes));
        }

        return graph;
    }

    private static UndirectedGraph getSparseGraph() {
        UndirectedGraph graph = new UndirectedGraph();
        Random random = new Random();
        int nodes = 25;
        int edges = 5 * nodes / 4;

        for (int i = 0; i < nodes; ++i) {
            graph.addNode(i);
        }

        for (int i = 0; i < edges; ++i) {
            graph.connect(random.nextInt(nodes), random.nextInt(nodes));
        }

        return graph;
    }
}

Critique request

Please tell me anything that comes to mind.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.