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.

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; } }

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; } }

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:

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

`AdditionMove`

is generated. If desired, a custom move
type could be created as well but this is not necessary here.
`getRandomMove(solution, rnd)`

takes a random generator as its second argument, which should
be used as the source of randomness. Each search has a dedicated random generator, which is passed to the neighbourhood
when requesting a random move. If desired, a search's random generator can be customized with
`search.setRandom(rnd)`

.
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)); } }

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.

`ProgressSearchListener`

keeps track of the search progress (see
example 1A: core subset selection).
// 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();

The basic greedy approach may easily get stuck in a local optimum, i.e. a clique which can not be further extended (maxim**al**) but
which is not the largest clique in the entire graph (not maxim**um**). 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.

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.

`RandomSolutionGenerator`

interface has a single method
`create(rnd, data)`

which generates a random solution using
the specified source of randomness and data. Each search has a dedicated
random generator, which is passed to the problem, and subsequently to the
applied random solution generator, when requesting a random solution.
If desired, a search's random generator can be customized with
`search.setRandom(rnd)`

.
// 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)

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.