1. Home
2. Examples
3. Maximum clique problem

Example 3: The maximum clique problem

This example demonstrates the application of a greedy heuristic to search for a maximum clique in a given graph. The heuristic is created by plugging in a custom greedy neighbourhood in the random descent algorithm. A variable neighbourhood search is also applied based on the greedy heuristic where additional shaking neighbourhoods are used to escape from local optima.

Providing the data

First provide the graph data by implementing the IntegerIdentifiedData interface in CliqueData. Each vertex in the graph is represented by a unique integer ID. Edges are modeled using an adjacency map in which every vertex is mapped onto the set of adjacent vertices. The data provides some utility methods to get the neighbours or degree of a given vertex, to check whether two vertices are connected, etc. The method degree(int v, Set<Integer> subGraph) computes the degree of a given vertex in a specific subgraph, in which case edges to vertices outside this subgraph are not counted.

public class CliqueData implements IntegerIdentifiedData {

    // maps each vertex to set of adjacent vertices
    private Map<Integer, Set<Integer>> adjacencyMap;
    // number of edges
    private int numEdges;

    public CliqueData(Map<Integer, Set<Integer>> adjacencyMap) {
        this.adjacencyMap = adjacencyMap;
        // count number of edges
        numEdges = adjacencyMap.values()
                               .stream()              // stream of neighbour sets
                               .mapToInt(Set::size)   // map to number of neighbours
                               .sum()                 // sum neighbour counts of all vertices
                               /2;                    // all edges have been counted twice
    }

    public Set<Integer> getIDs() {
        return adjacencyMap.keySet();
    }

    public Set<Integer> getNeighbours(int vertex){
        return adjacencyMap.get(vertex);
    }

    public boolean connected(int v1, int v2){
        return adjacencyMap.get(v1).contains(v2);
    }

    public int degree(int v){
        return adjacencyMap.get(v).size();
    }

    // computes the degree of a vertex in a specific subgraph
    // (edges to vertices outside the subgraph are not counted)
    public int degree(int v, Set<Integer> subGraph){
        // get neighbours of v
        Set<Integer> neighbours = adjacencyMap.get(v);
        // count and return degree within subgraph
        return neighbours.stream().filter(n -> subGraph.contains(n)).count();
    }

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

    public int numEdges(){
        return numEdges;
    }

}

Defining the objective

The objective for the maximum clique problem is straightforward: maximize the size of the selected subset. The solution type of CliqueObjective is SubsetSolution. The data type is set to Object as no data is used for evaluation. In fact, this same objective could also be used for other subset problems with any data type.

public class CliqueObjective implements Objective<SubsetSolution, Object>{

    public Evaluation evaluate(SubsetSolution solution, Object data) {
        return SimpleEvaluation.WITH_VALUE(solution.getNumSelectedIDs());
    }

    public boolean isMinimizing() {
        return false;
    }

}

Implementing a custom greedy neighbourhood

Our basic search strategy is as follows: start with an empty clique and iteratively add a vertex that is connected to all vertices in the current clique. This is a greedy approach in which the size of the clique inceases with one vertex in each search step. To implement this strategy we provide a custom neighbourhood that will be used in a random descent search. The GreedyCliqueNeighbourhood implements the Neighbourhood interface with solution type SubsetSolution. It has two methods: one to get a random move and one to get the list of all considered moves for the current solution. The greedy neighbourhood generates moves that add a single new vertex with maximum degree in the subgraph induced by all vertices that are connected to the entire current clique.

To get a random move, all moves are generated and one is randomly selected. If no vertex can be added, null is returned. The list of all considered moves is created as follows:

1. Infer the set of possible adds, i.e. unselected vertices that are connected to the entire current clique.
2. Retain only those vertices from the set of possible adds with maximum degree in the subgraph induced by this set of vertices.

For every retained candidate vertex an AdditionMove is generated. If desired, a custom move type could be created as well but this is not necessary here.

public class GreedyCliqueNeighbourhood implements Neighbourhood<SubsetSolution> {

    // clique data (graph)
    private CliqueData data;

    public GreedyCliqueNeighbourhood(CliqueData data) {
        this.data = data;
    }

    public Move<SubsetSolution> getRandomMove(SubsetSolution solution, Random rnd) {
        List<Move<SubsetSolution>> allMoves = getAllMoves(solution);
        if(allMoves.isEmpty()){
            return null;
        } else {
            return allMoves.get(rnd.nextInt(allMoves.size()));
        }
    }

    public List<Move<SubsetSolution>> getAllMoves(SubsetSolution solution) {
        // get current clique
        Set<Integer> clique = solution.getSelectedIDs();
        // construct set of possible additions
        Set<Integer> possibleAdds = solution.getUnselectedIDs().stream()
                                                               .filter(v -> isPossibleAdd(v, clique))
                                                               .collect(Collectors.toSet());
        // retain only additions of candidate vertices
        // with maximum degree within induced subgraph
        List<Move<SubsetSolution>> moves = new ArrayList<>();
        long degree, maxDegree = -1;
        for(int v : possibleAdds){
            // get degree within subgraph
            degree = data.degree(v, possibleAdds);
            if(degree > maxDegree){
                // higher degree
                maxDegree = degree;
                moves.clear();
                moves.add(new AdditionMove(v));
            } else if (degree == maxDegree){
                // same degree
                moves.add(new AdditionMove(v));
            }
        }
        return moves;
    }

    // check if given vertex is connected to all vertices in the current clique
    private boolean isPossibleAdd(int vertex, Set<Integer> clique){
        return clique.stream().allMatch(vc -> data.connected(vertex, vc));
    }

}

Basic greedy search

A basic greedy search is obtained by plugging in our GreedyCliqueNeighbourhood in a random descent algorithm that starts with an empty clique. In every step a random vertex with maximum degree among all possible adds is included in the clique. When no more vertices can be added, the neighbourhood returns null and the search automatically stops.

// define adjacency map (graph)
Map<Integer, Set<Integer>> adjacencyMap = ...

// create data object
CliqueData data = new CliqueData(adjacencyMap);
// create objective
CliqueObjective obj = new CliqueObjective();
// create subset problem (all sizes allowed)
SubsetProblem<CliqueData> problem = new SubsetProblem<>(obj, data);

// create random descent search with greedy clique neighbourhood
RandomDescent<SubsetSolution> randomDescent = new RandomDescent<>(problem, new GreedyCliqueNeighbourhood(data));

// attach listener
randomDescent.addSearchListener(new ProgressSearchListener());

// IMPORTANT: start with empty clique
randomDescent.setCurrentSolution(new SubsetSolution(data.getIDs()));

// start search
randomDescent.start();
// print results
System.out.println("Clique size: " + randomDescent.getBestSolution().getNumSelectedIDs());
// dispose search
randomDescent.dispose();

Variable neighbourhood search

The basic greedy approach may easily get stuck in a local optimum, i.e. a clique which can not be further extended (maximal) but which is not the largest clique in the entire graph (not maximum). We will now create a more advanced variable neighbourhood search that is based on the greedy approach from above in combination with additional shaking neighbourhoods used to escape from local optima.

A variable neighbourhood search iteratively applies some local search algorithm where the best solution obtained in the previous iteration is somehow perturbed (shaked) and then used as initial solution of the next iteration. We will use the predefined DisjointMultiDeletionNeighbourhood for shaking. Random moves generated by such neighbourhood remove a fixed number of randomly chosen items (vertices) from the selection (clique). The number of removed items is specified as a parameter when creating the neighbourhood.

The code below demonstrates how to create a variable neighbourhood search that iteratively applies the greedy strategy from before, using a series of shaking neighbourhoods with a different number of removals to escape from local optima. When the greedy search terminates some vertices will be randomly removed from the clique through shaking and the greedy strategy is resumed. This process is repeated until some stop criterion is satisfied.

// create shaking neighbourhoods
int maxShake = ...
List<Neighbourhood<SubsetSolution>> shakingNeighs = new ArrayList<>();
for(int s=1; s <= maxShake; s++){
    shakingNeighs.add(new DisjointMultiDeletionNeighbourhood(s));
}
// create variable neighbourhood search
LocalSearch<SubsetSolution> vns = new VariableNeighbourhoodSearch<>(
                                        problem,
                                        shakingNeighs,
                                        // use random descent with greedy clique neighbourhood
                                        problem -> new RandomDescent<>(problem, new GreedyCliqueNeighbourhood(data))
                                  );
// set maximum runtime
long timeLimit = ...
vns.addStopCriterion(new MaxRuntime(timeLimit, TimeUnit.SECONDS));
// attach listener
vns.addSearchListener(new ProgressSearchListener());
// IMPORTANT: start with empty clique
vns.setCurrentSolution(new SubsetSolution(data.getIDs()));

// start search
vns.start();
// print results
System.out.println("Clique size: " + vns.getBestSolution().getNumSelectedIDs(););
// dispose search
vns.dispose();

The applied VNS strategy is a simplification of a more powerful variable neighbourhood search described in "Variable neighborhood search for the maximum clique" — Hansen et al. This full VNS strategy can easily be implemented in JAMES by plugging in some additional neighbourhoods and chaining several local searches using a piped local search.

Adapting the solution type to speed up the search

The current implementation of GreedyCliqueNeighbourhood first constructs the set of possible adds by scanning all unselected vertices and verifying whether they are connected to the entire current clique. These computations are repeated whenever a random move is generated. Here, we describe an optimization that dynamically updates the set of possible adds when a vertex is added to or removed from the clique. This reduces the overall time complexity of the optimization process so that more steps can be taken in the same time.

To keep track of the set of possible adds we extend SubsetSolution in CliqueSolution. Only a single constructor is provided to create an empty clique. When a vertex is added to the clique, all unconnected vertices are removed from the possible adds. It is also verified whether the added vertex itself is actually contained in the set of possible adds and if not, the vertex is not added. This ensures that the selected subset is always a clique. When removing a vertex from the clique, all vertices that are connected to all remaining clique nodes are again marked as possible adds. The set of possible adds can be accessed at any time using getPossibleAdds().

When implementing or extending a solution type it is important to always provide a copy() method that returns a copy of the appropriate solution type. Therefore we override this method as well: it creates a new CliqueSolution in which exactly the same clique is selected.

public class CliqueSolution extends SubsetSolution {

    // possible adds (connected to entire current clique)
    private Set<Integer> possibleAdds;
    // impossible adds (not connected to at least one vertex in current clique)
    private Set<Integer> impossibleAdds;

    // reference to clique data
    private CliqueData data;

    // single constructor (empty clique)
    public CliqueSolution(CliqueData data){
        super(data.getIDs());
        // initialize possible adds (all vertices)
        possibleAdds = new HashSet<>(data.getIDs());
        // initialize impossible adds (empty)
        impossibleAdds = new HashSet<>();
        // store data reference
        this.data = data;
    }

    @Override
    public CliqueSolution copy() {
        CliqueSolution copy = new CliqueSolution(data);
        copy.selectAll(getSelectedIDs());
        return copy;
    }

    @Override
    public boolean select(int vertex){
        if(possibleAdds.contains(vertex) && super.select(vertex)){
            // new vertex included in clique
            possibleAdds.remove(vertex);
            Set<Integer> eliminated = possibleAdds.stream()
                                                  .filter(v -> !data.connected(v, vertex))
                                                  .collect(Collectors.toSet());
            // update (im)possible adds
            possibleAdds.removeAll(eliminated);
            impossibleAdds.addAll(eliminated);
            return true;
        } else {
            return false;
        }
    }

    @Override
    public boolean deselect(int vertex){
        if(super.deselect(vertex)){
            // vertex removed from clique (goes back to possible adds)
            possibleAdds.add(vertex);
            // check for new possible adds (connected to remaining clique)
            Set<Integer> newPossibleAdds = impossibleAdds.stream()
                                                         .filter(v -> connectedToClique(v))
                                                         .collect(Collectors.toSet());
            // update (im)possible adds
            possibleAdds.addAll(newPossibleAdds);
            impossibleAdds.removeAll(newPossibleAdds);
            return true;
        } else {
            return false;
        }
    }

    // checks whether a given vertex is conected to the entire current clique
    private boolean connectedToClique(int vertex){
        return getSelectedIDs().stream().allMatch(v -> data.connected(vertex, v));
    }

    public Set<Integer> getPossibleAdds(){
        return possibleAdds;
    }

}

To actually benefit from the new solution type, we create an alternative implementation of the greedy clique neighbourhood with solution type CliqueSolution. It can simply call clique.getPossibleAdds() to get the set of possible adds. Note that we still return an AdditionMove which is defined for solution type SubsetSolution. This is allowed because the method definitions in the Neighbourhood interface allow to return a more general move type (using generics with wildcards) and CliqueSolution extends SubsetSolution. After all, a move that can be applied to any subset solution can certainly also be applied to a clique solution.

public class GreedyCliqueNeighbourhood2 implements Neighbourhood<CliqueSolution> {

    // ...

    public Move<SubsetSolution> getRandomMove(CliqueSolution clique, Random rnd) {
        // ... (same as before)
    }

    public List<Move<SubsetSolution>> getAllMoves(CliqueSolution clique) {

        // get possible adds (constant time!)
        Set<Integer> possibleAdds = clique.getPossibleAdds();

        // retain only additions of candidate vertices
        // with maximum degree within induced subgraph

        // ... (same as before)

    }

}

Now we can not use the predefined SubsetProblem as its solution type is fixed to SubsetSolution. We can not change it to our new CliqueSolution. Therefore, we use the more general GenericProblem which allows to set a custom solution type. The constructor also requests a random solution generator, but since creating a random clique is not supported, we specify a generator that throws an appropriate exception. Our search strategy starts from an empty clique, so no random solution will ever be requested anyway.

// as before
CliqueData data = ...
CliqueObjective obj = ...

// create problem
GenericProblem<CliqueSolution, CliqueData> cliqueProblem = new GenericProblem<>(data, obj, (r,d) -> {
    // random solution generator throws exception (not supported for this problem)
    throw new UnsupportedOperationException("Creating a random clique is not supported.");
});

// RANDOM DESCENT

// set solution type of search to clique solution and use optimized neighbourhood
RandomDescent<CliqueSolution> randomDescent = new RandomDescent<>(problem, new GreedyCliqueNeighbourhood2(data));
// start with empty clique
randomDescent.setCurrentSolution(new CliqueSolution(data));

// ... (same as before)

// VARIABLE NEIGHBOURHOOD SEARCH

// create shaking neighbourhoods (same as before)
List<Neighbourhood<SubsetSolution>> shakingNeighs = ...

// create variable neighbourhood search with solution type clique solution and optimized neighbourhood
VariableNeighbourhoodSearch<CliqueSolution> vns = new VariableNeighbourhoodSearch<>(
                                                        problem,
                                                        shakingNeighs,
                                                        problem -> new RandomDescent<>(problem, new GreedyCliqueNeighbourhood2(data))
                                                  );
// start with empty clique
vns.setCurrentSolution(new CliqueSolution(data));

// ... (same as before)

Full source code

The complete source code of this example is available on GitHub, including some additional code to read the input from a text file. You can also download a ZIP file that contains the Java sources of all examples, a compiled JAR (including all dependencies) as well as some input files for in case you want to run any of the examples. To run this example, execute

$ java -cp james-examples.jar org.jamesframework.examples.clique.MaximumClique <inputfile> <maxshake> <runtime>

from the command line. The input file should be a text file in which every row indicates an edge between two vertices (integer IDs) separated by one or more spaces. The <maxshake> parameter determines the number of shaking neighbourhoods that are used for VNS which each remove a fixed number of vertices in [1,<maxshake>]. The runtime is given in seconds.

• Example input file 1 (125 vertices, > 6000 edges)
• Example input file 2 (500 vertices, > 110000 edges)
• Example input file 3 (700 vertices, > 120000 edges)

The example input files correspond to instances C125.9, C500.9 and p_hat700-2, respectively, from the DIMACS benchmark set.