## 2 The Algorithms: MC, MCQ, MCR, MCS and BBMC
### MCQ and MCR
#### 2.2.1. MCQ in Java  
MCQ extends MC, Listing 3 line 3, and has an additional instance variable \(colourClass\) (line 5) such that \(colourClass[i]\) is an ArrayList of integers (line 15) and will contain all the vertices of colour \(i+1\) and is used when sorting vertices by their colour (lines 45 to 64, Listing 4). At the top of search (method \(search\), lines 12 to 21, Listing 3) vertices are sorted (call to \(orderVertices(P)\) at line 19) into some order, and this is described later. Method \(expand\) (line 23 to 43 Listing 3) corresponds to the method of the same name in Figure 2 of [12]. The array \(colour\) is local to the method and holds the colour of the \(i^{th}\) vertex in \(P\). The candidate set \(P\) is then sorted in non-decreasing colour order by the call to \(numberSort\) in line 28, and \(colour[i]\)  
Figure 3: Cartoon, trace and backtrack-tree for MC on graph g10–50. is then the colour of integer vertex \(P.get(i)\). The search then begins in the loop at line 29. We first test to see if the combined size of the candidate set plus the colour of vertex \(v\) is sufficient to unseat the champion (line 30). If it is insufficient, the search terminates. Note that the loop starts at \(m-1\) (line 29), the position of the last element in \(P\), and counts down to zero. The \(i^{th}\) element of \(P\) is selected and assigned to \(v\). As in MC we create a new candidate set \(newP\), the set of vertices (integers) in \(P\) that are adjacent to \(v\) (lines 33 to 37). We then test to see if \(C\) is maximal (line 38) and if it unseats the champion. If the new candidate set is not empty, we recurse (line 39). Regardless, \(v\) is removed from \(P\) and from \(C\) (lines 40 and 41). ```
1 importjava.util. *;
2 classMCQextendsMC{
3 ArrayList[]colourClass;
4
5 MQD(intn,int[][]A,int[]degree,intstyle){
6 super(n,A,degree);
7 this.style=style;
8}
9 voidsearch(){
10 cpuTime =System.currentTimeMillis();
11 nodes =0;
12 colourClass =newArrayList[n];
13 ArrayList<Integer>C =newArrayList<Integer>(n);
14 ArrayList<Integer>P =newArrayList<Integer>(n);
15 for(inti=0;i<n;i++)colourClass[i] =newArrayList<Integer>(n);
16 orderVertices(P);
17 expand(C,P);
18}
19 voidexpand(ArrayList<Integer>C,ArrayList<Integer>P){
20 if(timeLimit>0&&System.currentTimeMillis()-cpuTime>=timeLimit)return;
21 nodes++;
22 intm=P.size();
23 int[]colour=newint[m];
24 numberSort(C,P,P,colour);
25 for(inti=m-1;i>=0;i--){
26 if(C.size()+colour[i]<=maxSize)return;
27 intv=P.get(i);
28C.add(v);
29 ArrayList<Integer>newP=newArrayList<Integer>(i);
30 for(intj=0;j<=i;j++){
31 intu=P.get(j);
32 if(A[u][v]==1)newP.add(u);
33}
34 if(newP.isEmpty()&&C.size()>maxSize)saveSolution(C);
35 if(!newP.isEmpty())expand(C,newP);
36C.remove(C.size()-1);
37P.remove(i);
38}
39}
40```
**Listing 4**MCQ (part 1 continued), Tomita 2003. ``` voidnumberSort(ArrayList<Integer>C,ArrayList<Integer>ColOrd,ArrayList<Integer>P,int[]colour){ intcolours=0; intm=ColOrd.size(); for(inti=0;i<m;i++)colourClass[i].clear(); for(inti=0;i<m;i++){ intv=ColOrd.get(i); intk=0; while(conflicts(v,colourClass[k]))k++; colourClass[k].add(v); colours=Math.max(colours,k+1); } P.clear(); inti=0; for(intk=0;k<colours;k++) for(intj=0;j<colourClass[k].size();j++){ intv=(Integer)(colourClass[k].get(j)); P.add(v); colour[i++]=k+1; }
6}
7 boolemann conflicts(intv,ArrayList<Integer>colourClass){ for(inti=0;i<colourClass.size();i++){ intw=colourClass.get(i); if(A[v]|w==1)returntrue; } returfalse; } ```
Listing 5: Vertex. ```
1 imporjava.util. *;
2
3 publicclassVerteximplementsComparable<Vertex>{
4
5 intindex,degree,nebDeg;
6
7 publicVertex(intindex,intdegree){ this.index=index;
8 this.degree=degree;
9 nebDeg=0;
10}
11}
12
13 publicintcompareTo(Vertexv){ if(degree<v.degree||degree==v.degree&&index>v.index)return1; return-1;
14} } ```
Listing 6: Vertex. ```
1 importjava.util.