# 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.
*/
if (done()) {
return false;
}

// Load 'list' with the next combination:

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

/**
* Loads the current combination into the input list.
*
* @param list the list holding the combination.
*/
list.clear();

for (int i = 0; i < currentCombinationSize; ++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 connect(int node1, int node2) {
}

public Set<Integer> nodeSet() {
}

public boolean edgeExists(int node1, int node2) {
return false;
}

return false;
}

}

public int 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);

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

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

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());

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) {
}

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) {
}

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.