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.
261 lines
9.1 KiB
C++
261 lines
9.1 KiB
C++
/*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.*/
|
|
|
|
#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()
|
|
{
|
|
//Read Graph (note we work with the complement of the input graph)
|
|
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);
|
|
}
|
|
//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 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;
|
|
}
|
|
|
|
/*
|
|
|
|
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
|