Demonstrate social media network using cliques

social-cliques.cpp

/*	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;
}