# C++ Program to Find the Largest Clique in a Planar Graph

«
»
This is a C++ Program to find the cliques of size k in a a graph. An undirected graph is formed by a finite set of vertices and a set of unordered pairs of vertices, which are called edges. By convention, in algorithm analysis, the number of vertices in the graph is denoted by n and the number of edges is denoted by m. A clique in a graph G is a complete subgraph of G; that is, it is a subset S of the vertices such that every two vertices in S are connected by an edge in G. A maximal clique is a clique to which no more vertices can be added; a maximum clique is a clique that includes the largest possible number of vertices, and the clique number ?(G) is the number of vertices in a maximum clique of G.

Here is source code of the C++ Program to Find the Largest clique in a Planar Graph. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

1. `#include <iostream>`
2. `#include <fstream>`
3. `#include <string>`
4. `#include <vector>`
5. `using namespace std;`
6. ` `
7. `bool removable(vector<int> neighbor, vector<int> cover);`
8. `int max_removable(vector<vector<int> > neighbors, vector<int> cover);`
9. `vector<int> procedure_1(vector<vector<int> > neighbors, vector<int> cover);`
10. `vector<int> procedure_2(vector<vector<int> > neighbors, vector<int> cover,`
11. `        int k);`
12. `int cover_size(vector<int> cover);`
13. `ifstream infile("graph.txt");`
14. `ofstream outfile("cliques.txt");`
15. ` `
16. `int main()`
17. `{`
18. `    //Read Graph (note we work with the complement of the input graph)`
19. `    cout << "Clique Algorithm." << endl;`
20. `    int n, i, j, k, K, p, q, r, s, min, edge, counter = 0;`
21. `    infile >> n;`
22. `    vector<vector<int> > graph;`
23. `    for (i = 0; i < n; i++)`
24. `    {`
25. `        vector<int> row;`
26. `        for (j = 0; j < n; j++)`
27. `        {`
28. `            infile >> edge;`
29. `            if (edge == 0)`
30. `                row.push_back(1);`
31. `            else`
32. `                row.push_back(0);`
33. `        }`
34. `        graph.push_back(row);`
35. `    }`
36. `    //Find Neighbors`
37. `    vector<vector<int> > neighbors;`
38. `    for (i = 0; i < graph.size(); i++)`
39. `    {`
40. `        vector<int> neighbor;`
41. `        for (j = 0; j < graph[i].size(); j++)`
42. `            if (graph[i][j] == 1)`
43. `                neighbor.push_back(j);`
44. `        neighbors.push_back(neighbor);`
45. `    }`
46. `    cout << "Graph has n = " << n << " vertices." << endl;`
47. `    //Read maximum size of Clique wanted`
48. `    cout << "Find a Clique of size at least k = ";`
49. `    cin >> K;`
50. `    k = n - K;`
51. `    //Find Cliques`
52. `    bool found = false;`
53. `    cout << "Finding Cliques..." << endl;`
54. `    min = n + 1;`
55. `    vector<vector<int> > covers;`
56. `    vector<int> allcover;`
57. `    for (i = 0; i < graph.size(); i++)`
58. `        allcover.push_back(1);`
59. `    for (i = 0; i < allcover.size(); i++)`
60. `    {`
61. `        if (found)`
62. `            break;`
63. `        counter++;`
64. `        cout << counter << ". ";`
65. `        outfile << counter << ". ";`
66. `        vector<int> cover = allcover;`
67. `        cover[i] = 0;`
68. `        cover = procedure_1(neighbors, cover);`
69. `        s = cover_size(cover);`
70. `        if (s < min)`
71. `            min = s;`
72. `        if (s <= k)`
73. `        {`
74. `            outfile << "Clique (" << n - s << "): ";`
75. `            for (j = 0; j < cover.size(); j++)`
76. `                if (cover[j] == 0)`
77. `                    outfile << j + 1 << " ";`
78. `            outfile << endl;`
79. `            cout << "Clique Size: " << n - s << endl;`
80. `            covers.push_back(cover);`
81. `            found = true;`
82. `            break;`
83. `        }`
84. `        for (j = 0; j < n - k; j++)`
85. `            cover = procedure_2(neighbors, cover, j);`
86. `        s = cover_size(cover);`
87. `        if (s < min)`
88. `            min = s;`
89. `        outfile << "Clique (" << n - s << "): ";`
90. `        for (j = 0; j < cover.size(); j++)`
91. `            if (cover[j] == 0)`
92. `                outfile << j + 1 << " ";`
93. `        outfile << endl;`
94. `        cout << "Clique Size: " << n - s << endl;`
95. `        covers.push_back(cover);`
96. `        if (s <= k)`
97. `        {`
98. `            found = true;`
99. `            break;`
100. `        }`
101. `    }`
102. `    //Pairwise Intersections`
103. `    for (p = 0; p < covers.size(); p++)`
104. `    {`
105. `        if (found)`
106. `            break;`
107. `        for (q = p + 1; q < covers.size(); q++)`
108. `        {`
109. `            if (found)`
110. `                break;`
111. `            counter++;`
112. `            cout << counter << ". ";`
113. `            outfile << counter << ". ";`
114. `            vector<int> cover = allcover;`
115. `            for (r = 0; r < cover.size(); r++)`
116. `                if (covers[p][r] == 0 && covers[q][r] == 0)`
117. `                    cover[r] = 0;`
118. `            cover = procedure_1(neighbors, cover);`
119. `            s = cover_size(cover);`
120. `            if (s < min)`
121. `                min = s;`
122. `            if (s <= k)`
123. `            {`
124. `                outfile << "Clique (" << n - s << "): ";`
125. `                for (j = 0; j < cover.size(); j++)`
126. `                    if (cover[j] == 0)`
127. `                        outfile << j + 1 << " ";`
128. `                outfile << endl;`
129. `                cout << "Clique Size: " << n - s << endl;`
130. `                found = true;`
131. `                break;`
132. `            }`
133. `            for (j = 0; j < k; j++)`
134. `                cover = procedure_2(neighbors, cover, j);`
135. `            s = cover_size(cover);`
136. `            if (s < min)`
137. `                min = s;`
138. `            outfile << "Clique (" << n - s << "): ";`
139. `            for (j = 0; j < cover.size(); j++)`
140. `                if (cover[j] == 0)`
141. `                    outfile << j + 1 << " ";`
142. `            outfile << endl;`
143. `            cout << "Clique Size: " << n - s << endl;`
144. `            if (s <= k)`
145. `            {`
146. `                found = true;`
147. `                break;`
148. `            }`
149. `        }`
150. `    }`
151. `    if (found)`
152. `        cout << "Found Clique of size at least " << K << "." << endl;`
153. `    else`
154. `        cout << "Could not find Clique of size at least " << K << "." << endl`
155. `                << "Maximum Clique size found is " << n - min << "." << endl;`
156. `    cout << "See cliques.txt for results." << endl;`
157. `    return 0;`
158. `}`
159. ` `
160. `bool removable(vector<int> neighbor, vector<int> cover)`
161. `{`
162. `    bool check = true;`
163. `    for (int i = 0; i < neighbor.size(); i++)`
164. `        if (cover[neighbor[i]] == 0)`
165. `        {`
166. `            check = false;`
167. `            break;`
168. `        }`
169. `    return check;`
170. `}`
171. ` `
172. `int max_removable(vector<vector<int> > neighbors, vector<int> cover)`
173. `{`
174. `    int r = -1, max = -1;`
175. `    for (int i = 0; i < cover.size(); i++)`
176. `    {`
177. `        if (cover[i] == 1 && removable(neighbors[i], cover) == true)`
178. `        {`
179. `            vector<int> temp_cover = cover;`
180. `            temp_cover[i] = 0;`
181. `            int sum = 0;`
182. `            for (int j = 0; j < temp_cover.size(); j++)`
183. `                if (temp_cover[j] == 1 && removable(neighbors[j], temp_cover)`
184. `                        == true)`
185. `                    sum++;`
186. `            if (sum > max)`
187. `            {`
188. `                max = sum;`
189. `                r = i;`
190. `            }`
191. `        }`
192. `    }`
193. `    return r;`
194. `}`
195. ` `
196. `vector<int> procedure_1(vector<vector<int> > neighbors, vector<int> cover)`
197. `{`
198. `    vector<int> temp_cover = cover;`
199. `    int r = 0;`
200. `    while (r != -1)`
201. `    {`
202. `        r = max_removable(neighbors, temp_cover);`
203. `        if (r != -1)`
204. `            temp_cover[r] = 0;`
205. `    }`
206. `    return temp_cover;`
207. `}`
208. ` `
209. `vector<int> procedure_2(vector<vector<int> > neighbors, vector<int> cover,`
210. `        int k)`
211. `{`
212. `    int count = 0;`
213. `    vector<int> temp_cover = cover;`
214. `    int i = 0;`
215. `    for (int i = 0; i < temp_cover.size(); i++)`
216. `    {`
217. `        if (temp_cover[i] == 1)`
218. `        {`
219. `            int sum = 0, index;`
220. `            for (int j = 0; j < neighbors[i].size(); j++)`
221. `                if (temp_cover[neighbors[i][j]] == 0)`
222. `                {`
223. `                    index = j;`
224. `                    sum++;`
225. `                }`
226. `            if (sum == 1 && cover[neighbors[i][index]] == 0)`
227. `            {`
228. `                temp_cover[neighbors[i][index]] = 1;`
229. `                temp_cover[i] = 0;`
230. `                temp_cover = procedure_1(neighbors, temp_cover);`
231. `                count++;`
232. `            }`
233. `            if (count > k)`
234. `                break;`
235. `        }`
236. `    }`
237. `    return temp_cover;`
238. `}`
239. ` `
240. `int cover_size(vector<int> cover)`
241. `{`
242. `    int count = 0;`
243. `    for (int i = 0; i < cover.size(); i++)`
244. `        if (cover[i] == 1)`
245. `            count++;`
246. `    return count;`
247. `}`

Output:

```\$ g++ LargestClique.cpp
\$ a.out

graph.txt:
4
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0

cliques.txt:
Clique ( 4 ): 1 2 3 4
------------------
(program exited with code: 0)

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.