/* prototypes.cpp  
 *  Author: Nam
 *  Version: Automatic ALPHA and OVERLAPPING_THRESHOLD
 */
#include "prototypes.h"
#include <string>
#include <cstring>
#include <cstdio>
#include <iostream>
#include <sstream>
#include <vector>
#include <algorithm>
#include <math.h>
//============================================================================//
using namespace std;
//============================================================================//
double OVERLAP_THRESHOLD=0.75;	// The OVERLAPPING THRESHOLD
//============================================================================//
//               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_DATA_LIST];		// The global array for intersection of two NODES
uint interH[MAX_NODE_INTER];	// 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, 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[]) {
	cout << str << endl;
	exit(0);
}
//============================================================================//
uint findSuffice(uint n) { // find the suffice number of edges in a community of n nodes
	if (n > N) {
		serr("Error: n > N in findSuffice()");
	}
	uint nn = n*(n-1)/2;
	return (uint)(pow(nn, (double)(nn-1)/nn)); // based on our proposed function
}
//============================================================================//
FILE *initOpenFile(const char filename[], const char mode[]) {
	FILE *f = NULL;
	if ( strcmp(mode, "read")==0 || strcmp(mode, "rt")==0 ) {// Open the file to read
		fopen_s(&f, filename,"rt");
	} else if ( strcmp(mode, "write")==0 || strcmp(mode, "wt")==0 ) { // Open the file to write
		fopen_s(&f, filename,"wt");
	} else {
		serr("Error: <mode> is incorrect in initOpenFile()");
	}
	if ( !f ) {
		serr("Error: Can not open input file in initOpenFile()");
	}
	return f;
}
//============================================================================//
void updateCounter() { // update the counter
	if (n_countInt >= SAFE_ULONGMAX) {
		memset(countInt, 0, MULTI_N*UINT_SIZE); // clear the counter
		n_countInt = 0; // clear the counting variable
	}
	n_countInt++; // increase the counter
}
//============================================================================//
// Find the intersection of adjList[nodeA] and adjList[nodeB].
// In the end, we DO PUT *nodeA* and *nodeB* to the end of the intersection set
bool findIntersectionLinearG(uint nodeA, uint nodeB) {
	n_interG = 0; // the number of elements in the intersection is 0 at beginning
	if (nodeA > N || nodeB > N) {
		serr("Error: nodeA>N || nodeB>N in findIntersectionLinearG()");
	}
	updateCounter(); // update the counter	
	uint i=0, x=0;
	for(i=0; i<degree[nodeA]; i++) {
		x = adjList[nodeA][i];
		countInt[x] = n_countInt; // mark nodes in adjList[nodeA]
	}
	for(i=0; i<degree[nodeB]; i++) {
		x = adjList[nodeB][i];
		if (countInt[x] == n_countInt) { // if we find something in common of the two sets
			if ( n_interG >= MAX_DATA_LIST-2 ) { // safety check
				serr("Error: n_interG >= MAX_DATA_LIST-2 in findIntersectionLinearG()");
			}
			interG[ n_interG++ ] = x; // mark nodes in the intersection
		}
	}
	if ( n_interG > 0 ) { // if two sets intersect, include nodeA and nodeB in the intersection
		interG[n_interG++] = nodeA;
		interG[n_interG++] = nodeB;
	}
	return true;
}
//============================================================================//
// This function finds the number of edges within a set of node arr[] with 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, x=0, v=0;
	for(i=0; i<n_arr; i++) { // first mark all the nodes in the current list
		x = arr[i];
		countInt[x] = n_countInt;
	}	
	for(i=0; i<n_arr; i++) { // now, iterate through all elements in the list
		x = arr[i];		
		for(j=0; j<degree[x]; j++) {
			v = adjList[x][j];
			if (countInt[v] == n_countInt) { // if we found an edge
				numEdge++; // count it
			}
		}
	}
	return numEdge/2;
}
//============================================================================//
uint testDuplicateInCom(uint comid) {
	updateCounter();
	uint i=0, x=0;
	for(i=0; i<n_ComID[comid]; i++) {
		x = ComID[comid][i];
		if (countInt[x] == n_countInt) {
			return x;
		}
		countInt[x] = n_countInt;
	}
	return 0;
}
//============================================================================//
// This function marks nodes belong to a new community whose ID equals comID
// Note: Nodes are stored in the intersection list interG[] with n_interG nodes, so we don't need extra input
void markNodes(uint comID) {
	if (comID >= MULTI_N) { // safety check
		serr("Error: comID >= MULTI_N in markNodes()");
	}
	for(uint i=0; i<n_interG; i++) {
		uint x = interG[i];
		if ( numCid[x] >= MAX_NODE_CID ) { // safety check
			serr("Error: numCid[interG[i]] >= MAX_NODE_CID in markNodes()");
		}		
		Cid[ x ][ numCid[x]++ ] = comID; // mark this node
	}
}
//============================================================================//
// Function to find the intersection of ComID[comA] and ComID[comB]. The result is stored in interH[]
bool findComIDIntersectionH(uint comA, uint comB) {
	n_interH = 0; // The default number of nodes in the intersection is set to 0
	if (comA >= MULTI_N || comB >= MULTI_N) { // safety check
		serr("Error: comA>=MULTI_N || comB >=MULTI_N in findComIDIntersectionH()");
	}
	if (n_ComID[comA] <= 0 || n_ComID[comB] <= 0) { // if one of them contains nothing
		return false;
	}
	updateCounter(); // update the counter
	uint j=0, x=0;
	for(j=0; j<n_ComID[comA]; j++) { // Now, assign every elements of ComID[comA] the value of n_countInt
		x = ComID[comA][j];
		countInt[x] = n_countInt; // then count it
	}
	for(j=0; j<n_ComID[comB]; j++) { // Scan the last list to get the intersection
		x = ComID[comB][j];
		if ( countInt[x] == n_countInt ) {
			if (n_interH >= MAX_NODE_INTER) { // Safety check
				serr("Error: n_interH >= MAX_NODE_INTER in findComIDIntersection()");
			}
			interH[ n_interH++ ] = x;
		}
	}
	return true;
}
//============================================================================//
// 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, old=0, numExtra=0, x=0, v=0;
	for(i=0; i<n_arr; i++) { // first mark nodes in the intersection
		x = arr[i];
		countInt[x] = n_countInt; // mark this node in the intersection
	}
	old = n_countInt + 1;
	for(i=0; i<n_ComID[comA]; i++) { // then mark nodes in comA
		x = ComID[comA][i];
		if (countInt[x] != n_countInt ) { // if we found an edge
			countInt[x] = old; // Just for speed up. Should be countInt[ ComID[comA][i] ] = n_countInt + 1
		}
	}
	old = n_countInt;
	updateCounter();
	for(i=0; i<n_ComID[comB]; i++) { // now, we mark nodes in comB
		x = ComID[comB][i];
		if (countInt[x] == old) { // skip over nodes in the intersection
			continue;
		}
		for(j=0; j<degree[x]; j++) {
			v = adjList[x][j];			
			if (countInt[v] == n_countInt) { // if we find an edge, count it
				numExtra++;
			}
		}
	}	
	return numExtra;
}
//============================================================================//
// This function finds the number of edges a node nodeA has to a community comI
uint numEdge2Com(uint nodeA, uint comI) {
	uint numEdge = 0;
	for(uint i=0; i<degree[nodeA]; i++) { // scan through all adjacent nodes of nodeA
		uint x = adjList[nodeA][i];
		for(uint j=0; j<numCid[x]; j++) {
			if (Cid[x][j]==comI && n_ComID[comI]>0) { // if there is an edge to the community comI
				numEdge++; // count it
			}
		}
	}
	return numEdge;
}
//============================================================================//
void unionComID(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;
	}
}
//============================================================================//
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, bool mode) {
	uint bigger = MAX(i,j), smaller = MIN(i,j);
	if (bigger>numCOM || smaller>numCOM) { // safety check
		serr("Error: bigger>numCOM || smaller>numCOM in swapAndDeleteComID()");
	}
	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 the used data
			delete [] ComID[smaller];
			ComID[smaller] = NULL;
		}
		ComID[smaller] = new uint [ n_ComID[bigger] ];
		if (!ComID[smaller]) {
			serr("Error: !ComID[smaller] in swapAndDeleteCom()");
		}
		memcpy(ComID[smaller], ComID[bigger], n_ComID[bigger]*UINT_SIZE); // copy the new data		
	}	
	n_ComID[bigger] = 0; // we need to clean 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) {
	if (comA>numCOM || comB>numCOM) { // safety check
		serr("Error: comA>numCOM || comB>numCOM in findOverlappingScore()");
	}
	totalEdges = 0;
	uint minNode = MIN(n_ComID[comA], n_ComID[comB]); // find the smaller set cardinality
	uint minEdge = MIN(numEdgeList[comA], numEdgeList[comB]); // find the smaller number of edges
	if (minNode<=0 || minEdge<=0) { // if any of them is destroyed
		return INVALID; // return invalid
	}
	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 INVALID; // return invalid
	}
	if (n_interH >= minNode) { // if they are fully overlapped
		return FULL_OVSCORE; // return the full score
	}
	totalEdges = findTotalNumberOfEdges(interH, n_interH); // find number of edges in the intersection
	return (double)n_interH/minNode + (double)totalEdges/minEdge; // find the overlapping score
}
//============================================================================//
// Function to find a list of communities that comA is adjacent to
int findComAdjList(uint comA, uint cAdjList[], uint &n_ComAdjList) {
	n_ComAdjList = 0;
	if (comA > numCOM) { // safety check
		serr("Error: comA>numCOM in findOverlappingScore()");
	}	
	if (n_ComID[comA] <= MIN_NODE) { // if this community is trivial (is a triangle)
		return 0;
	}	
	uint i=0, j=0, comid=0, x=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 (numCid[x] < 2) { // skip x if it is in just one community
			continue;
		}
		for(j=0; j<numCid[x]; j++) {
			comid = Cid[x][j];
			if (comid > numCOM) { // safety check
				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
				cAdjList[ n_ComAdjList++ ] = comid; // record the community ID
				countInt[comid] = n_countInt; // mark the id of Cid[x][j]
			}
		}
	}
	return 1;
}
//============================================================================//
bool isDuplicateCom(uint iG[], uint n_iG) {// UNUSED FUNCTION // Here we know that n_interG > MIN_NODE (=3)	
	updateCounter();
	uint i=0, j=0, comid=0, last=0;
	//-------------------------------//
	for(i=0; i<numCid[ iG[0] ]; i++) { // Begin marking with the n_countInt
		comid = Cid[iG[0]][i];
		if (comid > numCOM) { // safety check
			serr("Error: comid>numCOM ||comid<=0 in isDuplicateCom1()");
		}
		if (n_ComID[comid] > 0) {
			countInt[ comid ] = n_countInt;
		}
	}
	//-------------------------------//
	for(i=1; i<n_iG-1; i++) {
		for(j=0; j<numCid[ iG[i] ]; j++) {
			comid = Cid[ iG[i] ][j];
			if (comid > numCOM) { // safety check
				serr("Error: comid>numCOM || comid<=0 in isDuplicateCom2()");
			}
			if (n_ComID[comid] > 0) {
				countInt[ comid ]++; // <-- this is very RISKY
			}
		}
	}
	//-------------------------------//
	n_countInt += n_iG - 2; // Increase the counter <-- this is very RISKY
	last = iG[n_iG-1];
	//-------------------------------//
	for(j=0; j<numCid[last]; j++) { // Now finding whether they are duplicate or not
		comid = Cid[last][j];
		if (comid > numCOM ) { // safety check
			serr("Error: comid > numCOM in isDuplicateCom3()");
		}
		if (countInt[comid]==n_countInt && n_ComID[comid]>0) {
			return true;
		}
	}
	return false;
}
//============================================================================//
bool isInSameCS(uint a, uint b, uint boundID) {
	if (a>N || b>N) {
		serr("Error: a>N || a<=0 || b>N || b<=0 in isInSameCS()");
	}
	updateCounter();
	if (numCid[a]<=0 || numCid[b]<=0) { // If one of them is fresh
		return false;
	}
	uint i=0, comid=0;
	for(i=0; i<numCid[a]; i++) { // Otherwise, mark all Cid(s) of node A
		comid = Cid[a][i];
		if (comid > numCOM) { // safety check
			serr("Error: comid>numCOM || comid<=0 in isInSameCS1()");
		}
		if (n_ComID[comid] <= 0) {
			continue;
		}		
		countInt[ comid ] = n_countInt;
	}
	for(i=0; i<numCid[b]; i++) { // and then, check for node B
		comid = Cid[b][i];
		if (comid > numCOM) { // safety check
			serr("Error: x>numCOM ||x<=0 in isInSameCS2()");
		}
		if (countInt[comid]==n_countInt && comid>boundID) {
			return true;
		}
	}
	return false;
}
//============================================================================//
void initDegree() {
	degree = new uint [N+1];
	if (!degree ) {
		serr("Error: Not enough memory for degree[] in initDegree()");
	}
	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: Not enough memory for adjList[] in readFromFile()");
	}
	maxDegree = 0;
	for(uint a=1; a<=N; a++) {// Find the maxDegree		
		if (degree[a] <= 0) {
			continue;
		} else if (degree[a] > DEFAULT_DEG) {
			serr("Error: degree[a] > DEFAULT_DEG in initAdjList()");
		}
		maxDegree = MAX(maxDegree, degree[a]);
		adjList[a] = new uint [ DEFAULT_DEG ];
		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: !Cid[i] in findDenseCommunities()");
		}
	}
	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: Not enough memory for 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: Not enough memory for numEdgeList[] in initComID_n_ComID_numEdgeList()");
	}
	memset(numEdgeList, 0, UINT_SIZE*MULTI_N);
}
//============================================================================//
void resizeComID_n_ComID() {
	uint *tmp1=NULL, **tmp2=NULL, a=0;
	tmp1 = new uint [ numCOM + 1 ];
	if ( !tmp1 ) {
		serr("Error : !tmp1 in resizeComID_n_ComID()");
	}
	memcpy(tmp1, n_ComID, (numCOM+1)*UINT_SIZE);
	if (n_ComID){
		delete [] n_ComID;
	}
	n_ComID = tmp1;
	//-----------------------//
	tmp2 = new uint *[numCOM+1];
	if (!tmp2) {
		serr("Error : !tmp2 in resizeComID_n_ComID()");
	}
	for(a=1; a<=numCOM; a++) {
		tmp2[a] = new uint [n_ComID[a]];
		if (!tmp2[a]) {
			serr("Error : !tmp2[a] in resizeComID_n_ComID()");
		}
		memcpy(tmp2[a], ComID[a], n_ComID[a]*UINT_SIZE);
	}
	for(a=1; a<=numCOM; a++) {
		if (n_ComID[a]>0) {
			delete [] ComID[a];
			ComID[a] = NULL;
		}
	}
	if (ComID) {
		delete [] ComID;
	}
	ComID = tmp2;
}
//============================================================================//
double findTotalDelta() {
	double Delta = 0.0;
	for(uint i=1;i<=numCOM;i++) {
		if (n_ComID[i] <=0) {
			continue;
		}
		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;
	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){
			continue;
		}
		M++;
		degree[a]++;
		degree[b]++;
		if (a > realN) {
			realN = a;
		}
		if (b > realN) {
			realN = b;
		}
	}
	initAdjList(); // initialize the adjList[]
	memset(degree, 0, UINT_SIZE*(N+1)); // memset 0 for degree
	fseek(f,0,SEEK_SET); // 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);
		if (a==b || a<=0 || b<=0){
			continue;
		}
		adjList[a][degree[a]++] = b;
		adjList[b][degree[b]++] = a;
	}
	fclose(f);
}
//============================================================================//
bool tryFormingNewCommunity(uint nodeA, uint nodeB, bool mode) {
	findIntersectionLinearG(nodeA, nodeB); // find adjList[nodeA] intersect adjList[nodeB], the result is in interG[] and n_interG
	bool isOK = (mode==STATIC) ? (n_interG > MIN_NODE) : (n_interG > MIN_NODE && !isDuplicateCom(interG, n_interG));
	if (isOK) { // if they share significant substructure
		uint numEdge = findTotalNumberOfEdges(interG, n_interG); // Find number of edges in the intersection
		bool isOK2 = (n_interG<=MAX_DATA_LIST) ? (numEdge>=suffice_x[n_interG]) : (numEdge>=findSuffice(n_interG));		
		if (isOK2) {
			if (numCOM >= MULTI_N) {
				serr("Error: numCOM > MULTI_N in tryFormingNewCom().");
			}
			markNodes(++numCOM); // mark all the node in the intersection
			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; // copy the numEdgeList[numCOM]
			n_ComID[numCOM] = n_interG; // n_interG is the number of nodes inside this community
			return true;
		}		
	}
	return false;
}
//============================================================================//
void findDenseCommunities(const char filename[]) {	
	cout<<">>> Finding dense communities";
	FILE *f = initOpenFile(filename, "read"); // open file to read
	initCid_numCid_countInt(); // set up initial data
	initComID_n_ComID_numEdgeList(); // Set up initial data
	uint a, b;
	while (!feof(f)) { // Begin the process
		fscanf_s(f,"%u %u", &a, &b);
		if (a==b || a<=0 || b<=0) {
			continue;
		}
		if ( !isInSameCS(a, b, 0) ) {
			tryFormingNewCommunity(a, b, STATIC);
		}		
	}
	fclose(f);
	//////resizeComID_n_ComID(); // <-- For AFOCS, we dont need this
	cout<<". numCOM = "<<numCOM<<endl;
}
//============================================================================//
void combineOverlappingCommunities(bool mode) {
	if (mode==STATIC ) {
		cout<<">>> Merging overlapped communities."<<" Overlapping threshold = "<<OVERLAP_THRESHOLD<<endl;
	}
	bool done=false;
	uint comid=0, j=0, interEdges=0, round=1, *comAdjList=NULL, n_comAdjList=0, comA=0;
	double overlappingScore; // the overlapping score between two communities
	comAdjList = new uint [numCOM]; // initialize comAdjList[]
	if ( !comAdjList ) { // safety check
		serr("Error: !comAdjList[] in combineOverlappingCommunities()");
	}
	while (!done) { // start checking overlapped communities
		if (mode == STATIC) {
			cout<<"Round #"<<round++<<", numCOM = "<<numCOM<<endl;
		} else if (round > STOP_SIGN) {
			break;
		}
		done = true;
		realNumCOM = numCOM; // make a copy of the current number of communities
		for(comid = numCOM; comid >= 1; comid--) {
			findComAdjList(comid, comAdjList, n_comAdjList); // find the adjacent list of community comid
			if (n_comAdjList <= 0) { // if this community does not overlap with any other community
				continue;
			} else if (n_comAdjList >= numCOM) {
				serr("Error: n_comAdjList >= numCOM in combineOverlappingCommunities()");
			}
			for(j=0; j<n_comAdjList; j++) { // if this community is adjacent to at least a community
				comA = comAdjList[j];
				if (comA > numCOM) {
					serr("Error: comA > numCOM in combineOverlappingCommunities()");
				}
				interEdges = 0;
				overlappingScore = findOverlappingScore(comid, comA, interEdges); // find the overlapping score of the two ComID
				if (overlappingScore >= OVERLAP_THRESHOLD) { // if the overlapping score is too big
					if (overlappingScore >= FULL_OVSCORE) {
						swapAndDeleteComID(comA, comid, mode);
						realNumCOM--;
						done = false;
						continue;
					}
					done = false; // we are not done yet
					realNumCOM--; // update the real number of communities
					unionComID(comA, comid, interH, n_interH, interEdges); // combine the two sets & delete community i_th					
					if (n_ComID[comid] <= 0) { // if ComID[i] disappears, we can skip
						break;
					}
				}
			}
		}
		if (!done) {
			reassignCommunityID();
		}
	}
	if (comAdjList) {
		delete comAdjList;
	}
}
//============================================================================//
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 (a==b || a<=0 || b<=0 || 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); // copy to the new community
			n_ComID[numCOM] = MIN_NODE; // Update n_ComID[numCOM]
			numEdgeList[numCOM] = MIN_NODE; // 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) {
	cout<<"\t*** Refining Final Community Assignment ***"<<endl;
	uint i=0, j=0, comid=0;
	//----------------------------//
	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] = new uint [ n_ComID[i] ]; // allocate new memory
		if ( !ComID[i] ) { // safety check
			serr("Error: !ComID[i] in finalRefinement()");
		}
	}
	//----------------------------//
	memset(n_ComID, 0, UINT_SIZE * (numCOM+1)); // clear the current number of communities
	memset(countInt, 0, UINT_SIZE * MULTI_N); // reset countInt and n_countInt to remove duplicate nodes in a community
	n_countInt = 1; // reset n_countInt
	//----------------------------//
	for(i=1; i<=N; i++) {
		if (numCid[i] <= 0) {
			continue;
		}		
		if (numCid[i] >= MAX_NODE_CID) { // safety check
			serr("Error: numCid[i] >= MAX_NODE_CID in finalRefinement()");
		}
		updateCounter();
		for(j=0; j<numCid[i]; j++) {
			comid = Cid[i][j];
			if (comid > numCOM) { // safety check
				serr("Error: comid > numCOM in finalRefinement()");
			}
			if (n_ComID[ comid ] > N) { // safety check
				serr("Error: n_ComID[comid] > N in finalRefinement()");
			}
			if (countInt[comid] != n_countInt) {
				ComID[comid][ n_ComID[comid]++ ] = i;
				countInt[comid] = n_countInt;
			}
		}		
	}
}
//============================================================================//
// This function assign community IDs for vertices that have not been assigned ones yet
uint *visitUnAssignedVertices() {
	cout<<">>> Visiting unasigned vertices"<<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: !(res && res[0] && res[1] && mark && numDegList) 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<=N; 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
			if (x>N || x<=0) {
				serr("Error: x>N || x<=0 in visit UnAssignedVertices()");
			}
			for(k=0; k<numCid[x]; k++) { // Iterate from all community IDs that x may have
				id = Cid[x][k];
				if (id>numCOM || id<=0) {
					serr("Error: id>numCOM || id<=0 in visit UnAssignedVertices()");
				}
				if ( mark[id] == 0 ) {
					mark[ id ] = ++n_res;
					res[0][ n_res ] = id;
				}
				res[1][ mark[id] ]++; ///<--- Remember to replace by weight here -->///
			}
		}
		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
			}
		}
		//--------- If needed, copy Assigning Unassigned nodes here ----------//
	}	
	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;
	}
	return old_n_ComID;
}
//============================================================================//
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[]) {
	findDenseCommunities(filename);
	combineOverlappingCommunities(STATIC);
	findTinyCommunities(filename);
	uint *old_n_ComID = visitUnAssignedVertices();
	finalRefinement(old_n_ComID);	
}
//============================================================================//
void printData(const char FILENAME[], bool printComID, bool printCid, bool printDeg, bool printAdjList, bool printToFile, bool mode) {
	if (mode == STATIC) {
		cout<<"numCOM = "<<numCOM<<endl;
		cout<<"N = "<<N<<endl;
		cout<<"M = "<<M<<endl;
		cout<<"numTinyCom = "<<numCOM-realNumCOM<<endl;
		cout<<"maxDegree = "<<maxDegree<<endl;
		cout<<"maxn_ComID = "<<maxn_ComID<<endl;
		cout<<"maxnumCid = "<<maxnumCid<<endl;
		cout<<"maxOutliers = "<<maxOutliers<<endl;
	}
	uint a,b;
	if (printCid) {
		for(a=1;a<=N;a++) {
			if (numCid[a] > 0) {
				cout<<"Cid["<<a<<"] = {";
				for(b=0;b<numCid[a];b++)
					cout<<Cid[a][b]<<", ";
				cout<<"}"<<endl;
			}
		}
	}
	if (printComID) {
		for(a=1;a<=numCOM;a++) {
			cout<<"ComID["<<a<<"] = {";
			for(b=0;b<n_ComID[a];b++)
				cout<<ComID[a][b]<<", ";
			cout<<"}"<<endl;
		}
	}
	if (printToFile) { // Print everything to a file specified by the FILENAME
		char filename[256], tmp[5];
		strcpy_s(filename,FILENAME);
		size_t len = strlen(FILENAME);
		filename[len-4] = '\0';
		strcat_s(filename, "_CID_AFOCS_");
		_itoa_s(int(OVERLAP_THRESHOLD*100), tmp, 10);
		strcat_s(filename,tmp);
		strcat_s(filename,".txt");
		cout<<"Results = "<<filename<<endl;
		FILE *f = initOpenFile(filename, "write");
		
		for (a = 1; a <= numCOM; a++) {
			for (b = 0; b < n_ComID[a]; b++) {
				fprintf(f, "%u ", ComID[a][b]);
			}
			fprintf(f, "\n");
		}
		fclose(f);
	}
	if (printDeg)
		for(a=1;a<=N;a++)
			cout<<"degree["<<a<<"] = "<<degree[a]<<endl;
	if (printAdjList) {
		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;	
	for(uint 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(uint i=1; i<=numCOM; i++) {
		if (ComID[i] && n_ComID[i]>0) {
			delete [] ComID[i];
		}
	}	
	if (adjList) {
		delete [] adjList;
	}	
	if (Cid) {
		delete [] Cid;
	}
	if (degree) {
		delete [] degree;
	}
	if (numCid) {
		delete [] numCid;
	}
	if (countInt) {
		delete [] countInt;
	}	
	if (ComID) {
		delete [] ComID;
	}
	if (n_ComID) {
		delete [] n_ComID;
	}
}
//============================================================================//
void FOCS(const char filename[]) {
	cout<<"Reading base file: "<<filename;
	readFromFile(filename);
	cout<<". Done."<<endl;
	clock_t tstart = clock(); // Start the timer
	cout<<"+++++++++++++++++++++++++++++++++++++++++++++"<<endl;
	cout<<"+++++++++++++++ Starting FOCS +++++++++++++++"<<endl;
	cout<<"+++++++++++++++++++++++++++++++++++++++++++++"<<endl;
	findOverlappingCommunityStructure(filename);
	clock_t tend = clock(); // Stop the timer	
	tDelta = findTotalDelta();
	cout<<"----- Printing FOCS results -----"<<endl;
	cout<<"Time taken = "<<(double)(tend - tstart)/CLOCKS_PER_SEC<<"s"<<endl;
	bool pCID=false, pComID=false, pDeg=false, pAdjList=false, pToFile=true;
	printData(filename, pComID, pCID, pDeg, pAdjList, pToFile, STATIC);
	cout<<"DONE FOCS"<<endl;
}
//============================================================================//
//==========================BEGIN ADAPTIVE FUNCTION===========================//
//============================================================================//
uint *updateNewNode(uint nodeU, uint arr[], uint n_arr) {
	if (nodeU > MAX_N) {
		serr("Error: nodeU > MAX_N in updateNewNode()");
	}
	uint i=0, *adjNei=NULL, x=0, j=0, comid=0;
	//----------------------------//
	bool isOldNode = false; // indicate whether nodeU is an old node or not
	if (!adjList[nodeU] || degree[nodeU]<=0) { // if nodeU is a new node, we need to allocate memory for it
		adjList[nodeU] = new uint [ DEFAULT_DEG ];
		if (!adjList[nodeU]) {
			serr("Error: !adjList[nodeU] in updateNewNode()");
		}
		if (!Cid[nodeU] || numCid[nodeU]<=0) {
			Cid[nodeU] = new uint [ MAX_NODE_CID ];
			if ( !Cid[nodeU] ) {
				serr("Error: !Cid[nodeU] in updateNewNode()");
			}
		}
		degree[nodeU] = 0; // initialize the degree of nodeU
		numCid[nodeU] = 0; // initialize numCid of nodeU
		realN++; // increase the number of real nodes
		M += n_arr; // increase the number of edges
	} else { // here, nodeU previously existed
		if (!adjList[nodeU]) { // if nodeU is there but we can't find memory for it
			serr("Error: !adjList[nodeU] when nodeU was already existed in updateNewNode()");
		}
		isOldNode = true; // this is an old node
		updateCounter();
		for(i=0; i<numCid[x]; i++) {
			comid = Cid[x][i];
			countInt[comid] = n_countInt; // mark all community of nodeU
		}
		for(i=0; i<n_arr; i++) {
			x = arr[i];
			for(j=0; j<numCid[x]; j++){
				comid = Cid[x][j];
				if (countInt[comid] == n_countInt) { // add one edge into communty if nodeU is previously existed
					numEdgeList[comid]++;
				}
			}
		}
		updateCounter(); // update the counter
		for(i=0; i<degree[nodeU]; i++) { // mark all current nodes in adjList[nodeU]
			x = adjList[nodeU][i];
			countInt[x] = n_countInt;
		}
	}
	//----------------------------//
	adjNei = new uint [numCOM+1];
	if (!adjNei) {
		serr("Error: !adjNei == NULL in updateNewNode()");
	}
	memset(adjNei, 0, (numCOM+1)*UINT_SIZE); // init adjNei[]
	//----------------------------//
	for(i=0; i<n_arr; i++) {
		x = arr[i]; // x is an adjacent node of nodeU		
		if (isOldNode && (countInt[x]==n_countInt || x==nodeU) ) { // skip over existing edge (nodeU, x)
			continue;
		}
		//----------------------------//
		if (!adjList[x] || degree[x]<=0) { // if an adjacent node x of nodeU is also new
			adjList[x] = new uint [ DEFAULT_DEG ]; // locate new memory for x
			if (!adjList[x]) {
				serr("Error: !adjList[x] in updateNewNode()");
			}
			degree[x] = 0; // init degree[x]
			realN++; // increase the number of real nodes
			if (!Cid[x] || numCid[x]<=0) {
				Cid[x] = new uint [MAX_NODE_CID];
				if (!Cid[x]) {
					serr("error: !cid[x] in updatenewnode()");
				}
				numCid[x] = 0; // and numCid[x]
			}
		}
		if (degree[nodeU] > DEFAULT_DEG) { // safety check
			serr("Error : degree[nodeU] > DEFAULT_DEG in updateNewNode()");
		}
		adjList[nodeU][ degree[nodeU]++ ] = x; // update the adjList[nodeU]
		//----------------------------//
		if (degree[x] > DEFAULT_DEG) { // safety check
			serr("Error : degree[x] > DEFAULT_DEG in updateNewNode()");
		}
		if (!isOldNode) { // if nodeU is new
			adjList[x][degree[x]++] = nodeU; // update the adjList[] of U's neighbor
		} else { // else, we need to check whether nodeU was in adjList[x] or not
			bool isExisted = false; // indicates whether nodeU was already in adjList[x] or not
			for (uint j=0; j<degree[x]; j++) {
				if (adjList[x][j] == nodeU) { // it nodeU was already in it
					isExisted = true;
					break;
				}
			}
			if (!isExisted) { // if nodeU hasn't been in the adjList[x] list
				adjList[x][degree[x]++ ] = nodeU; // else, we include it into adjList[x]
			}
		}
		//----------------------------//
		if (numCid[x] > 0) { // find the adjacent community neighbors
			for (uint j=0; j<numCid[x]; j++) {
				comid = Cid[x][j];
				if (n_ComID[comid] >0) {
					adjNei[ comid ]++; // find d_{nodeU, i}
				}				
			}
		}
		//----------------------------//		
		M++; // increase M
	}
	return adjNei;
}
//============================================================================//
void newNode(uint nodeU, uint arr[], uint n_arr) {
	uint i=0, *adjNei=NULL, nA=0, comid=0;
	adjNei = updateNewNode(nodeU, arr, n_arr); // Update the basic information
	updateCounter();
	for(i=0; i<numCid[nodeU]; i++) {
		comid = Cid[nodeU][i];
		if (n_ComID[comid] >  0) { // if community comid is still alive
			countInt[comid] = n_countInt;
		}
	}
	for(i=1; i<=numCOM; i++) {
		if (adjNei[i]<=0 || n_ComID[i]<MIN_NEWNODE || countInt[i]==n_countInt) { // should check whether nodeU was previously in this community or not
			continue;
		}
		nA = n_ComID[i]+1;
		uint sufficeEdge = (n_ComID[i]<=MAX_DATA_LIST) ? suffice_x[nA] : findSuffice(nA);
		if (adjNei[i] + numEdgeList[i] >= sufficeEdge) { // make sure that we dont count communities that nodeU is already in
			if (numCid[nodeU] >= MAX_NODE_CID) {
				serr("Error: numCid[nodeU] >= MAX_NODE_CID in newNode()");
			}
			Cid[nodeU][numCid[nodeU]++] = i; // include nodeU in community i_th
			numEdgeList[i] += adjNei[i];
			uint *tmp;
			tmp = new uint [n_ComID[i]+1];
			if (!tmp) {
				serr("Error: !tmp[] in newNode()");
			}
			memcpy(tmp, ComID[i], n_ComID[i] * UINT_SIZE);
			tmp[n_ComID[i]++] = nodeU;			
			if (ComID[i]) {
				delete [] ComID[i];
			}
			ComID[i] = tmp;
		}
	}	
	for(i=0; i<n_arr; i++) {
		if ( !isInSameCS(arr[i], nodeU, 0) ) {
			tryFormingNewCommunity(arr[i], nodeU, ADAPTIVE);
		}
	}	
	if (adjNei) {
		delete [] adjNei;
	}	
}
//============================================================================//
bool updateNewEdge(uint nodeU, uint nodeV) {
	if (nodeU>MAX_N || nodeV>MAX_N) { // if they are out of range
		serr("Error: nodeU>=MAX_N || nodeV>=MAX_N in updateNewEdge()");
	}
	if (!adjList[nodeU]) { // allocate memory for adjList[nodeU] if needed
		adjList[nodeU] = new uint [DEFAULT_DEG];
		if (!adjList[nodeU]) {
			serr("Error: !adjList[nodeU] in updateNewEdge()");
		}
		degree[nodeU] = 0;		
	}
	if (!Cid[nodeU]) { // allocate memory for Cid[nodeU] if needed
		Cid[nodeU] = new uint [MAX_NODE_CID];
		if ( !Cid[nodeU] ) {
			serr("Error: !Cid[nodeU] in updateNewEdge()");
		}
		numCid[nodeU] = 0;
	}
	if (!adjList[nodeV]) {// allocate memory for adjList[nodeV] if needed
		adjList[nodeV] = new uint [DEFAULT_DEG];
		if (!adjList[nodeV]) {
			serr("Error: !adjList[nodeV] in updateNewEdge()");
		}
		degree[nodeV] = 0;		
	}
	if (!Cid[nodeV]) {// allocate memory for Cid[nodeU] if needed
		Cid[nodeV] = new uint [MAX_NODE_CID];
		if ( !Cid[nodeV] ) {
			serr("Error: !Cid[nodeV] in updateNewEdge()");
		}
		numCid[nodeV] = 0;
	}
	//-------------------------//
	uint i;
	bool isExisted = false;
	for(i=0; i<degree[nodeU]; i++) { // check whether nodeU is already in adjList[nodeV] or not
		if (adjList[nodeU][i]==nodeV) {
			isExisted = true;
			break;
		}
	}
	if (!isExisted) { // if not, include nodeV in adjList[nodeU]
		adjList[nodeU][degree[nodeU]++] = nodeV;
	}
	isExisted = false;
	for(i=0; i<degree[nodeV]; i++) { // check whether nodeV is already in adjList[nodeU] or not
		if (adjList[nodeV][i]==nodeU) {
			isExisted = true;
			break;
		}
	}
	if (!isExisted) { // if not, include nodeU in adjList[nodeV]
		adjList[nodeV][degree[nodeV]++] = nodeU;
	}
	//-------------------------//
	updateCounter(); // update the counter
	uint comid=0;
	for(i=0; i<numCid[nodeU]; i++) { // mark all community id(s) of nodeU
		comid = Cid[nodeU][i];
		if (n_ComID[comid] >0) {
			countInt[ comid ] = n_countInt;
		}
	}
	bool inSameCS = false;
	for(i=0; i<numCid[nodeV]; i++) { // check whether these two nodes are in the same community or not
		comid = Cid[nodeV][i];
		if (countInt[comid] == n_countInt) {
			numEdgeList[ comid ]++;
			inSameCS = true;
		}
	}
	return inSameCS;
}
//============================================================================//
// This function checks whether a node nodeU should be in another community when a new edge is added
void checkNodeMove2Com(uint nodeU) {
	uint i=0, j=0, x=0, comI=0, comid=0;
	updateCounter();
	//----------------------//
	for(i=0; i<numCid[nodeU]; i++) { // mark the communities that nodeU is already in
		comid = Cid[nodeU][i];
		if (n_ComID[comid] > 0) {
			countInt[ comid ] = n_countInt;
		}
	}
	//----------------------//
	for(i=0; i<degree[nodeU]; i++) { // scan through the adjacent list
		x = adjList[nodeU][i]; // x is an adjacent node of nodeU
		for(j=0; j<numCid[x]; j++) {
			comI = Cid[x][j]; // get the community id of x
			if (countInt[comI]==n_countInt || n_ComID[comI]<=1) { // if we find a community that we have already marked, skip it
				continue;
			}
			countInt[comI] = n_countInt; // else, mark that community
			uint nEdge = numEdge2Com(nodeU, comI); // find number of edges nodeU has to that community
			uint numsEdge = (n_ComID[comI]+1 <= MAX_DATA_LIST) ? suffice_x[n_ComID[comI]+1] : findSuffice(n_ComID[comI]+1);
			if ( (nEdge>=2.0*numEdgeList[comI]/(n_ComID[comI]-1)) || (nEdge+numEdgeList[comI]>=numsEdge)) { // if the number of edges suffices
				if (numCid[nodeU] >= MAX_NODE_CID) { // safety check
					serr("Error: numCid[nodeU] >= MAX_NODE_CID in checkNodeMove2Com()");
				}
				Cid[nodeU][numCid[nodeU]++] = comI; // update the Cid[nodeU]
				numEdgeList[comI] += nEdge;
				uint *tmp;
				tmp = new uint [n_ComID[comI] + 1];
				if (!tmp) {
					serr("Error: !tmp in checkNodeMove2Com()");
				}
				memcpy(tmp, ComID[comI], n_ComID[comI] * UINT_SIZE); // copy the current ComID[comI]
				tmp[n_ComID[comI]++] = nodeU; // include nodeU				
				if (ComID[comI]) { // delete the current ComID[comI]
					delete [] ComID[comI];
				}
				ComID[comI] = tmp; // refer to a new link
				countInt[comI] = n_countInt; // mark that this community has been recorded
			}
		}
	}
}
//============================================================================//
int newEdge(uint nodeU, uint nodeV) {
	bool inSameCS = updateNewEdge(nodeU, nodeV);
	if (inSameCS || degree[nodeU]<=1 || degree[nodeV]<=1) {
		return 0;
	}
	bool isOK = tryFormingNewCommunity(nodeU, nodeV, ADAPTIVE);
	if ( !isOK ) {
		checkNodeMove2Com(nodeU);
		checkNodeMove2Com(nodeV);
	}
	return 1;
}
//============================================================================//
void removeNodeFromCom(uint nodeU, uint comid) {
	if (n_ComID[comid] <= 0) {			
		return;
	}
	uint i=0;
	for(i=0; i<n_ComID[comid] && ComID[comid][i]!=nodeU; i++);
	if (i < n_ComID[comid]-1) {
		memcpy(ComID[comid]+i, ComID[comid]+i+1, (n_ComID[comid]-i-1)*UINT_SIZE);
	}
	n_ComID[comid] = MAX(n_ComID[comid]--, 0);
}
//============================================================================//
void removeNodeFromAdjList(uint nodeU) {
	uint i=0, j=0, x=0;
	for(i=0; i<degree[nodeU]; i++) {
		x = adjList[nodeU][i];
		if (degree[x] <= 0) {
			continue;
		}
		for(j=0; j<degree[x] && adjList[x][j]!=nodeU; j++);
		if(j < degree[x]-1) {
			memcpy(adjList[x]+j, adjList[x]+j+1, (degree[x]-j-1)*UINT_SIZE);
		}
		degree[x] = MAX(degree[x]--, 0);
	}
	degree[nodeU] = 0;
}
//============================================================================//
void removeNode(uint nodeU) {
	if (nodeU > MAX_N) {
		serr("Error: nodeU>MAX_N in removeNode()");
	}
	if (degree[nodeU]<=0 || !adjList[nodeU])	 {
		cout<<"Warning: node "<<nodeU<<" is not previously existed prior to its removal in removeNode()"<<endl;
		return;
	}
	uint comid=0, numEdge=0, i=0, j=0, x=0, y=0, t=0, k=0;	
	//-----------------------------------//
	uint *ncomidcpy = new uint [ numCid[nodeU] ]; // make a back up of number of nodes in each community nodeU is adjacent to
	if (!ncomidcpy) {
		serr("Error: !ncomidcpy[] in removeNode()");
	}
	//-----------------------------------//
	for(i=0; i<numCid[nodeU]; i++) {
		comid = Cid[nodeU][i]; // get the community id
		uint numE2Com = numEdge2Com(nodeU, comid);
		numEdge = numEdgeList[comid] - numE2Com; // find the number of left over edges
		removeNodeFromCom(nodeU, comid); // remove nodeU from this community
		bool isOK = (n_ComID[comid]<=MAX_DATA_LIST) ? (numEdge>=suffice_x[n_ComID[comid]]) : (numEdge>=findSuffice(n_ComID[comid])); // check whether this number of edges suffices
		if (isOK) { // if this community still has a sufficient number of edges			
			ncomidcpy[i] = 0; // then we dont have to worry about this community
			numEdgeList[comid] = numEdge; // update the number of edges			
		} else { // else, we need to do something here			
			ncomidcpy[i] = n_ComID[comid]; // store the old number of nodes 
			n_ComID[comid] = 0; // mark that community comid has been deleted because of insufficient edges			
			numEdgeList[comid] = 0;
		}
	}
	//-----------------------------------//
	removeNodeFromAdjList(nodeU);
	//-----------------------------------//
	uint oldnumcom = numCOM;
	for(i=0; i<numCid[nodeU]; i++) {
		comid = Cid[nodeU][i];
		if (ncomidcpy[i] <=0) {
			continue;
		}
		for(j=0; j<ncomidcpy[i]-1; j++) {
			x = ComID[comid][j];						
			for(t=0; t<degree[x]; t++) {
				y = adjList[x][t];
				for(k=0; k<numCid[y]; k++) {
					if (Cid[y][k]==comid && !isInSameCS(x, y, oldnumcom )) {
						tryFormingNewCommunity(x, y, STATIC); // <-- **** n_countInt can be changed in here 						
					}
				}
			}
		}
		if (ComID[comid]) { // now we delete the old community
			delete [] ComID[comid];
			ComID[comid] = NULL;			
		}
		n_ComID[comid] = 0; // make sure that no node is in this commnunity
		numEdgeList[comid] = 0; // and also no edges
	}
	if (ncomidcpy) {
		delete [] ncomidcpy;
	}
	//-----------------------------------//	
	numCid[nodeU] = 0;
	degree[nodeU] = 0;
}
//============================================================================//
bool updateRemoveEdge(uint nodeU, uint nodeV, uint *sharedCid, uint &n_sharedCid) {
	n_sharedCid = 0;
	if (nodeU>N || nodeV>N) {
		serr("Error: nodeU>N || nodeU<=0 || nodeV>N || nodeV<=0 in updateRemoveEdge()");
	}
	if (degree[nodeU]<=0 || degree[nodeV]<=0) {
		cout<<"Warning_0: edge ("<<nodeU<<", "<<nodeV<<") does not previously exist in updateRemoveEdge()"<<endl;
		return false;
	}
	//-------------------------------------//
	// Here, nodeU and nodeV all have degrees >= 1
	uint i=0, j=0;
	bool need2Process = true;
	for(i=0; i<degree[nodeU] && nodeV!=adjList[nodeU][i]; i++); // find where nodeV is in adjList[nodeU]
	if (i >= degree[nodeU]) { // this means nodeU and nodeV has never been adjacent to each other
		cout<<"Warning_1: edge ("<<nodeU<<", "<<nodeV<<") does not exist in updateRemoveEdge()"<<endl;
		return false;
	} else if (i < degree[nodeU]-1){
		memcpy(adjList[nodeU]+i, adjList[nodeU]+i+1, (degree[nodeU]-i-1) * UINT_SIZE); // copy memory to remove nodeV
		degree[nodeU]--; // since degree[nodeU] >=1, this will not hurt
		if (degree[nodeU] <= 0) { // this means degree[nodeU] == 1
			for(j=0; j<numCid[nodeU]; j++) {
				removeNodeFromCom(nodeU, Cid[nodeU][j]);
			}
			need2Process = false; // so we dont need to process 
		}
	}
	for(i=0; i<degree[nodeV] && nodeU!=adjList[nodeV][i]; i++); // find where nodeV is in adjList[nodeU]
	if (i >= degree[nodeV]) { // this means nodeU and nodeV has never been adjacent to each other
		cout<<"Warning_2: edge ("<<nodeU<<", "<<nodeV<<") does not exist in updateRemoveEdge()"<<endl;
		return false;
	} else if (i < degree[nodeV]-1) {
		memcpy(adjList[nodeV]+i, adjList[nodeV]+i+1, (degree[nodeV]-i-1) * UINT_SIZE); // copy memory to remove nodeV
		degree[nodeV]--; // since degree[nodeU] >=1, this will not hurt
		if (degree[nodeV] <= 0) { // this means degree[nodeV] == 1
			for(j=0; j<numCid[nodeV]; j++) {
				removeNodeFromCom(nodeV, Cid[nodeV][j]);
			}
			need2Process = false; // and we dont need to process
		}
	}
	//-------------------------------------//
	// now we subtract one edge from any community that contain both nodeU and nodeV	
	updateCounter();
	uint comid;
	for(i=0; i<numCid[nodeU]; i++) { // mark community id(s) in Cid[nodeU] first
		comid = Cid[nodeU][i];
		if (n_ComID[comid]> 0) {
			countInt[ comid ] = n_countInt;
		}
	}
	for(i=0; i<numCid[nodeV]; i++) { // then check nodes in Cid[nodeV]
		comid = Cid[nodeV][i];
		if (n_ComID[comid]<=0 || countInt[comid]!=n_countInt) {
			continue;
		}
		numEdgeList[comid] = MAX(numEdgeList[comid]-1,0); // exclude 1 edge from numEdgeList[comid]
		if (n_sharedCid >= DEFAULT_DEG/2) { // safety check
			serr("Error: n_sharedCid >= DEFAULT_DEG/2 in updateRemoveNode()");
		}
		sharedCid[n_sharedCid++] = comid; // record the shared community id between nodeU and nodeV
	}
	return need2Process;
}
//============================================================================//
bool removeEdge(uint nodeU, uint nodeV) {
	uint *sharedCid = new uint [DEFAULT_DEG/2];
	if (!sharedCid) {
		serr("Error: !sharedCid[] in removeEdge()");
	}
	uint n_sharedCid=0, comid=0;
	bool need2Process = updateRemoveEdge(nodeU, nodeV, sharedCid, n_sharedCid); // update the removed edge and check whether we need to go further or not
	if (!need2Process) { // if we dont have to do anything
		if (sharedCid) { // delete the allocated memory
			delete [] sharedCid;
		}
		return false;
	}
	//-----------------------------//
	uint i=0, j=0, t=0, x=0, y=0, k=0;
	uint oldnumcom = numCOM;
	for(i=0; i<n_sharedCid; i++) {
		comid = sharedCid[i];
		uint n_comid = n_ComID[comid];
		bool isOK = (n_comid<=MAX_DATA_LIST) ? (numEdgeList[comid]>=suffice_x[n_comid]) : (numEdgeList[comid]>=findSuffice(n_comid)); // check whether comid has enough sufficient edges
		if (isOK) { // if it does
			continue;
		}
		// else, if it doesnt, it should be broken into smaller pieces
		n_ComID[comid] = 0;
		for(j=1; j<n_comid-1; j++) {
			x = ComID[comid][j]; // x is a node in comid
			for(t=0; t<degree[x]; t++) {
				y = adjList[x][t];
				for(k=0; k<numCid[y]; k++) {
					if (Cid[y][k]==comid && !isInSameCS(x, y, oldnumcom)) {
						tryFormingNewCommunity(x, y, STATIC);
					}
				}
			}
		}
		//-----------------------------//
		if (ComID[comid]) {
			delete [] ComID[comid];
			ComID[comid] = NULL;
		}
		numEdgeList[comid] = 0;
		n_ComID[comid] = 0;
	}	
	return true;
}
//============================================================================//
void printData2File(uint totalCom[], double runningTime[], double totalDelta[], double overlapThreshold, uint numFile) {
	uint i;
	char fname[200], str[3];	
	strcpy_s(fname, "Result_totalNumCOM_");
	_itoa_s(int(overlapThreshold*100), str, 10);
	strcat_s(fname, str);
	strcat_s(fname, ".txt");
	FILE *f = initOpenFile(fname, "write");
	for(i=1;i<=numFile;i++)
		fprintf(f, "%d\n",totalCom[i]);
	fprintf(f, "OVERLAP_THRESHOLD = %0.4f", overlapThreshold);
	fclose(f);
	//-------------------------//	
	strcpy_s(fname, "Result_runningTime_");
	strcat_s(fname, str);
	strcat_s(fname, ".txt");
	f = initOpenFile(fname, "write");
	for(i=1;i<=numFile;i++)
		fprintf(f, "%0.4f\n",runningTime[i]);
	fprintf(f, "OVERLAP_THRESHOLD = %0.4f", overlapThreshold);
	fclose(f);
	//-------------------------//	
	strcpy_s(fname, "Result_totalDelta_");
	strcat_s(fname, str);
	strcat_s(fname, ".txt");
	f = initOpenFile(fname, "write");
	for(i=1;i<=numFile;i++)
		fprintf(f, "%0.4f\n",totalDelta[i]);
	fprintf(f, "OVERLAP_THRESHOLD = %0.4f", overlapThreshold);
	fclose(f);
}
//============================================================================//
void AFOCS(const char file_add[], uint numFile) {
	clock_t timeAll, timeRound;
	char fName[1000], str[5];
	uint i=0, link[DEFAULT_DEG], n_link=0, count=0, v=0;
	int u=0, node=0;	
	FILE *f;
	cout<<"++++++++++++++++++++++++++++++++++++++++++++++"<<endl;
	cout<<"+++++++++++++++ Starting AFOCS +++++++++++++++"<<endl;
	cout<<"++++++++++++++++++++++++++++++++++++++++++++++"<<endl;
	timeAll = clock(); // record the starting time
	for(i = 1; i <= numFile; i++) {
		cout<<"------------- file #"<<i<<" -------------"<<endl;
		strcpy_s(fName,file_add);
		_itoa_s(i,str,10);
		strcat_s(fName,str);
		strcat_s(fName,".txt");
		f = initOpenFile(fName, "read"); // open each additional input file to read
		timeRound = clock(); // starting time at each round
		fscanf_s(f,"%d %u", &u, &v); // read data from file
		while ( u !=0 ) {
			node = u;
			link[0] = v;
			n_link = 1;
			while (node==u && u!=0) { // read adjacent nodes of u until we meet a new node
				if (node < 0) { // notice for node - edge removal
					u = 0;
					fscanf_s(f,"%d %u",&u, &v); // read the next item
					break;
				}
				u = 0;
				fscanf_s(f,"%d %u",&u, &v);
				if (node != u) { // if we find a new node, break
					break;
				}
				if (n_link >= DEFAULT_DEG) { // if this nodes have too many neighbors
					serr("Error: n_link >= DEFAULT_DEG in AFOCS()");
				}
				if (u !=0 ) { // esle, include this into the list
					link[n_link++] = v;
				}
			}
			//----------------------------------//
			if (node < 0) { // notice for node-edge removal
				if (link[0] <= 0) { // if the second element is 0 ...
					removeNode((uint)(-node)); // then ths is node removal
					combineOverlappingCommunities( ADAPTIVE ); // combine overlapping communities
				} else {
					removeEdge((uint)(-node), link[0]); // else, this is edge removal
					combineOverlappingCommunities( ADAPTIVE ); // combine CS
				}
			} else { // node-edge addition
				if (n_link > 1) { // if we have to add a new node
					newNode((uint)node, link, n_link); // Update the network				
				} else { // else, add a new edge
					newEdge(node, link[0]); // update the network
				}
				count++;
				if ( count % NUM_NNODE == 0 ) {
					combineOverlappingCommunities( ADAPTIVE ); // combine CS
					count = 0;
				}
			}
		}
		combineOverlappingCommunities( ADAPTIVE );
		cout<<"Time = "<<(double)(clock() - timeRound)/CLOCKS_PER_SEC<<"s"<<endl;
		double dt = findTotalDelta();
		cout<<"Delta["<<i<<"] = "<<dt<<endl;
		cout<<"numCOM = "<<numCOM<<endl;
		cout<<"Avg density = "<<dt/numCOM<<endl;		
		bool pComID=false, pCID=false, pDeg=false, pAdjList=false, pToFile = true;
		printData(fName, pComID, pCID, pDeg, pAdjList, pToFile, ADAPTIVE);
		fclose(f);
	}	
	cout<<"Total time = "<<(double)(clock() - timeAll)/CLOCKS_PER_SEC<<"s"<<endl;
}
//============================================================================//
//========================== END ADAPTIVE FUNCTION ===========================//
//============================================================================//
void doAFOCS(const char base_file[], const char file_path[], const uint numFile){
	FOCS(base_file); // doing FOCS - the first phase	
	AFOCS(file_path, numFile); // doing AFOCS - the adaptive phase
	cleanUpData(); // clean up data after used
	cout << "*********** ALL DONE ***********" << endl;
}