A C++ Program to Find the Maximum Size Clique in a Graph.
It's a C++ Program to find the cliques of size k in a graph. An un-directed graph which is formed by a finite set of vertices and a set of un-ordered pairs of vertices, which are called edges. 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 sub-graph 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 the source code for the C++ Program to Find the Maximum Size Clique in a Graph which is
successfully compiled and run on a Linux system.
#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("cliques.txt");
int main()
{
cout << "Clique 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;
if (edge == 0)
row.push_back(1);
else
row.push_back(0);
}
graph.push_back(row);
}
// To 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;
// To Read maximum size of Clique wanted
cout << "Find a Clique of size at least k = ";
cin >> K;
k = n - K;
//Find Cliques
bool found = false;
cout << "Finding Cliques..." << 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 << "Clique (" << n - s << "): ";
for (j = 0; j < cover.size(); j++)
if (cover[j] == 0)
outfile << j + 1 << " ";
outfile << endl;
cout << "Clique 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 << "Clique (" << n - s << "): ";
for (j = 0; j < cover.size(); j++)
if (cover[j] == 0)
outfile << j + 1 << " ";
outfile << endl;
cout << "Clique 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 << "Clique (" << n - s << "): ";
for (j = 0; j < cover.size(); j++)
if (cover[j] == 0)
outfile << j + 1 << " ";
outfile << endl;
cout << "Clique 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 << "Clique (" << n - s << "): ";
for (j = 0; j < cover.size(); j++)
if (cover[j] == 0)
outfile << j + 1 << " ";
outfile << endl;
cout << "Clique Size: " << n - s << endl;
if (s <= k)
{
found = true;
break;
}
}
}
if (found)
cout << "Found Clique of size at least " << K << "." << endl;
else
cout << "Could not find Clique of size at least " << K << "." << endl
<< "Maximum Clique size found is " << n - min << "." << endl;
cout << "See cliques.txt for results." << endl;
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;
}
OUTPUT
$ g++ MaxClique.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
0 comments:
Post a Comment