C++ Program to Find Independent Sets in a Graph by Graph Coloring

This is a C++ Program to find largest independent set by graph coloring. In graph theory, an independent set or stable set is a set of vertices in a graph, no two of which are adjacent. That is, it is a set I of vertices such that for every two vertices in I, there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in I. The size of an independent set is the number of vertices it contains. Independent sets have also been called internally stable sets. A maximal independent set is either an independent set such that adding any other vertex to the set forces the set to contain an edge or the set of all vertices of the empty graph.

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

Output:

$ g++ LargestIndependentSetGraphColoring.cpp
$ a.out
 
graph.txt:
4
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0
 
set.txt:
Independent Set ( 1 ): 2
------------------
(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.