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)
Press return to continue

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

advertisement
advertisement

Here’s the list of Best Books in C++ Programming, Data Structures and Algorithms.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.