/* prototypes.cpp
 * Created on: May 18, 2010
 * Updated: Aug 03, 2012
 *  Author: Nam
 *  Version: Automatic ALPHA and OVERLAPPING_THRESHOLD
 *  ** STATIC version: This version deals with static networks only **
 */
#include "prototypes.h"
//============================================================================//
//               Global variables that can be accessed anywhere               //
//============================================================================//
uint N = 0; 			// N is the highest node index.
uint realN = 0;			// real number of nodes
uint M = 0; 			// M is the total number of edges.
uint numCOM = 0;		// numCOM is the number of communities.
uint realNumCOM = 0;	// realNumCOM is the actual number of communities when some communities combine together.
double tDelta = 0;		// total Delta found the system
//----------------- Static arrays ----------------//
uint interG[MAX_NODE_INTER_G];	// the global array for intersection of two NODES
uint interH[MAX_NODE_INTER_H];	// the list containing the intersection of two COMMUNITIES
uint n_interG = 0;				// the counter of interG[]
uint n_interH = 0;				// the counter of interH[]
uint n_countInt = 0;			// the counter of countInt[]
uint maxDegree = 0,				// other variables for reference purpose
	maxn_ComID = 0,
	maxnumCid = 0,
	maxIntersection = 0,
	maxEdgeIntersection = 0,
	maxOutliers = 0;
//---------------- Dynamic arrays ----------------//
uint **adjList = NULL;		// the adjacent list
uint **ComID = NULL;		// the array contains nodes in the same community ID
uint **Cid = NULL;			// the Community ID of each node
uint *degree = NULL;		// the degree list
uint *n_ComID = NULL;		// the number of Community ID(s) we can have
uint *numCid = NULL;		// the number of community ids for each node
uint *countInt = NULL;		// countInt[] array to find intersection, etc
uint *numEdgeList = NULL;	// number of edges in each community
//============================================================================//
//                         Details of global prototypes                       //
//============================================================================//
void serr(const char str[]) { // output error when unexpected cases happen
	cout<< str <<endl;
	exit(0);
}
//============================================================================//
FILE *initOpenFile(const char filename[], const char mode[]) { // open a file with different mode - C style
	FILE *f = NULL;
	if (strcmp(mode, "read")==0 || strcmp(mode, "rt")==0) { // open file to read
		fopen_s(&f, filename,"rt");
	} else if (strcmp(mode, "write")==0 || strcmp(mode, "wt")==0) {// open file to write
		fopen_s(&f, filename,"wt");
	} else if (strcmp(mode, "append")==0 || strcmp(mode, "ap")==0) {// open file to append
		fopen_s(&f, filename,"ap");
	} else {
		serr("Error: incorrect <mode> in initOpenFile()");		
	}
	if (!f) {
		serr("Error: Can not open input file in initOpenFile()");
	}
	return f;
}
//============================================================================//
void updateCounter() {
	if (n_countInt >= SAFE_ULONGMAX) { // if the counter gets too large...
		memset(countInt, 0, MULTI_N * UINT_SIZE); // clear the counter
		n_countInt = 0; // reset it
	}
	n_countInt++; // increase the counter
}
//============================================================================//
uint findTau(uint n) { // find the suffice number of edges
	if (n <= MIN_NODE) { // if we dont have enough nodes
		return 0;
	}
	if (n > N) { // if the number of nodes gets too large
		serr("Error: n > N in findTau()");
	}
	uint pn = n*(n-1)/2; // since we have a safety check above, this step should not be a problem
	return ROUND( pow(pn, 1 - (double)1/pn) );
}
//============================================================================//
// Find the intersection of adjList[nodeA] and adjList[nodeB].
// In the end, we PUT *nodeA* and *nodeB* to the end of the intersection
void findIntersectionLinearG(uint nodeA, uint nodeB) {
	n_interG = 0; // the number of elements in the intersection is 0 at beginning
	updateCounter(); // update the counter	
	if (degree[nodeA]<=0||degree[nodeB]>=N) { //--- SAFETY CHECK ---
		serr("Error: degree[nodeA]<=0||degree[nodeB]>=N in findIntersectionLinearG()");
	}
	uint i;
	for(i=0; i<degree[nodeA]; i++) {// mark nodes in adjList[nodeA]
		if (adjList[nodeA][i]<=0 || adjList[nodeA][i]>N) { //--- SAFETY CHECK ---
			serr("Error: adjList[nodeA][i]<=0 || adjList[nodeA][i]>N in findIntersectionLinearG()");
		}
		countInt[ adjList[nodeA][i] ] = n_countInt;
	}
	if (degree[nodeB]<=0||degree[nodeB]>=N) { //--- SAFETY CHECK ---
		serr("Error: degree[nodeA]<=0||degree[nodeB]>=N in findIntersectionLinearG()");
	}
	for(i=0; i<degree[nodeB]; i++) { // if we find something in common of the two sets
		if (adjList[nodeB][i]<=0 || adjList[nodeB][i]>N) { //--- SAFETY CHECK ---
			serr("Error: adjList[nodeB][i]<=0 || adjList[nodeB][i]>N in findIntersectionLinearG()");
		}
		if ( countInt[ adjList[nodeB][i] ] == n_countInt ) {
			if ( n_interG >= MAX_NODE_INTER_G - 2 ) { //--- SAFETY CHECK ---
				serr("Error: n_interG >= MAX_NODE_INTER_G - 2 in findIntersectionLinearG()");
			}
			interG[ n_interG++ ] = adjList[nodeB][i];
		}
	}
	if (n_interG > 0) { // if two sets intersect, include nodeA and nodeB in the intersection
		interG[n_interG++] = nodeA;
		interG[n_interG++] = nodeB;
	}
}
//============================================================================//
// This function finds the number of edges within the set arr[] of n_arr nodes
uint findTotalNumberOfEdges(uint arr[], uint n_arr) {
	if (n_arr <= 1) { // if there is no more than a node, return 0
		return 0;
	}
	updateCounter(); // update the counter
	uint i=0, j=0, numEdge=0;
	for(i=0; i<n_arr; i++) { // first mark all the nodes in the current list
		if (arr[i]<=0 || arr[i]>N) { //--- SAFETY CHECK ---
			serr("Error: arr[i]<=0 || arr[i]>N in findTotalNumberOfEdges()");
		}
		countInt[ arr[i] ] = n_countInt;
	}
	for(i=0; i<n_arr; i++) { // now, iterate through all elements in the list
		if (degree[arr[i]]<=0 || degree[arr[i]]>=N) { //--- SAFETY CHECK ---
			serr("Error: degree[arr[i]]<=0 || degree[arr[i]]>=N in findTotalNumberOfEdges()");
		}
		for(j=0; j<degree[arr[i]]; j++) {
			if (adjList[arr[i]][j]<=0 || adjList[arr[i]][j]>N) { //--- SAFETY CHECK ---
				serr("Error: adjList[arr[i]][j]<=0 || adjList[arr[i]][j]>N in findTotalNumberOfEdges()");
			}
			if ( countInt[ adjList[arr[i]][j] ] == n_countInt ) {
				numEdge++;
			}
		}
	}
	return numEdge/2;
}
//============================================================================//
// This function marks nodes belong to a new community with community ID = comID
// Note: Nodes here are in the intersection list interG[], so we don't need extra input
void markNodes(uint comID) {
	if (comID<=0 || comID>=MULTI_N) { //--- SAFETY CHECK ---
		serr("Error: comID<=0 || comID>=MULTI_N in markNodes()");
	}
	for(uint i=0; i<n_interG; i++) {
		if (interG[i]<=0 || interG[i] >N) { //--- SAFETY CHECK ---
			serr("Error: interG[i]<=0 || interG[i] >N in markNodes()");
		}
		if ( numCid[ interG[i] ] >= MAX_NODE_CID ) { //--- SAFETY CHECK ---
			serr("Error: numCid[interG[i]] >= MAX_NODE_CID in markNodes()");
		}
		Cid[ interG[i] ][ numCid[ interG[i] ]++ ] = comID; // mark nodes with their corresponding comID
	}
}
//============================================================================//
// Function to find the intersection of ComID[comA] and ComID[comB]
int findComIDIntersectionH(uint comA, uint comB) {
	n_interH = 0; // the default number of nodes in the intersection is set to 0
	if (comA<=0 || comA>=MULTI_N || comB<=0 || comB>=MULTI_N) { //--- SAFETY CHECK ---
		serr("Error: comA<=0 || comA>=MULTI_N || comB<=0 || comB>=MULTIN in findComIDIntersectionH()");
	}
	if (n_ComID[comA]<=0 || n_ComID[comB]<=0 || !ComID[comA] || !ComID[comB]) { //--- SAFETY CHECK ---
		serr("Error: n_ComID[comA]<=0 || n_ComID[comB]<=0 || !ComID[comA] || !ComID[comB] in findComIDIntersectionH()");		
	}
	uint j=0;
	updateCounter(); // update the counter
	for(j=0; j<n_ComID[comA]; j++) {
		if (ComID[comA][j]<=0 || ComID[comA][j]>N) { //--- SAFETY CHECK ---
			serr("Error: ComID[comA][j]<=0 || ComID[comA][j]>N in findComIDIntersectionH()");
		}
		countInt[ ComID[comA][j] ] = n_countInt; // now, mark all nodes in comA[]
	}
	for(j=0; j<n_ComID[comB]; j++) { // scan comB to get the intersection
		if (ComID[comB][j]<=0 || ComID[comB][j]>N) { //--- SAFETY CHECK ---
			serr("Error: ComID[comB][j]<=0 || ComID[comB][j]>N in findComIDIntersectionH()");
		}
		if ( countInt[ ComID[comB][j] ] == n_countInt) { // if there is a commnon node in comB[]
			if ( n_interH >= MAX_NODE_INTER_H ) { //--- SAFETY CHECK ---
				serr("Error: n_interH >= MAX_NODE_INTER_H in findComIDIntersection()");
			}
			interH[ n_interH++ ] = ComID[comB][j]; // include this node to the intersection
		}
	}
	return OK;
}
//============================================================================//
// Function to find the extra edges that comA had to comB, other than the intersected edges arr[]
uint findExtraEdges(uint comA, uint comB, uint arr[], uint n_arr) {
	updateCounter();
	uint i=0, j=0, id=0, old=0, numExtra=0;
	for(i=0; i<n_arr; i++) { // first mark nodes in the intersection
		if (arr[i]<=0 || arr[i]>N) {  //--- SAFETY CHECK ---
			serr("Error: arr[i]<=0 || arr[i]>N in findExtraEdges()");
		}
		countInt[ arr[i] ] = n_countInt;
	}
	old = n_countInt + 1;
	for(i=0; i<n_ComID[comA]; i++) {// then mark nodes in comA[] with the new counter
		if (ComID[comA][i]<=0 || ComID[comA][i]>N) { //--- SAFETY CHECK ---
			serr("Error: ComID[comA][i]<=0 || ComID[comA][i]>N in findExtraEdges()");
		}
		if ( countInt[ ComID[comA][i] ] != n_countInt ) {
			countInt[ ComID[comA][i] ] = old; // just for speed up, should be countInt[ ComID[comA][i] ] = n_countInt + 1
		}
	}
	old = n_countInt;
	updateCounter(); // now, n_countInt <-- n_countInt + 1;
	for(i=0; i<n_ComID[comB]; i++) { // next, mark nodes in comB[]
		id = ComID[comB][i];
		if (id<=0 || id>N) { //--- SAFETY CHECK ---
			serr("Error: id<=0 || id>N in findExtraEdges()");
		}
		if (countInt[id] == old) { // skip over nodes in the intersection
			continue;
		}
		for(j=0; j<degree[id]; j++) {
			if (adjList[id][j]<=0 || adjList[id][j]>N) { //--- SAFETY CHECK ---
				serr("Error: adjList[id][j]<=0 || adjList[id][j]>N in findExtraEdges()");
			}
			if (countInt[ adjList[id][j] ] == n_countInt) {// if we find an edge
				numExtra++; // count it
			}
		}
	}	
	return numExtra;
}
//============================================================================//
// Here bb > aa. This is a very important step
void unionComID(uint aa, uint bb, uint inter[], uint n_inter, uint interEdges) {
	uint a = MIN(aa, bb), b = MAX(aa, bb);
	uint *tmp=NULL, i=0, n_tmp=0, nA = n_ComID[a]-n_inter;
	tmp = new uint [ nA ]; // create tmp[], a new array for ComID[a] \ ComID[b]
	if ( !tmp ) { // Safety check
		serr("Error: !tmp[] in unionComID()");
	}
	uint moreEdges = findExtraEdges(a, b, inter, n_inter); // find extra edges going between comA and comB
	updateCounter(); // update the counter
	for(i=0; i<n_ComID[b]; i++){
		countInt[ ComID[b][i] ] = n_countInt; // mark elements in the bigger array
		if (numCid[ComID[b][i]] >= MAX_NODE_CID) { // safety check
			serr("Error: numCid[ComID[b][i]] >= MAX_NODE_CID in unionComID()");
		}
		Cid[ ComID[b][i] ][ numCid[ ComID[b][i] ]++ ] = a; // assign new community ID for ComID[b][i]
	}
	n_tmp = 0;
	for(i=0; i<n_ComID[a]; i++) { // mark elements in ComID[a] only
		if (countInt[ ComID[a][i] ] != n_countInt) { // find ComID[a] \ ComID[b]
			if (n_tmp >= nA) { // Safety check
				serr("Error: n_tmp >= n_ComID[a] - n_inter + 1 in unionComID()");
			}
			tmp[ n_tmp++ ] = ComID[a][i]; // copy to tmp			
		}
	}
	if (ComID[a]) { // delete the old ComID[a], to save some memory
		delete [] ComID[a];
	}
	n_ComID[a] += n_ComID[b] - n_inter; // update the number of vertices in ComID[a]
	ComID[a] = new uint [ n_ComID[a] ]; // restore ComID[a]
	if (!ComID[a]) {
		serr("Error: !ComID[a] in unionComID()");
	}	
	for(i=0; i<n_tmp; i++) { // copy elements in ComID[a] \ ComID[b]
		ComID[a][i] = tmp[i];
	}
	for(i=0; i<n_ComID[b]; i++) { // copy elements in ComID[b]
		ComID[a][i+n_tmp] = ComID[b][i];
	}
	n_ComID[b] = 0; // now, there should be no elements in ComID[b]
	numEdgeList[a] += numEdgeList[b] - interEdges + moreEdges; // update the numEdgeList
	/*-----------------------------------------------------------
	uint ttEdgesnew = findTotalNumberOfEdges(ComID[a], n_ComID[a]);
	if (ttEdgesnew != numEdgeList[a]) {
		serr("Error: ttEdgesnew != numEdgeList[a] in unionComID()");
	}
	-------------------------------------------------------------*/
	numEdgeList[b] = 0;
	if (ComID[b]) {// clean up the used data
		delete [] ComID[b];
		ComID[b] = NULL;
	}
	if (tmp) { // Clean up temp[] array
		delete []tmp;
	}
}
//============================================================================//
void unionComID_new(uint aa, uint bb, uint inter[], uint n_inter, uint ttEdges) {
	uint a=MIN(aa, bb), b=MAX(aa, bb);	
	if (a>numCOM || b>numCOM) { // safety check
		serr("Error: a>numCOM || b>numCOM in unionComID()");
	}
	uint *tmp=NULL, i=0, n_tmp=0, x=0, nA=n_ComID[a]+n_ComID[b]-n_inter;
	tmp = new uint [ nA ]; // make a new copy of the unionComID
	if ( !tmp ) { // safety check
		serr("Error: !tmp[] in unionComID()");
	}	
	updateCounter(); // update the counter	
	for(i=0; i<n_ComID[a]; i++) { // mark elements in ComID[a]
		x = ComID[a][i];
		if (countInt[x] != n_countInt) { // if this node is alive and has not been marked
			tmp[n_tmp++] = x; // copy to tmp
			countInt[x] = n_countInt; // and mark it
		}
	}
	for(i=0; i<n_ComID[b]; i++){ // mark elements in ComID[b]
		x = ComID[b][i];
		if (countInt[x] == n_countInt) { // skip dead nodes or those who are already in ComID[a]
			continue;
		}
		countInt[x] = n_countInt; // mark this node so that we dont include it further
		if (n_tmp >= nA) {
			serr("Error: n_tmp >= nA in unionComID()");
		}
		tmp[ n_tmp++ ] = x; // include this node in tmp[]
		if (numCid[x] >= MAX_NODE_CID) { // safety check
			serr("Error: numCid[ComID[b][i]] >= MAX_NODE_CID in unionComID()");
		}
		Cid[ x ][ numCid[x]++ ] = a; // assign new community ID for ComID[b][i]		
	}	
	if (ComID[a]) { // delete the old ComID[a]
		delete [] ComID[a];
	}
	n_ComID[a] = n_tmp; // update the number of vertices in ComID[a]
	ComID[a] = tmp; // update the pointer to comID[a]
	numEdgeList[a] = findTotalNumberOfEdges(ComID[a], n_ComID[a]); // update the numEdgeList[a]	
	n_ComID[b] = 0; // now, there should be no elements in ComID[b]	
	numEdgeList[b] = 0; // nor any edges in ComID[b]
	if (ComID[b]) { // clean up used data
		delete [] ComID[b];
		ComID[b] = NULL;
	}
}
//============================================================================//
void reassignCommunityID_old_old_old() {
	uint i=1, id=2, j=0; // *** very important initial parameters ***
	memset(numCid, 0, (N+1) * UINT_SIZE); // we also want to update the Cid of each node
	for(j=0; j<n_ComID[1]; j++) {// refine all duplicate community ID for ComID[1]
		Cid[ ComID[1][j] ][ numCid[ ComID[1][j] ]++ ] = 1;
	}
	while (i <= numCOM) { // reassign new community ID
		for(i=i+1; n_ComID[i]<=0 && i<=numCOM; i++); // skip over communities that were previously combined
		if (i > numCOM) {
			break;
		}
		if (i > id) { // if we encounter a big combined community, we need to copy it
			if (ComID[id]) { // clean up used memory
				delete [] ComID[id];
			}
			ComID[id] = new uint [n_ComID[i]]; // initialize a new memory allocation
			if ( !ComID[id] ) {
				serr("Error: !ComID[id] in reassignCommunityID()");
			}
			memcpy(ComID[id], ComID[i], n_ComID[i] * UINT_SIZE); // copy new data
			n_ComID[id] = n_ComID[i];
			n_ComID[i] = 0;
			numEdgeList[id] = numEdgeList[i]; // update numEdgeList;
			numEdgeList[i] = 0;
			if (ComID[i]) { // free up memory
				delete [] ComID[i];
				ComID[i] = NULL;
			}
		}
		for(j=0; j<n_ComID[id]; j++) { // refining duplicate community IDs
			if ( numCid[ComID[id][j]] >= MAX_NODE_CID ) {
				serr("Error : numCid[ComID[id][j]] >= MAX_NODE_CID in reassignCommunityID()");
			}
			Cid[ ComID[id][j] ][ numCid[ ComID[id][j] ]++ ] = id; // refine all duplicate community IDs
		}
		id++;
	}
	numCOM = realNumCOM; // Update the real number of community;
}
//============================================================================//
bool reassignCommunityID() { // here ncomid2[] is the array with the exact number of node in each community
	uint i=1, id=2, j=0, x=0; // **** very important initial parameters ****
	memset(numCid, 0, (N+1) * UINT_SIZE); // we also want to update the Cid of each node	
	//------------------------------------//
	updateCounter();
	for(j=0; j<n_ComID[1]; j++) { // refine all duplicate community ID for ComID[1]
		x = ComID[1][j];
		if (countInt[x] != n_countInt ) {
			Cid[x][ numCid[x]++ ] = 1; // assign community id for x
			countInt[x] = n_countInt; // mark x so that we dont have duplicates
		}
	}
	//------------------------------------//
	while (i <= numCOM) { // reassign new community ID
		for(i=i+1; n_ComID[i]<=0 && i<=numCOM; i++); // skip over communities that were combined
		if (i > numCOM) {
			break;
		}
		if (i > id) { // if we encounter a big combined community, we need to copy it
			if ( ComID[id] ) {// clean up used memory
				delete [] ComID[id];
			}
			ComID[id] = new uint [ n_ComID[i] ]; // initialize new memory allocation
			if ( !ComID[id] ) {
				serr("Error: !ComID[id] in reassignCommunityID()");
			}
			updateCounter();
			n_ComID[id] = 0;
			for(j=0; j<n_ComID[i]; j++) { // copy nodes from ComID[i] to ComID[id]
				x = ComID[i][j];
				if ( countInt[x] != n_countInt ) { // make sure that we dont have a duplicate
					countInt[x] = n_countInt;
					ComID[id][ n_ComID[id]++ ] = x; // inlude x into ComID[id]
					Cid[x][ numCid[x]++ ] = id;
				}
			}		
			numEdgeList[id] = numEdgeList[i]; // update numEdgeList[id];
			numEdgeList[i] = 0; // update numEdgeList[i]
			n_ComID[i] = 0; // clear the number of nodes in community ith
			if ( ComID[i] ) { // free up memory
				delete [] ComID[i];
				ComID[i] = NULL;
			}
		} else {
			updateCounter();			
			for(j=0; j<n_ComID[i]; j++) { // copy nodes from ComID[i] to ComID[id]
				x = ComID[i][j];
				if ( countInt[x] != n_countInt ) { // make sure that we dont have a duplicate
					countInt[x] = n_countInt;					
					Cid[x][ numCid[x]++ ] = i;
				}
			}
		}
		//------------------------------//
		id++;
		//------------------------------//
	}
	numCOM = realNumCOM; // Update the real number of community;
	return true;
}
//============================================================================//
void swapAndDeleteComID(uint i, uint j) { // swap communities i and j if they overlap too much. The community with bigger ID will be deleted
	uint bigger = MAX(i,j),smaller = MIN(i,j);
	if (n_ComID[bigger] > n_ComID[smaller]) { // if ComID[bigger] has more data than ComID[smaller], we copy ComID[smaller] <-- ComID[bigger]
		n_ComID[smaller] = n_ComID[bigger];
		numEdgeList[smaller] = numEdgeList[bigger];
		if (ComID[smaller]) { // clean up used data
			delete [] ComID[smaller];
			ComID[smaller] = NULL;
		}		
		ComID[smaller] = new uint [ n_ComID[bigger] ]; // create new memory allocation
		if (!ComID[smaller]) {
			serr("!ComID[smaller] in swapAndDeleteCom()");
		}
		memcpy(ComID[smaller], ComID[bigger], n_ComID[bigger]*UINT_SIZE); // copy the new data
	}	
	// else, what we simply do is to get rid of the bigger community ComID[bigger]
	n_ComID[bigger] = 0; // we need to free up n_ComID[bigger]
	numEdgeList[bigger] = 0; // and NumEdgeList[bigger]
	if (ComID[bigger]) { // as well as ComID[bigger]
		delete [] ComID[bigger];
		ComID[bigger] = NULL;
	}
}
//============================================================================//
double findOverlappingScore(uint comA, uint comB, uint &totalEdges) {
	totalEdges = 0;
	uint minNode = 0, minEdge = 0;
	minNode = MIN(n_ComID[comA], n_ComID[comB]); // find the smaller set cardinality
	minEdge = MIN(numEdgeList[comA], numEdgeList[comB]); // find the smaller number of edges
	if (minNode<=0 || minEdge<=0) {
		return 0; // <-- here, we dont output error since some merged communities may vanish and the system has not been updated yet
	}
	findComIDIntersectionH(comA, comB); // find the intersection of ComID[comA] and ComID[comB]
	if (n_interH <= 1) {// if the intersection has less than one element
		return NO_OVERLAP;
	}
	if (n_interH >= minNode) { // if they are fully overlapped
		return FULL_OVERLAP;
	}
	totalEdges = findTotalNumberOfEdges(interH, n_interH); // find number of edges in the intersection
	double res = (double)n_interH/minNode + (double)totalEdges/minEdge; // find the overlapping score
	if (res > FULL_OVERLAP) {
		serr("Error: overlappingScore > FULL_OVERLAP in findOverlappingScore()");
	}
	return res;
}
//============================================================================//
int findComAdjList(uint comA, uint cAdjList[], uint &n_ComAdjList) { // function to find a list of communities that comA is adjacent to
	n_ComAdjList = 0;
	if (n_ComID[comA] <= MIN_NODE) { // if community comA is just a triangle
		return 0; // return nothing
	}
	uint i=0, j=0, x=0, comid=0;
	updateCounter(); // update the counter
	for(i=0; i<n_ComID[comA]; i++) { // find the number of adjacent communities
		x = ComID[comA][i];	// x is the current element in the array
		if (x > N || x <=0) {
			serr("Error: x > N || x <=0 in findComAdjList()");
		}
		if (numCid[x] < 2) { // skip x if it is in just one community
			continue;
		}
		for(j=0; j<numCid[x]; j++) {
			comid = Cid[x][j]; // comid is the id of one adjacent community
			if (comid>numCOM || comid<=0) {
				serr("Error: comid > numCOM in findComAdjList()");
			}
			if ( n_ComID[comid]>0 && countInt[comid]<n_countInt && comid!=comA ) { // if x belongs to more than 2 communities, count it
				if (n_ComAdjList >= numCOM) { // safety check
					serr("Error: n_ComAdjList >= numCOM in findComAdjList()");
				}
				cAdjList[ n_ComAdjList++ ] = comid; // record the community ID
				countInt[comid] = n_countInt;	// mark the id of Cid[x][j]
			}
		}
	}
	return 1;
}
//============================================================================//
/*
bool isDuplicateCom() { // Here we know that n_interG > MIN_NODE (=3)	
	updateCounter();
	uint i=0, j=0;
	for(i=0; i<numCid[ interG[0] ]; i++) { // Begin marking with the n_countInt
		countInt[ Cid[interG[0]][i] ] = n_countInt;
	}
	for(i=1; i<n_interG - 1; i++) {
		for(j=0; j<numCid[ interG[i] ]; j++) {
			countInt[ Cid[interG[i]][j] ]++;
		}
	}
	n_countInt += n_interG-2; // Increase the counter <-- THIS IS VERY RISKY. CHECK IT !!!!
	for(j=0; j<numCid[interG[n_interG-1]]; j++) { // Now finding whether they are duplicate or not
		if (countInt[ Cid[interG[n_interG-1]][j] ] == n_countInt) {
			return true;
		}
	}
	return false;
}
*/
//============================================================================//
bool isInSameCS(uint a, uint b) { // check whether nodes a and b are in the same community or not
	updateCounter();
	if (numCid[a]<=0 || numCid[b]<=0) { // if one of them is fresh
		return false; // then they will not be
	}
	uint i;
	for(i=0; i<numCid[a]; i++) { // otherwise, mark all Cid(s) of node A
		if (Cid[a][i] > numCOM || Cid[a][i] <=0) { // safety check
			serr("Error: Cid[a][i] > numCOM || Cid[a][i] <=0 in isInSameCS()");
		}
		countInt[ Cid[a][i] ] = n_countInt;
	}
	for(i=0; i<numCid[b]; i++) { // and then, mark Cid(s) of node B
		if (Cid[b][i] > numCOM || Cid[b][i] <=0) {
			serr("Error: Cid[b][i] > numCOM || Cid[b][i] <=0 in isInSameCS()");
		}
		if (countInt[ Cid[b][i] ] == n_countInt) { // if we find a common community
			return true; // return true
		}
	}
	return false; // otherwise, return false
}
//============================================================================//
void initDegree() {
	degree = new uint [N+1];
	if (!degree ) {
		serr("Error: Not enough memory for degree/weight/numCid/countInt in readFromFile()");
	}
	memset(degree, 0, UINT_SIZE*(N+1)); // Set up the degree arrary
}
//============================================================================//
void initAdjList() {	
	adjList = new uint* [N+1]; // initialize the adjacent list
	if ( !adjList ) {
		serr("Error: !adjList[] in initAdjList()");
	}
	maxDegree = 0;
	for(uint a=1; a<=N; a++) {
		maxDegree = MAX(maxDegree, degree[a]); // find the maxDegree
		if (degree[a] <= 0) {
			continue;
		}
		adjList[a] = new uint [ degree[a] ]; // initialize the adjList[] of each node
		if ( !adjList[a] ) {
			serr("Error: !adjList[a] in initAdjList()");
		}
	}	
}
//============================================================================//
void initCid_numCid_countInt() {
	numCid = new uint [N+1];
	countInt = new uint [MULTI_N];
	Cid = new uint *[N+1]; // initialize the Cid array
	if ( !Cid || !numCid || !countInt ) {
		serr("Error: !Cid || !numCid || !countInt in initCid_numCid_countInt()");
	}	
	for(uint i=1; i<=N; i++) { // initially, each node has one community ID
		Cid[i] = new uint [MAX_NODE_CID];
		if ( !Cid[i] ) {
			serr("Error: Not enough memory for Cid[i] in initCid_numCid_countInt()");
		}
	}
	memset(numCid, 0, UINT_SIZE*(N+1)); // set up the numCid array
	memset(countInt, 0, UINT_SIZE*(MULTI_N)); // set up the countInt array
}
//============================================================================//
void initComID_n_ComID_numEdgeList() {
	ComID = new uint *[MULTI_N];
	if ( !ComID ) {
		serr("Error: !ComID in initComID_n_ComID_numEdgeList()");
	}
	n_ComID = new uint [MULTI_N]; // n_ComID[] array which stores the number of members in each community
	if ( !n_ComID ) {
		serr("Error: !n_ComID in initComID_n_ComID_numEdgeList()");
	}
	memset(n_ComID, 0, UINT_SIZE*MULTI_N); // memset ComID counter, make sure it contains all 0's at the beginning
	numEdgeList = new uint [MULTI_N];
	if ( !numEdgeList ) { // safety check
		serr("Error: !numEdgeList in initComID_n_ComID_numEdgeList()");
	}
	memset(numEdgeList, 0, UINT_SIZE*MULTI_N);
}
//============================================================================//
void resizeComID_n_ComID() { // resize ComID[][] and n_ComID[] arrays. This for the STATIC version only
	uint *tmp1=NULL, **tmp2=NULL, a=0;
	tmp1 = new uint [ numCOM + 1 ]; // allocate the appropriate amount of memory for n_ComID[]
	if ( !tmp1 ) {
		serr("Error : !tmp1 in resizeComID_n_ComID()");
	}
	memcpy(tmp1, n_ComID, (numCOM+1)*UINT_SIZE);
	if (n_ComID) { // free up used memory
		delete [] n_ComID;
	}
	n_ComID = tmp1; // assign the new pointer
	//-----------------------//
	tmp2 = new uint *[numCOM+1]; // allocate the appropriate amount of memory for ComID[][]
	if (!tmp2) {
		serr("Error : !tmp2 in resizeComID_n_ComID()");
	}
	for(a=1; a<=numCOM; a++) {
		tmp2[a] = new uint [n_ComID[a]]; // allocate the appropriate amount of memory for ComID[a]
		if (!tmp2[a]) {
			serr("Error : !tmp2[a] in resizeComID_n_ComID()");
		}
		memcpy(tmp2[a], ComID[a], n_ComID[a]*UINT_SIZE); // copy data
	}
	for(a=1; a<=numCOM; a++) {
		if (n_ComID[a]>0 && ComID[a]) { // free up old memory
			delete [] ComID[a];
			ComID[a] = NULL;
		}
	}
	if (ComID) {
		delete [] ComID;
	}
	ComID = tmp2;
}
//============================================================================//
double findTotalDelta() {
	double Delta = 0;
	for(uint i=1;i<numCOM;i++) {
		if (n_ComID[i] > MIN_NODE) {
			Delta += (double)(2*numEdgeList[i])/( n_ComID[i]*(n_ComID[i]-1) );
		}
	}
	return Delta;
}
//----------------------------------------------------------------------------//
//============================================================================//
//----------------------------------------------------------------------------//
// Function to read the network from file
void readFromFile(const char fileName[]) {
	uint a, b;
	FILE *f = initOpenFile(fileName, "read"); // open file to read
	N = MAX_N; // initially, we set this to be the maximum possible
	initDegree(); // initialize the degree and weight arrays
	while (!feof(f)) { // read file to find the degree and weight for each node
		fscanf_s(f,"%u %u", &a, &b);
		if (a == b || a<=0 || b<=0) { // this is important, we should get rid of the selfloop
			cout<<"a = "<<a<<"; b = "<<b<<endl;
			serr("Error: a == b || a<=0 || b<=0 in readFromFile()");
		}
		if (a > MAX_N || b > MAX_N) { // if the number of vertices is out of range
			serr("Error: a > MAX_N || b > MAX_N in readFromFile()");
		}
		M++; // count the number of edges
		degree[a]++; // record the degree for init adjList[][]
		degree[b]++; // record the degree for init adjList[][]
		if (a > realN) { // record the real number of nodes
			realN = a;
		}
		if (b > realN) {
			realN = b;
		}
	}
	N = realN; // reset the real number of nodes in the network
	initAdjList(); // Initialize the adjList[][]
	memset(degree, 0, UINT_SIZE*(N+1)); // Memset 0 for degree
	fseek(f,0,SEEK_SET); // Now, go back and read the adjacent list
	while ( !feof(f) ) { // Note that we assume the input is friendly, that is there are no duplicate edges.
		fscanf_s(f,"%u %u",&a, &b); // we dont have to check input since we already did up there
		if (a == b || a<=0 || b<=0) { // this is important, we should get rid of the selfloop			
			continue;
		}
		adjList[a][degree[a]++] = b; // record adjList[a]
		adjList[b][degree[b]++] = a; // record adjList[b]
	}
	fclose(f);
}
//============================================================================//
void tryFormingNewCommunity(uint nodeA, uint nodeB) {
	uint numEdge=0, suffice_edge=0;
	findIntersectionLinearG(nodeA, nodeB); // find adjList[nodeA] intersect adjList[nodeB], the result is in interG[] and n_interG	
	if ( n_interG > MIN_NODE ) { // if they have something in common
		numEdge = findTotalNumberOfEdges(interG, n_interG); // find number of edges in the intersection
		bool isOK = (n_interG<=MAX_DATA_LIST) ? (numEdge>=suffice_x[n_interG]) : (numEdge>=findTau(n_interG));
		if (isOK) { // if we can form a new community
			if ( numCOM >= MULTI_N ) {
				serr("Error: numCOM > MULTI_N in tryFormingNewCom()");
			}
			markNodes(++numCOM); // mark all nodes in the intersection interG[]			
			ComID[numCOM] = new uint [n_interG]; // initialize ComID[numCOM]
			if ( !ComID[numCOM] ) {
				serr("Error: !ComID[numCOM] in newNode()");
			}
			memcpy(ComID[numCOM], interG, n_interG * UINT_SIZE); // copy data from interG[]
			numEdgeList[numCOM] = numEdge; // set the number of edges in numEdgeList[numCOM]
			n_ComID[numCOM] = n_interG; // n_interG is the number of nodes inside this community
		}
	}
}
//============================================================================//
void findDenseCommunities(const char *filename) {	
	cout<<">>> FINDING DENSE COMMUNITIES"<<endl;	
	FILE *f = initOpenFile(filename, "read"); // open file to read
	initCid_numCid_countInt(); // initialize data
	initComID_n_ComID_numEdgeList(); // initialize ComID, n_ComID and numEdgeList
	uint a, b, numEdge=0;
	while ( !feof(f) ) { // reading from the begining of file
		fscanf_s(f,"%u %u", &a, &b);
		if ( ! isInSameCS(a,b) ) { // if a and b are not in the same commuity
			tryFormingNewCommunity(a, b); // try to form a dense local community from (a,b)
		}
	}
	fclose(f);
	resizeComID_n_ComID(); // resize ComID[][] and n_ComID[] arrays
	cout<<"numCOM = "<<numCOM<<endl;
	//--------- SAFETY CHECK -----------//
	/*for (uint i=1; i<=numCOM; i++) {
		if (n_ComID[i]<=0 || numEdgeList[i]<=0 || !ComID[i]) {
			cout<<"n_ComID["<<i<<"] = "<<n_ComID[i]<<"; numEdgeList["<<i<<"] = "<<numEdgeList[i]<<endl;
			serr("Error2: n_ComID[i]<=0 || numEdgeList[i]<=0 in findDenseCommunities2()");
		}
	}*/
	//----------------------------------//
}
//============================================================================//
void combineOverlappingCommunities(const double overlapThres) {
	cout<<">>> COMBINING OVERLAPPING COMMUNITIES"<<". OVERLAP_THRESHOLD = "<<overlapThres<<endl;
	bool done=false;	
	double overlappingScore;
	uint comI=0, j=0, totalEdges=0, round=1, *comAdjList=NULL, n_comAdjList=0, comA=0;
	comAdjList = new uint [MAX_N]; // initialize the comAdjList[]
	if (!comAdjList) {
		serr("Error: !comAdjList in combineOverlappingCommunities()");
	}
	while (!done) { // start checking overlapped communities
		done = true;
		realNumCOM = numCOM; // make a copy of the current number of communities
		cout<<"Round #"<<round++<<", numCOM = "<<numCOM<<endl;
		for(comI = numCOM; comI >= 1; comI--) { // we start from bottom - up
			findComAdjList(comI, comAdjList, n_comAdjList); // find the adjacent list of community comI, the result is in comAdjList[] and n_comAdjList
			if (n_comAdjList <= 0) { // if this community does not overlap with any other community
				continue;
			}
			for(j=0; j<n_comAdjList; j++) { // if this community is adjacent to at least a community
				comA = comAdjList[j];				
				overlappingScore = findOverlappingScore(comI, comA, totalEdges); // find the overlapping score of the two ComID
				if (overlappingScore >= overlapThres) { // if the overlapping score is too big										
					if (overlappingScore >= FULL_OVERLAP) {
						swapAndDeleteComID(comA, comI);
						realNumCOM--; // update the real number of communities
						done = false; // tell the program that it is not done yet
					} else {
						unionComID(comA, comI, interH, n_interH, totalEdges); // Combine the two sets & delete community i_th					
						realNumCOM--; // update the real number of communities
						done = false; // tell the program that it is not done yet
						if ( !n_ComID[comI] ) { // if ComID[i] disappears, we can skip it
							break;
						}
					}
				}
			}
		}
		if (!done) {
			reassignCommunityID(); // we reassign community ID right here
		}
	}
	if (comAdjList) { // clear used data
		delete comAdjList;
	}
	cout<<"--> Done"<<endl;
}
//============================================================================//
void findTinyCommunities(const char *filename) {
	cout<<">>> FINDING TINY COMMUNITIES"<<endl;
	FILE *f = initOpenFile(filename, "read"); // Open file to read
	uint a, b;
	realNumCOM = numCOM;
	while (!feof(f)) { // Read the adjacent list to find N and M
		fscanf_s(f,"%u %u", &a, &b);
		if ( numCid[a]>0 || numCid[b]>0 ) {
			continue;
		}
		findIntersectionLinearG(a, b); // Find the intersection of adjList[a] and adjList[b]
		if (n_interG == MIN_NODE) { // If we find a triangle
			if (numCOM >= MULTI_N) { // If numCOM exceed the upper bound, return error
				serr("Error : numCOM >= MULTI_N in findTinyCommunities()");
			}
			markNodes(++numCOM); // Mark all the node in the intersection
			ComID[numCOM] = new uint [MIN_NODE]; // Locate the memory for this tiny com
			if (!ComID[numCOM]) {
				serr("Error : ComID[numCOM] = NULL in findTinyCommunities()");
			}
			memcpy(ComID[numCOM], interG, n_interG * UINT_SIZE);
			n_ComID[numCOM] = MIN_NODE; // Update n_ComID[numCOM]
			numEdgeList[numCOM] = 3; // Update the numEdgeList
		}
	}
	fclose(f);
	cout<<"numTinyCom = "<<numCOM - realNumCOM<<endl;
	cout<<"Current numCOM = "<<numCOM<<endl;	
}
//============================================================================//
void findNumDegList(uint arr[]) {
	uint i,j;
	for(i=1; i<=numCOM; i++) { // Find the numDegList
		for(j=0; j<n_ComID[i]; j++) {
			arr[i] += degree[ ComID[i][j] ];
		}
	}
}
//============================================================================//
void finalRefinement(uint *old_n_ComID) {
	uint i, j;
	for(i=1; i<=numCOM; i++) {
		if (old_n_ComID[i] == n_ComID[i] || n_ComID[i] <=0 ) { // if nothing changes, we skip
			continue;
		}
		// else, we need to do reallocate memory
		if (ComID[i]) {// delete the old memory
			delete [] ComID[i];
			ComID[i] = NULL;
		}
		ComID[i] = new uint [ n_ComID[i] ]; // allocate new memory
		if (!ComID[i]) {
			serr("Error: ComID[i] = NULL in finalRefinement()");
		}
	}
	memset(n_ComID, 0, UINT_SIZE * (numCOM+1)); // clear the current number of communities
	for(i=1; i<=N; i++) { // refining all Cid(s) of all nodes
		for(j=0; j<numCid[i]; j++) {
			if (Cid[i][j] > numCOM) {
				serr("Error: Cid[i][j] > numCOM in finalRefinement()");
			}
			ComID[ Cid[i][j] ][ n_ComID[Cid[i][j]]++ ] = i;
		}
	}
}
//============================================================================//
// This function assign community IDs for vertices that have not been assigned ones yet
void visitUnAssignedVertices() {
	cout<<">>>>> VISIT UNASSIGNED VERTICES OF THE NETWORK"<<endl;
	uint i, j, *mark, id, x, k;
	uint **res, n_res;
	mark = new uint [numCOM+1];
	res = new uint* [2];
	res[0] = new uint [numCOM+1];
	res[1] = new uint [numCOM+1];	
	uint *numDegList, *old_n_ComID;
	numDegList = new uint [numCOM+1];
	if (! (res && res[0] && res[1] && mark && numDegList)) { // Safety check
		serr("Error: Not enough memory for map in visitUnAssignedVertices()");
	}
	maxOutliers = 0; // The number of outliers	
	memset(numDegList, 0, UINT_SIZE*(numCOM+1)); // Initialize the numDegList array
	findNumDegList(numDegList); // Find the numDegList;
	old_n_ComID = new uint [numCOM+1]; // Initialize a copy of n_ComID
	memcpy(old_n_ComID, n_ComID, (numCOM+1) * UINT_SIZE); // Copy cpy_n_ComID <-- n_ComID
	for(i=1; i<=realN; i++) { // Begin to find
		if (numCid[i] > 0) {
			continue;
		}
		memset(res[0], 0, (numCOM+1)*UINT_SIZE);
		memset(res[1], 0, (numCOM+1)*UINT_SIZE);
		memset(mark, 0, (numCOM+1)*UINT_SIZE);
		n_res = 0;
		for(j=0; j<degree[i]; j++) { // Find the Cids of communities that are adjacent to vertex i and the number of edges i connects to them
			x = adjList[i][j]; // x is the vertex number
			for(k=0; k<numCid[x]; k++) { // Iterate from all community IDs that x may have
				id = Cid[x][k];
				if ( mark[id] == 0 ) {
					mark[ id ] = ++n_res;
					res[0][ n_res ] = id;
				}
				res[1][ mark[id] ]++; ///<--- Remember to replace by weight here, if necessary -->///
			}
		}
		if (n_res <= 0) { // If this node doesn't connect to any other community
			maxOutliers++;
			continue;
		}
		double ratio = 0, newRatio = 0;		
		numCid[i] = 0;
		for(j=1; j<=n_res; j++) { // Find the maximum score from those adjacent communities
			if (res[0][j] > realNumCOM) { // Skip over tiny communities (i.e. triangles)
				continue;
			}
			ratio = (HIRE_CONST * numEdgeList[res[0][j]])/numDegList[ res[0][j] ];
			newRatio = (double)(numEdgeList[res[0][j]]+ res[1][j])/(numDegList[res[0][j]]+degree[i]);
			if (newRatio >= ratio) {
				Cid[i][numCid[i]++] = res[0][j]; // Assign node i to community res[0][j]
				n_ComID[ res[0][j] ]++; // Increase the number of nodes inside community res[0][j]
				numEdgeList[res[0][j]] += res[1][j]; // Update numEdgeList
				numDegList[res[0][j]] += degree[i]; // Update numDegList
			}
		}		
	}
	cout<<"\t*** Refining Final Community Assignment ***"<<endl;
	finalRefinement(old_n_ComID); // Final refinement
	cout<<"\t*** Finding relevant info ***"<<endl;
	for(i=1;i<=N;i++) {
		maxnumCid = MAX( maxnumCid, numCid[i] );
	}
	for(i=1;i<=numCOM;i++) {
		maxn_ComID = MAX( maxn_ComID, n_ComID[i] );
	}
	if (mark) { // Clean up
		delete [] mark;
	}
	if (res[0]) {
		delete [] res[0];
	}
	if (res[1]) {
		delete [] res[1];
	}
	if (res) {
		delete [] res;
	}
	if (numDegList) {
		delete [] numDegList;
	}
	cout<<"--> Done"<<endl;
}
//============================================================================//
void testDuplicateComID() {
	uint i=0, j=0;
	bool *mark = NULL;
	mark = new bool [N+1];
	if (!mark) {
		serr("Error: !mark in testDuplicateComID()");
	}
	for(i=1; i<=numCOM; i++) {
		memset(mark, false, sizeof(bool) * (N+1));
		if (n_ComID[i] <= 0) {
			cout<<"n_ComID["<<i<<"] = "<<n_ComID[i]<<endl;
			serr("Error: n_ComID[i] <= 0 in testDuplicateComID()");
		}
		for(j=0; j<n_ComID[i];j++) {
			uint x = ComID[i][j];
			if (x>N || x<=0) {
				serr("Error: x>N || x<=0 in testDuplicateComID()");
			}
			if (mark[x]) {
				cout<<x<<" appears >= 2 times in ComID["<<i<<"]"<<endl;
				serr("Error: mark[x] in testDuplicateComID()");
			}
			mark[x] = true;
		}
	}
	if (mark) {
		delete [] mark;
	}
	cout<<"DUPLICATE COMID test PASSED"<<endl;
}
//============================================================================//
void findOverlappingCommunityStructure(const char *filename, const double overlapThres) {
	findDenseCommunities(filename);
	combineOverlappingCommunities(overlapThres);
	findTinyCommunities(filename);
	visitUnAssignedVertices();
	//testDuplicateComID();
}
//============================================================================//
void printData(const char FILENAME[], bool pComID, bool pCid, bool pDeg, bool pAdjList, bool pToFile, const double overlapThres) {
	cout<<"N = "<<realN<<endl;
	cout<<"M = "<<M<<endl;
	cout<<"numCOM = "<<numCOM<<endl;
	cout<<"num TinyCom = "<<numCOM-realNumCOM<<endl;
	cout<<"max Degree = "<<maxDegree<<endl;
	cout<<"max n_ComID = "<<maxn_ComID<<endl;
	cout<<"max numCid = "<<maxnumCid<<endl;
	cout<<"max Outliers = "<<maxOutliers<<endl;
	cout<<"Delta = "<<findTotalDelta()<<endl;
	uint a=0, b=0;
	if (pCid) {
		for(a=1;a<=N;a++) {
			if (numCid[a] <= 0)
				continue;
			cout<<"Cid["<<a<<"] = {";
			for(b=0;b<numCid[a];b++)
				cout<<Cid[a][b]<<", ";
			cout<<"}"<<endl;			
		}
	}
	if (pComID) {
		for(a=1;a<=numCOM;a++) {
			cout<<"ComID["<<a<<"] = {";
			for(b=0;b<n_ComID[a];b++)
				cout<<ComID[a][b]<<", ";
			cout<<"}"<<endl;
		}
	}
	if (pToFile) { // Print everything to a file specified by the FILENAME
		char filename[256], tmp[5], fileinfo[256];
		strcpy_s(filename,FILENAME);
		int len = strlen(FILENAME);
		filename[len-4] = '\0';
		strcat_s(filename, "_CID_DOCA_");
		_itoa_s(int(overlapThres*100), tmp, 10);		
		strcat_s(filename,tmp);
		strcpy_s(fileinfo, filename);
		strcat_s(filename,".txt");
		cout<<"Results = "<<filename<<endl;
		// Writing ComID to file
		FILE *g = initOpenFile(filename, "write");
		for(a=1; a<=numCOM; a++) { // Print Cid[] of each node in the network
			if (n_ComID[a] <=0) {
				continue;
			}
			for(b=0; b<n_ComID[a]; b++)
				fprintf(g, "%u ", ComID[a][b]);			
			fprintf(g,"\n");
		}
		//-----------------//
		//-----------------//
		for(a=1; a <=N; a++) {
			if (numCid[a] <= 0) {
				fprintf(g, "%u\n", a);
			}
		}
		//-----------------//
		//-----------------//
		fclose(g);		
		
		// Writing relevant info to file
		/*
		strcat_s(fileinfo,"_info.txt");
		FILE *f = initOpenFile(fileinfo, "write");
		//fprintf(f,"//N = %u\n", realN);
		//fprintf(f,"//M = %u\n", M);		
		//fprintf(f,"//OVERLAP_THRESHOLD = %f\n", overlapThres);
		//fprintf(f,"//Number of communities = %u\n", numCOM);
		//fprintf(f,"//tDelta = %f\n",tDelta);
		//fprintf(f,"//Maximum degree = %u\n",maxDegree);
		//fprintf(f,"//Maximum number of members in a community = %u\n", maxn_ComID);
		//fprintf(f,"//Maximum communities a user belongs to = %u\n", maxnumCid);
		//fprintf(f,"//Maximum intersection = %u\n", maxIntersection);
		//fprintf(f,"//Maximum edge intersection = %u\n", maxEdgeIntersection);
		//fprintf(f,"//Maximum number of outliers = %u\n",maxOutliers);
		//fprintf(f,"//Number of tiny communities = %u\n",numCOM-realNumCOM);
		//fprintf(f,"//Time taken = %f\n", difftime (end_t,start_t));

		fprintf(f,"numCOM\t\t", numCOM); //1
		fprintf(f,"Delta\t\t", tDelta); //2 
		fprintf(f,"max Degree\t\t", maxDegree); //3
		fprintf(f,"max n_ComID\t\t", maxn_ComID); //4
		fprintf(f,"max numCid\t\t", maxnumCid); //5
		fprintf(f,"max outliers\t\t", maxOutliers); //6
		fprintf(f,"tiny com\t\t", numCOM-realNumCOM); //7
		fprintf(f,"time\n"); //8

		fprintf(f,"%u\t\t", numCOM); //1
		fprintf(f,"%f\t\t", tDelta); //2 
		fprintf(f,"%u\t\t", maxDegree); //3
		fprintf(f,"%u\t\t", maxn_ComID); //4
		fprintf(f,"%u\t\t", maxnumCid); //5
		fprintf(f,"%u\t\t", maxOutliers); //6
		fprintf(f,"%u\t\t", numCOM-realNumCOM); //7
		fprintf(f,"%f", difftime (end_t,start_t)); //8
		fclose(f);*/
	}
	if (pDeg)
		for(a=1;a<=N;a++)
			cout<<"degree["<<a<<"] = "<<degree[a]<<endl;
	if (pAdjList) {
		for(a=1;a<=N;a++) {
			cout<<"adjList["<<a<<"] = ";
			for(b=0;b<degree[a];b++)
				cout<<adjList[a][b]<<" ";
			cout<<endl;
		}
	}
}
//============================================================================//
void cleanUpData() {
	cout<<"+++++ CLEANING DATA ... +++++"<<endl;
	uint i;
	for(i=1; i<=N; i++) { // Delete the adjacent list and Cid[i]
		if (adjList && adjList[i] && degree[i]>0) {
			delete [] adjList[i];
		}
		if (numCid && Cid[i] && numCid[i]>0) {
			delete [] Cid[i];
		}
	}
	for(i=1; i<=numCOM; i++) {
		if (ComID[i]) {
			delete [] ComID[i];
		}
	}
	if (adjList) {
		delete [] adjList;
	}
	if (Cid) {
		delete [] Cid;
	}
	if (ComID) {
		delete [] ComID;
	}
	if (n_ComID) {
		delete [] n_ComID;
	}
	if (degree) {
		delete [] degree;
	}
	if (numCid) {
		delete [] numCid;
	}
	if (countInt) {
		delete [] countInt;
	}
	cout<<"*********** ALL DONE ***********"<<endl;
}
//============================================================================//
int findOverlappingTopRatios(const char fileName[], const double overlappThres) {
	cout<<"+++++ FINDING TOP 30 RATIOS +++++"<<endl;
	if (overlappThres != 0.67)
		return 0;
	uint i=0, n_ratio=0, count=0, j=0, x=0;
	uint *id=NULL, *ncomid=NULL;
	id = new uint [realNumCOM+10];
	ncomid = new uint [realNumCOM+10];
	if (!ncomid || !id) {
		cout<<"Error: Not enough memory for ratio[] in findOverlappingRatios()"<<endl;
		exit(0);
	}
	for (i=1; i<=realNumCOM; i++) {
		ncomid[i] = n_ComID[i];
		id[i] = i;
	}	
	for (i=1; i <realNumCOM; i++) {
		for (j=i+1; j<=realNumCOM; j++) {
			if (ncomid[i] < ncomid[j]) {
				count = ncomid[i];
				ncomid[i] = ncomid[j];
				ncomid[j] = count;
				count = id[i];
				id[i] = id[j];
				id[j] = count;
			}
		}
	}
	double *ratio=NULL, tmp=0;
	ratio = new double [realNumCOM+10];	
	for (i=1; i<=31; i++) { // Find the 
		x = id[i];
		if (ncomid[ i ] <= MIN_NODE) {
			ratio[n_ratio++] = 0;
			continue;
		}
		count = 0;
		for (j=0; j<ncomid[i]; j++)
			if (numCid[ ComID[x][j] ] >= 2)
				count++;
		ratio[ n_ratio++ ] = (double)count/ncomid[ i ];
	}	
	char fname[256];
	strcpy_s(fname, fileName);
	fname[ strlen (fname) - 4 ] = '\0';
	strcat_s(fname, "_top30.txt");
	cout<<"fname = "<<fname<<endl;
	FILE *f = initOpenFile(fname, "write");	
	for(i=1; i<=29; i++)
		fprintf(f, "%f\n", ratio[i]);
	fprintf(f, "%f", ratio[30]);
	fclose(f);
	if (ncomid)
		delete [] ncomid;
	if (id)
		delete [] id;
	if (ratio)
		delete [] ratio;
	cout<<"Done FINDING TOP 30 RATIOS"<<endl;
	return 1;
}
//============================================================================//
void DOCA(const char *filename, const double overlapThres) {
	cout<<"+++++ READING FROM FILE ... +++++"<<endl;
	readFromFile(filename);
	cout<<"\tRead from file is done"<<endl;	
	clock_t start_t = clock(); // Start the timer
	cout<<"+++++ FINDING OVERLAPPING COMMUNITY STRUCTURE ... +++++"<<endl;
	findOverlappingCommunityStructure(filename, overlapThres);
	clock_t end_t = clock(); // Stop the timer
	cout<<"\tTime taken = "<<(double)(end_t - start_t)/CLOCKS_PER_SEC<<endl;
	tDelta = findTotalDelta();
	cout<<"+++++ PRINTING RESULTS ... +++++"<<endl;	
	//--------------------------------------------------//
	bool pCID = false, pComID = false, pDeg = false, pAdjList = false, pToFile = true;
	printData(filename, pComID, pCID, pDeg, pAdjList, pToFile, overlapThres); // output community assignment to file
	cout<<"\tDone DOCA"<<endl;	
}
//============================================================================//
//------------------------------ MAIN PROCEDURE ------------------------------//
//============================================================================//
int doDOCA(const char inputFile[], const double overlapThres){
	DOCA( inputFile , overlapThres);
	cleanUpData();
	return true;
}