## 2 The Algorithms: MC, MCQ, MCR, MCS and BBMC
### MCQ and MCR
#### 2.2.1. MCQ in Java
*;
2 publicclassMCRComparatorimplementsComparator{
4
5 publicintcompare(Object01,Object02){
6 Vertexu=(Vertex)01;
7 Vertexv=(Vertex)02;
8 if(u.degree<v.degree||
9u.degree==v.degree&&u.nebDeg<v.nebDeg||
10u.degree==v.degree&&u.nebDeg==v.nebDeg&&u.index>v.index)return1;
11 return-1;
12}
13}
```
Listing 6: MCRComparator. ```
7 voidorderVertices(ArrayList<Integer>ColOrd){
8 Vertex[]V=newVertex[n];
9 for(inti=0;i<n;i++)V[i]=newVertex(i,degree[i]);
10 for(inti=0;i<n;i++)
11 for(intj=0;j<n;j++)
12 if(At[i][j]==1)V[i].nebDeg=V[i].nebDeg+degree[j];
13 if(style==1)Array.sort(V);
14 if(style==2)minWidthOrder(V);
15 if(style==3)Array.sort(V,newMCRComparator());
16 for(Vertexv:V)ColOrd.add(v.index);
17}
18 voidminWidthOrder(Vertex[]V){
19 ArrayList<Vertex>L=newArrayList<Vertex>(n);
20 Stack<Vertex>S=newStack<Vertex>();
21 for(Vertexv:V)L.add(v);
22 while(!L.isEmpty)(){
23 Vertexv=L.get(0);
24 for(Vertexu:L)if(u.degree<v.degree)v=u;
25S.push(v);L.remove(v);
26 for(Vertexu:L)if(At[u.index][v.index]==1)u.degree==;
27}
28 intk=0;
29 while(!S.isEmpty)V[k++]=S.pop();
30}
```
Listing 7: MCRComparator. Method \(numberSort\) (Listing 4) can be compared to the method of the same name in Figure 3 of [12]. \(numberSort\) takes as arguments the current clique \(C\), an ordered \(ArrayList\) of integers \(ColOrd\) corresponding to vertices to be coloured in that order, an \(ArrayList\) of integers \(P\) that will correspond to the coloured vertices in non-decreasing colour order, and an array of integers \(colour\) such that if \(v=P.get(i)\) (\(v\) is the \(i^{th}\) vertex in \(P\)) then the colour of \(v\) is \(colour[i]\). Lines 45 to 64 (Listing 4) differs from [PERSON]'s NUMBER-SORT method because we use the additional arguments \(ColOrd\) and the growing clique \(C\) as this allows us to easily implement our next algorithm MCS (clique \(C\) is not used in \(numberSort\) until we get to MCSb, therefore we carry it for convenience only. )Rather than assigning colours to vertices explicitly, \(numberSort\) places vertices into colour classes, _i.e._, if a vertex is not adjacent to any of the vertices in \(colourClass[i]\) then that vertex can be placed into that class and given colour number \(i+1\) (\(i+1\) so that colours range from 1 upwards). The vertices can then be sorted into colour order via a pigeonhole sort, where colour classes are the pigeonholes. \(numberSort\) starts by clearing out the colour classes that might be used (line 48). In lines 49 to 55 vertices are selected from \(ColOrd\) and placed into the first colour class in which there are no conflicts, _i.e._, a class in which the vertex is not adjacent to any other vertex in that class (lines 51 to 53, and method \(conflicts\)). The variable \(colours\) records the number of colours used. Lines 56 to 63 is a pigeonhole sort, starting by clearing \(P\) and then iterating over the colour classes (loop start at line 58) and in each colour class adding those vertices into \(P\) (lines 59 to 63). The boolean method \(conflicts\), lines 66 to 72, takes a vertex \(v\) and an ArrayList of vertices \(colourClass\) where vertices in \(colourClass\) are not pair-wise adjacent and have the same colour, _i.e._, the vertices are an independent set. If vertex \(v\) is adjacent to any vertex in \(colourClass\), the method returns true (lines 67 to 70), otherwise false. Note that if vertex \(v\) needs to be added into a new colour class in \(numberSort\), the size of that \(colourClass\) will be zero, and the for loop of lines 67 to 70 will not be performed and \(conflicts\) returns true. The complexity of \(numberSort\) is quadratic in the size of \(P\). Vertices need to be sorted at the top of search, line 19. To do this we use the class Vertex in Listing 5 and the comparator MCRComparator in Listing 6. If \(i\) is a vertex in \(P\) then the corresponding Vertex \(v\) has an integer \(index\) equal to \(i\). The Vertex also has attributes \(degree\) and \(nebDeg\).