Instantly share code, notes, and snippets.
Last active
December 17, 2020 06:08
-
Star
0
(0)
You must be signed in to star a gist -
Fork
0
(0)
You must be signed in to fork a gist
-
Save msvamp/7584d93a105a807459f18f462d9b383f to your computer and use it in GitHub Desktop.
Demonstrate social media network using cliques
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* 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