Skip to content

Instantly share code, notes, and snippets.

@msvamp
Last active December 17, 2020 06:08
Show Gist options
  • Save msvamp/7584d93a105a807459f18f462d9b383f to your computer and use it in GitHub Desktop.
Save msvamp/7584d93a105a807459f18f462d9b383f to your computer and use it in GitHub Desktop.
Demonstrate social media network using cliques
/* Demonstration of connection suggestions
* in a basic social media network
* using cliques in undirected graph
*/
#include<iostream>
using std::cin;
using std::cout;
#define VMAX 100 // Max no. of vertices to allow
#define CMAX 100 // Max no. of cliques to consider at a time
// Declaring global variables
uint16_t vnum; // To store no. of input vertices
uint8_t
*vdeg, // Array to hold degree of all vertices
*vertices, // Array to hold vertices being checked for clique
clqcc=0, // To store count of cliques being checked
clqbc=0, // To store count of found max cliques
clqac=0 // To store count of found (max-1) cliques
;
bool
**graph, // 2D array to hold edges
**clqc, // 2D array to hold all cliques being checked
**clqb, // 2D array to hold all cliques of max size
**clqa // 2D array to hold all cliques of (max-1) size
;
// Checks if the given set of vertices is a clique
bool isClique(uint8_t b) {
for(uint8_t i=1; i<b; ++i) // Check for all set of edges
for(uint8_t j=i+1; j<b; ++j)
if(!graph[vertices[i]][vertices[j]]) // If any edge is missing
return false;
return true;
}
// To store cliques into 2D array 'clqc'
void clCopy(uint8_t n, uint8_t pos) {
// Allocate space for 1 clique
clqc[pos]=(bool*)calloc(vnum,sizeof(bool));
// Store clique (set present vertices to true)
for(uint8_t i=1; i<n; ++i)
clqc[pos][vertices[i]]=true;
}
// To store if we found at least 1 clique
bool foundClique;
// To find all the cliques of size 's'
void findCliques(uint8_t i, uint8_t l, uint8_t s) {
// Check if any vertices starting (i+1) can be inserted
for(uint8_t j=i+1; j<=vnum-(s-l); ++j)
if(vdeg[j]>=s-1) { // If the degree of the vertex is sufficient
vertices[l]=j; // Add the vertex
if(isClique(l+1)) // If graph is a clique after adding vertex
if(l<s) // If clique is smaller than 's'
findCliques(j,l+1,s); // Add more vertices
else { // Else, required size attained
foundClique=true; // We found at least 1 clique
clCopy(l+1,clqcc++); // Store clique and increment counter
}
else // Else, skip this vertex
continue;
}
}
// Function to merge 'l' true values from 'src' into 'dst'
inline void boolArrayMerge(bool* src, bool* dst, uint8_t l) {
while(l--) {
*dst=*dst||*src;
++src; ++dst;
}
}
// To compute list of connection suggestions
bool** suggestUsers() {
uint8_t i,j,k,l;
bool* p=NULL;
// To store generated list of suggestions for all users
bool **sgg=(bool**)calloc(vnum,sizeof(bool*));
for(i=0; i<vnum; ++i)
sgg[i]=(bool*)calloc(vnum,sizeof(bool));
// Traverse all (max-1) cliques
for(i=0; i<clqac; ++i) {
// Create empty array 'p' for common suggestions in this (max-1) clique
p=(bool*)calloc(vnum,sizeof(bool));
// Traverse each user 'j' in this (max-1) clique
for(j=0; j<vnum; ++j)
if(clqa[i][j])
// Search all max cliques in which 'j' is present
for(k=0; k<clqbc; ++k)
if(clqb[k][j])
// Mark everyone in this max clique as suggestion in 'p'
for(l=0; l<vnum; ++l)
if(clqb[k][l])
p[l]=true;
// For every user 'j' in this (max-1) clique
for(j=0; j<vnum; ++j)
if(clqa[i][j])
// Merge the suggestions in 'p' with individual suggestions
boolArrayMerge(p,sgg[j],vnum);
// Delete the common array of suggestions in this (max-1) clique
free(p);
}
return sgg;
}
int main() {
uint8_t i,j; // Looping variables
// Accept number of vertices (users)
cout<<"Enter total number of users (max "<<VMAX<<"):\t";
cin>>vnum;
if(vnum>VMAX) vnum=VMAX;
// Allocate memory for storing edges and degrees of vertices
graph=(bool**)calloc(vnum,sizeof(bool*));
for(i=0; i<vnum; ++i)
graph[i]=(bool*)calloc(vnum,sizeof(bool));
vdeg=(uint8_t*)calloc(vnum,sizeof(uint8_t));
// Accept number of edges (connections)
uint16_t size,s=(vnum*(vnum-1)/2); // because, max no. of edges = C(vnum,2)
cout<<"Enter total number of connections (max "<<s<<"):\t";
cin>>size;
if(size>s) size=s;
cout<<"\n";
// Accept vertices for each edge
uint16_t v1,v2; // To store input vertices
for(i=0; i<size; ++i) {
cout<<"Enter users for connection "<<(i+1)<<":\t";
cin>>v1>>v2;
// Validate whether input is in range
if(v1<1 || v1>vnum || v2<1 || v2>vnum) {
cout<<"\tInvalid vertices, ignored this edge.\n";
continue;
}
--v1; --v2; // Align to 0-based array indices
if(graph[v1][v2] && graph[v2][v1])
cout<<"\tThis edge already exists, ignored.\n";
else {
graph[v1][v2]=graph[v2][v1]=true; // Mark edges in undirected graph
++vdeg[v1]; // Increment degree of both vertices
++vdeg[v2];
}
}
// Allocate memory for arrays of vertices and cliques
vertices=(uint8_t*)calloc(vnum,sizeof(uint8_t));
clqc=clqb=clqa=NULL;
// Find cliques of max and (max-1) size
for(size=2; true; ++size) {
// Delete the currently stored list of (max-1) cliques
for(i=0; i<clqac; ++i)
free(clqa[i]);
free(clqa);
// Copy the current max cliques list to (max-1)
clqa=clqb;
clqac=clqbc;
// Copy the last checked list of cliques to max list
clqb=clqc;
clqbc=clqcc;
// Allocate memory for new list of cliques
clqc=(bool**)calloc(CMAX,sizeof(bool*));
// Find next set of cliques having 'size' vertices
clqcc=0;
foundClique=false;
findCliques(0,1,size);
if(!foundClique) // If no more cliques were found
break; // We found our max and (max-1) cliques
}
--size; // Because the last attempt to find vertices had failed
cout<<"\nMax size of clique (clique number) is "<<size<<"\n\n";
// Free up dynamically allocated memory heaps not needed anymore (optional)
free(vdeg);
free(vertices);
for(i=0; i<CMAX; ++i) free(clqc[i]);
free(clqc);
// We need max clique size to be at least 3
if(size<3) {
cout<<"Too few connections to generate suggestions!\n";
return 1;
}
// Prepare suggestions for users in all (max-1) cliques
bool **suggestions=suggestUsers();
// Remove already-existing connections and self from all suggestions
for(i=0; i<vnum; ++i)
for(j=0; j<vnum; ++j)
if(suggestions[i][j] && graph[i][j] || i==j)
suggestions[i][j]=false;
// Print all suggestions for all users
bool pTitle; // Whether user's identifier should be printed
for(i=0; i<vnum; ++i) {
pTitle=true; // Set to true after every user is complete
for(j=0; j<vnum; ++j)
if(suggestions[i][j]) { // Print only those users with non-empty suggestions
if(pTitle) {
cout<<"Suggestions for user "<<(i+1)<<" :\t";
pTitle=false;
}
cout<<(j+1)<<" "; // Print the suggested user's identifier
}
if(!pTitle) // Change line only if user's title was printed
cout<<"\n";
}
cout<<"\nDone printing suggestions!\n\n";
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment