## 2 The Algorithms: MC, MCQ, MCR, MCS and BBMC
### Bbmc
#### 2.4.1 BBMC in Java  
We implement sets using Java's BitSet class (a vector of bits with associated methods) and from now on we refer to \(P\) as _the candidate BitSet_ and an ordered array of integers \(U\) as the _ordered candidate set_. In Listing 10, lines 5 to 7, we have an array of BitSet \(N\) for representing neighbourhoods, \(invN\) as the inverse neighbourhoods (the complement of \(N\)) and \(V\) an array of Vertex. \(N[i]\) is then a BitSet representing the neigbourhood of the \(i^{th}\) vertex in the array \(V\), and \(invN[i]\) as its complement. The array \(V\) is used at the top of search for renaming vertices (and we discuss this later). The \(search\) method (lines 16 to 30) creates the candidate BitSet \(P\), current clique (as a BitSet) \(C\), and Vertex array \(V\). The \(orderVertices\) method renames the vertices and will be discussed later. The method \(BBMaxClique\) corresponds to the procedure in Figure 3 of [11] and can be compared to the \(expand\) method in Listing 8. In a BitSet we use \(cardinality\) rather than \(size\) (line 35, 40 and 44). The integer array \(U\) (same name as in [11]) is essentially the colour ordered candidate set such that if \(v=U[i]\) then \(colour[i]\) corresponds to the colour given to \(v\) and \(colour[i]\leq colour[i+1]\). The method call of line 38 colours the vertices and delivers those colours in the array \(colour\) and the sorted candidate set in \(U\). The for loop, lines 39 to 47 (again, counting down from \(m-1\) to zero), first tests to see if the colour cut-off occurs (line 40) and if it does the method returns. ```
1 importjava.util. *;
2 publicclassBBMCextendsMCQ{
4
5 BitSet[]N;//neighbourhood
6 BitSet[]invN;//inverseneighbourhood
7 Vertex[]V;//mappingbitstovertices
8
9 BBMC(intn,int[][][]A,int[]degree,intstyle){
10 super(n,A,degree,style);
11N=newBitSet[n];
12 invN=newBitSet[n];
13V=newVertex[n];
14}
15
16 voidsearch(){
17 cpuTime=System.currentTimeMillis();
18 nodes=0;
19 BitSetC=newBitSet(n);
20 BitSetP=newBitSet(n);
21 for(inti=0;i<n;i++){
22N[i]=newBitSet(n);
23 invN[i]=newBitSet(n);
24V[i]=newVertex(i,degree[i]);
25}
26 orderVertices();
27C.set(0,n,false);
28P.set(0,n,true);
29 BBMaxClique(C,P);
30}
31
32 voidBBMaxClique(BitSetC,BitSetP){
33 if(timeLimit>0&&System.currentTimeMillis()-cpuTime>=timeLimit)return;
34 nodes++;
35 intm=P.cardinality();
36 int[]U=newint[m];
37 int[]colour=newint[m];
38 BBColour(P,U,colour);
39 for(inti==



\(BBMaxClique\). Regardless, \(v\) is removed from the current candidate BitSet and the current clique (line 46) and the for loop continues. Method \(BBColour\) (Listing 11) corresponds to the procedure of the same name in Figure 2 of [11] but differs in that it does not explicitly represent colour classes and therefore does not require a pigeonhole sort as in San Segundo's description. Our method takes the candidate BitSet \(P\) (see line 38), ordered candidate set \(U\) and array of \(colour\) as parameters. Due to the nature of Java's BitSet the \(and\) operation is not functional but actually modifies bits, consequently cloning is required (line 51 Listing 11) and we take a copy of \(P\). In line 52 \(colourClass\) records the current colour class, initially zero, and \(i\) is used as a counter for adding coloured vertices into the array \(U\). The while loop, lines 54 to 64, builds up colour classes whilst consuming vertices in \(copyP\). The BitSet \(Q\) (line 56) is the candidate BitSet as we are about to start a new colour class. The while loop of lines 57 to 64 builds a colour class: The first vertex in \(Q\) is selected (line 58) and is removed from the candidate BitSet \(copyP\) (line 59) and BitSet \(Q\) (line 60), \(Q\) then becomes the set of vertices that are in the current candidate BitSet (\(Q\)) and in the inverse neighborhood of \(v\) (line 61), _i.e._, \(Q\) becomes the BitSet of vertices that can join the same colour class with \(v\). We then add \(v\) to the ordered candidate set \(U\) (line 62), record its colour and increment our counter (line 63).