You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
259 lines
9.1 KiB
C++
259 lines
9.1 KiB
C++
/*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.*/
|
|
|
|
#include <iostream>
|
|
#include <fstream>
|
|
#include <string>
|
|
#include <vector>
|
|
using namespace std;
|
|
|
|
bool removable(vector<int> neighbor, vector<int> cover);
|
|
int max_removable(vector<vector<int> > neighbors, vector<int> cover);
|
|
vector<int> procedure_1(vector<vector<int> > neighbors, vector<int> cover);
|
|
vector<int> procedure_2(vector<vector<int> > neighbors, vector<int> cover,
|
|
int k);
|
|
int cover_size(vector<int> cover);
|
|
ifstream infile("graph.txt");
|
|
ofstream outfile("sets.txt");
|
|
|
|
int main()
|
|
{
|
|
//Read Graph
|
|
cout << "Independent Set Algorithm." << endl;
|
|
int n, i, j, k, K, p, q, r, s, min, edge, counter = 0;
|
|
infile >> n;
|
|
vector<vector<int> > graph;
|
|
for (i = 0; i < n; i++)
|
|
{
|
|
vector<int> row;
|
|
for (j = 0; j < n; j++)
|
|
{
|
|
infile >> edge;
|
|
row.push_back(edge);
|
|
}
|
|
graph.push_back(row);
|
|
}
|
|
//Find Neighbors
|
|
vector<vector<int> > neighbors;
|
|
for (i = 0; i < graph.size(); i++)
|
|
{
|
|
vector<int> neighbor;
|
|
for (j = 0; j < graph[i].size(); j++)
|
|
if (graph[i][j] == 1)
|
|
neighbor.push_back(j);
|
|
neighbors.push_back(neighbor);
|
|
}
|
|
cout << "Graph has n = " << n << " vertices." << endl;
|
|
//Read maximum size of Independent Set wanted
|
|
cout << "Find an Independent Set of size at least k = ";
|
|
cin >> K;
|
|
k = n - K;
|
|
//Find Independent Sets
|
|
bool found = false;
|
|
cout << "Finding Independent Sets..." << endl;
|
|
min = n + 1;
|
|
vector<vector<int> > covers;
|
|
vector<int> allcover;
|
|
for (i = 0; i < graph.size(); i++)
|
|
allcover.push_back(1);
|
|
for (i = 0; i < allcover.size(); i++)
|
|
{
|
|
if (found)
|
|
break;
|
|
counter++;
|
|
cout << counter << ". ";
|
|
outfile << counter << ". ";
|
|
vector<int> cover = allcover;
|
|
cover[i] = 0;
|
|
cover = procedure_1(neighbors, cover);
|
|
s = cover_size(cover);
|
|
if (s < min)
|
|
min = s;
|
|
if (s <= k)
|
|
{
|
|
outfile << "Independent Set (" << n - s << "): ";
|
|
for (j = 0; j < cover.size(); j++)
|
|
if (cover[j] == 0)
|
|
outfile << j + 1 << " ";
|
|
outfile << endl;
|
|
cout << "Independent Set Size: " << n - s << endl;
|
|
covers.push_back(cover);
|
|
found = true;
|
|
break;
|
|
}
|
|
for (j = 0; j < n - k; j++)
|
|
cover = procedure_2(neighbors, cover, j);
|
|
s = cover_size(cover);
|
|
if (s < min)
|
|
min = s;
|
|
outfile << "Independent Set (" << n - s << "): ";
|
|
for (j = 0; j < cover.size(); j++)
|
|
if (cover[j] == 0)
|
|
outfile << j + 1 << " ";
|
|
outfile << endl;
|
|
cout << "Independent Set Size: " << n - s << endl;
|
|
covers.push_back(cover);
|
|
if (s <= k)
|
|
{
|
|
found = true;
|
|
break;
|
|
}
|
|
}
|
|
//Pairwise Intersections
|
|
for (p = 0; p < covers.size(); p++)
|
|
{
|
|
if (found)
|
|
break;
|
|
for (q = p + 1; q < covers.size(); q++)
|
|
{
|
|
if (found)
|
|
break;
|
|
counter++;
|
|
cout << counter << ". ";
|
|
outfile << counter << ". ";
|
|
vector<int> cover = allcover;
|
|
for (r = 0; r < cover.size(); r++)
|
|
if (covers[p][r] == 0 && covers[q][r] == 0)
|
|
cover[r] = 0;
|
|
cover = procedure_1(neighbors, cover);
|
|
s = cover_size(cover);
|
|
if (s < min)
|
|
min = s;
|
|
if (s <= k)
|
|
{
|
|
outfile << "Independent Set (" << n - s << "): ";
|
|
for (j = 0; j < cover.size(); j++)
|
|
if (cover[j] == 0)
|
|
outfile << j + 1 << " ";
|
|
outfile << endl;
|
|
cout << "Independent Set Size: " << n - s << endl;
|
|
found = true;
|
|
break;
|
|
}
|
|
for (j = 0; j < k; j++)
|
|
cover = procedure_2(neighbors, cover, j);
|
|
s = cover_size(cover);
|
|
if (s < min)
|
|
min = s;
|
|
outfile << "Independent Set (" << n - s << "): ";
|
|
for (j = 0; j < cover.size(); j++)
|
|
if (cover[j] == 0)
|
|
outfile << j + 1 << " ";
|
|
outfile << endl;
|
|
cout << "Independent Set Size: " << n - s << endl;
|
|
if (s <= k)
|
|
{
|
|
found = true;
|
|
break;
|
|
}
|
|
}
|
|
}
|
|
if (found)
|
|
cout << "Found Independent Set of size at least " << K << "." << endl;
|
|
else
|
|
cout << "Could not find Independent Set of size at least " << K << "."
|
|
<< endl << "Maximum Independent Set size found is " << n - min
|
|
<< "." << endl;
|
|
cout << "See sets.txt for results." << endl;
|
|
system("PAUSE");
|
|
return 0;
|
|
}
|
|
|
|
bool removable(vector<int> neighbor, vector<int> cover)
|
|
{
|
|
bool check = true;
|
|
for (int i = 0; i < neighbor.size(); i++)
|
|
if (cover[neighbor[i]] == 0)
|
|
{
|
|
check = false;
|
|
break;
|
|
}
|
|
return check;
|
|
}
|
|
|
|
int max_removable(vector<vector<int> > neighbors, vector<int> cover)
|
|
{
|
|
int r = -1, max = -1;
|
|
for (int i = 0; i < cover.size(); i++)
|
|
{
|
|
if (cover[i] == 1 && removable(neighbors[i], cover) == true)
|
|
{
|
|
vector<int> temp_cover = cover;
|
|
temp_cover[i] = 0;
|
|
int sum = 0;
|
|
for (int j = 0; j < temp_cover.size(); j++)
|
|
if (temp_cover[j] == 1 && removable(neighbors[j], temp_cover)
|
|
== true)
|
|
sum++;
|
|
if (sum > max)
|
|
{
|
|
max = sum;
|
|
r = i;
|
|
}
|
|
}
|
|
}
|
|
return r;
|
|
}
|
|
|
|
vector<int> procedure_1(vector<vector<int> > neighbors, vector<int> cover)
|
|
{
|
|
vector<int> temp_cover = cover;
|
|
int r = 0;
|
|
while (r != -1)
|
|
{
|
|
r = max_removable(neighbors, temp_cover);
|
|
if (r != -1)
|
|
temp_cover[r] = 0;
|
|
}
|
|
return temp_cover;
|
|
}
|
|
|
|
vector<int> procedure_2(vector<vector<int> > neighbors, vector<int> cover,
|
|
int k)
|
|
{
|
|
int count = 0;
|
|
vector<int> temp_cover = cover;
|
|
int i = 0;
|
|
for (int i = 0; i < temp_cover.size(); i++)
|
|
{
|
|
if (temp_cover[i] == 1)
|
|
{
|
|
int sum = 0, index;
|
|
for (int j = 0; j < neighbors[i].size(); j++)
|
|
if (temp_cover[neighbors[i][j]] == 0)
|
|
{
|
|
index = j;
|
|
sum++;
|
|
}
|
|
if (sum == 1 && cover[neighbors[i][index]] == 0)
|
|
{
|
|
temp_cover[neighbors[i][index]] = 1;
|
|
temp_cover[i] = 0;
|
|
temp_cover = procedure_1(neighbors, temp_cover);
|
|
count++;
|
|
}
|
|
if (count > k)
|
|
break;
|
|
}
|
|
}
|
|
return temp_cover;
|
|
}
|
|
|
|
int cover_size(vector<int> cover)
|
|
{
|
|
int count = 0;
|
|
for (int i = 0; i < cover.size(); i++)
|
|
if (cover[i] == 1)
|
|
count++;
|
|
return count;
|
|
}
|
|
|
|
/*
|
|
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
|