Source

IntroToAlgorithm3ed / src / NCKUAlg / ProgHW5 / disjointSetForest_timing.c

/*
 * Copyright (C) 2012 Eric Chen(G+ page:HencriceFOSS, gmail:hencrice+FOSS+HW5@gmail.com)
 * This file is a part of introtoalgorithm3ed.
 *
 * introtoalgorithm3ed is a free software; you can redistribute it and/or modify it under the terms of the GNU General
 * Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option)
 * any later version.
 *
 * This software is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the
 * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
 * License for more details.
 *
 * You should have received a copy of the GNU General Public License along with this source file; if not, write to the
 * Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <limits.h>
struct Node {
	struct Node *parentPtr;
	int value;
	int rank;
};
struct additionalInfoForPrintUnionPerNode{
	int numOfChildren,childrenNumLimit,*childrenIndexArr;
//	struct Node *actualPtrToNode;//required?
//	struct Node *actualPtrToChildrenArr;//required?
};
struct allSets {
	struct Node *nodeArr;
	struct additionalInfoForPrintUnionPerNode *nodeInfoArr;
};
void printUnion(struct Node *rootPtr, struct allSets *setsPtr, int nodeNumLimit,FILE *outputFile);
void dfsPrint(int *exploredArr,struct Node *rootPtr,struct allSets *setsPtr,FILE *outputFile);
struct Node* unionFunc(struct Node *xPtr, struct Node *yPtr);
void unionFuncUpdateInfo(struct additionalInfoForPrintUnionPerNode *nodeInfoArr,struct Node *root1Ptr,struct Node *root2Ptr,int root1Rank,int root2Rank);
struct Node makeSet(struct Node *xPtr, int value);
struct additionalInfoForPrintUnionPerNode makeSetUpdateInfo(struct additionalInfoForPrintUnionPerNode* newInfoNodePtr);
struct Node* linkFunc(struct Node *xPtr, struct Node *yPtr);
struct Node* findSet(struct Node *xPtr);

int main(int argc, char *argv[]) {
	char *inputFileName, *outputFileName;
	if (argc == 1) {
		inputFileName = "./test3.txt";
		outputFileName = "./output.txt";
	} else {
		inputFileName = argv[1];
		outputFileName = argv[2];
	}
	FILE *inputFile = fopen(inputFileName, "r");
	FILE *outputFile = fopen(outputFileName, "w");
	if (inputFile == NULL || outputFile == NULL) {
		printf("Program terminates because %s can't be found\n", inputFileName);
		exit(1);
	}
	double totalTimeSpent=0;
	clock_t cl1,cl2;//clock(), totalTimeSpent+=(cl2-cl1)/(double)CLOCKS_PER_SEC;UINT_MAX
	int nodeNumLimit=1000000;
	struct allSets sets={realloc(NULL,nodeNumLimit*sizeof(struct Node)),realloc(NULL,nodeNumLimit*sizeof(struct additionalInfoForPrintUnionPerNode))};
	const int maxCharLength = 128;
	char aLine[maxCharLength],*numberStr;
	int number1,number2,timesCmdUExec=0,timesCmdMExec=0,timesCmdFExec=0;
	cl1=clock();
	printf("clk1:%d\n",cl1);
	while (fgets(aLine, sizeof aLine, inputFile) != NULL) //read a line
	{
//		printf("Command: %s",aLine);//useless when timing program
//		fprintf(outputFile, "Command: %s",aLine);//useless when timing program
		strtok(aLine," ");//get rid of command char. For ex, 'u', 'm'......
		numberStr=strtok(NULL," ");
		number1=atoi(numberStr);
		switch(aLine[0]){
			case 'u'://unionFunc
				numberStr=strtok(NULL," ");//read 2nd number
				number2=atoi(numberStr);
//				printf("Uniting 2 sets...\n");//useless when timing program
//				fprintf(outputFile, "Uniting 2 sets...\n");//useless when timing program
				struct Node *beforeUnionRoot1Ptr=findSet(&(sets.nodeArr[number1-1])), *beforeUnionRoot2Ptr=findSet(&(sets.nodeArr[number2-1]));
				int beforeUnionRoot1Rank=beforeUnionRoot1Ptr->rank,beforeUnionRoot2Rank=beforeUnionRoot2Ptr->rank;
				//start timing
	            struct Node *rootPtr=unionFunc(&(sets.nodeArr[number1-1]),&(sets.nodeArr[number2-1]));
				//stops timing
				if(beforeUnionRoot1Rank>beforeUnionRoot2Rank)
					sets.nodeArr[(beforeUnionRoot1Ptr->value)-1]=(*rootPtr);
				else
					sets.nodeArr[(beforeUnionRoot2Ptr->value)-1]=(*rootPtr);
//				unionFuncUpdateInfo(sets.nodeInfoArr,beforeUnionRoot1Ptr,beforeUnionRoot2Ptr,beforeUnionRoot1Rank,beforeUnionRoot2Rank);//useless when timing program
				//print all nodes in the newly created union
//				printf("Resulting union:\n");//useless when timing program
//				fprintf(outputFile, "Resulting union:\n");//useless when timing program
//				printUnion(rootPtr,&sets,nodeNumLimit,outputFile);//useless when timing program
				timesCmdUExec++;
				break;
			case 'm':{//makeSet
//				printf("Making a new set with value: %d\n",number1);//useless when timing program
//				fprintf(outputFile, "Making a new set with value: %d\n",number1);//useless when timing program
				//start timing
				struct Node *newNodePtr=realloc(NULL,sizeof(struct Node));
				sets.nodeArr[number1-1]=makeSet(newNodePtr,number1);
				//stop timing
//				struct additionalInfoForPrintUnionPerNode *newNodeInfoPtr=realloc(NULL,sizeof(struct additionalInfoForPrintUnionPerNode));//useless when timing program
//				sets.nodeInfoArr[number1-1]=makeSetUpdateInfo(newNodeInfoPtr);//useless when timing program
				timesCmdMExec++;
			}
				break;
			case 'f':{//findSet
//				printf("Trying to find the representative of node: %d\n",number1);//useless when timing program
//				fprintf(outputFile, "Trying to find the representative of node: %d\n",number1);//useless when timing program
				//start timing
				struct Node *representativePtr=findSet(&(sets.nodeArr[number1-1]));
				//stop timing
//				printf("The representative found: %d\n",(representativePtr->value));//useless when timing program
//				fprintf(outputFile, "The representative found: %d\n",(representativePtr->value));//useless when timing program
				timesCmdFExec++;
			}
				break;
			default:
				printf("Fatal Error!\n");
				exit(1);
		}
//		printf("\n");//useless when timing program
//		fprintf(outputFile, "\n");//useless when timing program
		cl2=clock();
		printf("clk2:%d\n",cl2);
		if((cl2-cl1)>UINT_MAX/2){
			totalTimeSpent+=(cl2-cl1)/(double)CLOCKS_PER_SEC;
			cl1=cl2;
		}
	}
	totalTimeSpent+=(cl2-cl1)/(double)CLOCKS_PER_SEC;
	printf("Finish processing all commands!\n");
	fprintf(outputFile,"Finish processing all commands!\n");
	printf("\n");
	fprintf(outputFile,"\n");
	printf("The following is how many time a type of command is executed:\n");
	fprintf(outputFile, "The following is how many time a type of command is executed:\n");
	printf("Command 'u': %d\nCommand 'm': %d\nCommand 'f': %d\n",timesCmdUExec,timesCmdMExec,timesCmdFExec);
	fprintf(outputFile, "Command 'u': %d\nCommand 'm': %d\nCommand 'f': %d\n",timesCmdUExec,timesCmdMExec,timesCmdFExec);
	printf("Because a node requires %ld bytes, and command 'm' has been executed %d times. As a result, total memory usage is %ld bytes\n",sizeof(struct Node),timesCmdMExec,timesCmdMExec*sizeof(struct Node));
	fprintf(outputFile, "Because a node requires %ld bytes, and command 'm' has been executed %d times. As a result, total memory usage is %ld bytes\n",sizeof(struct Node),timesCmdMExec,timesCmdMExec*sizeof(struct Node));
	printf("Total time spent: %.10lf sec, so in average, each command takes: %.10lf sec\n",totalTimeSpent,totalTimeSpent/(timesCmdUExec+timesCmdMExec+timesCmdFExec));
	fprintf(outputFile, "Total time spent: %.10lf sec, so in average, each command takes: %.10lf sec\n",totalTimeSpent,totalTimeSpent/(timesCmdUExec+timesCmdMExec+timesCmdFExec));
	fclose(inputFile);
	fclose(outputFile);
	return 0;
}
void printUnion(struct Node *rootPtr, struct allSets *setsPtr, int nodeNumLimit,FILE *outputFile){
	int nodeExplored[nodeNumLimit],i;
	for(i=0;i<nodeNumLimit;i++)//mark all nodes as unexplored
		nodeExplored[i]=0;
	printf("[ ");
	fprintf(outputFile, "[ ");
	dfsPrint(nodeExplored,rootPtr,setsPtr,outputFile);
	printf("]\n");
	fprintf(outputFile, "]\n");
	for(i=0;i<nodeNumLimit;i++)//clean up all node which were marked as explored to nonexplored for next call to this func
		nodeExplored[i]=0;
}
void dfsPrint(int *exploredArr,struct Node *rootPtr,struct allSets *setsPtr,FILE *outputFile){
	int currentNodeIndex=(rootPtr->value)-1,i,childNodeIndex;
	exploredArr[currentNodeIndex]=1;//mark current node as explored
	printf("%d ",rootPtr->value);
	fprintf(outputFile,"%d ",rootPtr->value);
	for(i=0;i<(setsPtr->nodeInfoArr)[currentNodeIndex].numOfChildren;i++){
		childNodeIndex=(setsPtr->nodeInfoArr)[currentNodeIndex].childrenIndexArr[i];
		if(exploredArr[childNodeIndex]==0)
			dfsPrint(exploredArr,&((setsPtr->nodeArr)[childNodeIndex]),setsPtr,outputFile);
	}
}
struct Node* unionFunc(struct Node *xPtr, struct Node *yPtr){
	return linkFunc(findSet(xPtr),findSet(yPtr));
}
void unionFuncUpdateInfo(struct additionalInfoForPrintUnionPerNode *nodeInfoArr,struct Node *root1Ptr,struct Node *root2Ptr,int root1Rank,int root2Rank){
	int root1Index=(root1Ptr->value)-1,root2Index=(root2Ptr->value)-1;
	if (root1Rank>root2Rank){
		int numOfChildren=nodeInfoArr[root1Index].numOfChildren;
		(nodeInfoArr[root1Index].numOfChildren)++;
		//test
//		printf("nodeInfoArr[%d].numOfChildren=%d\n",root1Index,nodeInfoArr[root1Index].numOfChildren);
		//test
		if(numOfChildren<=nodeInfoArr[root1Index].childrenNumLimit)
			nodeInfoArr[root1Index].childrenIndexArr[numOfChildren]=root2Index;//root2Ptr as child
		else{
			nodeInfoArr[root1Index].childrenNumLimit+=200;
			int *tempArr=realloc(NULL,nodeInfoArr[root1Index].childrenNumLimit*sizeof(int));
			int i;
			for(i=0;i<numOfChildren;i++)//first save all value to temporary storage
				tempArr[i]=nodeInfoArr[root1Index].childrenIndexArr[i];
			nodeInfoArr[root1Index].childrenIndexArr=realloc(NULL,(nodeInfoArr[root1Index].childrenNumLimit)*sizeof(int));//extend array memory size
			for(i=0;i<numOfChildren;i++)//copy all value back from temp storage
				nodeInfoArr[root1Index].childrenIndexArr[i]=tempArr[i];
			nodeInfoArr[root1Index].childrenIndexArr[numOfChildren]=root2Index;//add new child
		}
	}else{
		int numOfChildren=nodeInfoArr[root2Index].numOfChildren;
		(nodeInfoArr[root2Index].numOfChildren)++;
		//test
//		printf("nodeInfoArr[%d].numOfChildren=%d\n",root2Index,nodeInfoArr[root2Index].numOfChildren);
		//test
		if(numOfChildren<=nodeInfoArr[root2Index].childrenNumLimit)
			nodeInfoArr[root2Index].childrenIndexArr[numOfChildren]=root1Index;//root1Ptr as child
		else{
			nodeInfoArr[root2Index].childrenNumLimit+=200;
			int *tempArr=realloc(NULL,nodeInfoArr[root2Index].childrenNumLimit*sizeof(int));
			int i;
			for(i=0;i<numOfChildren;i++)//first save all value to temporary storage
				tempArr[i]=nodeInfoArr[root2Index].childrenIndexArr[i];
			nodeInfoArr[root2Index].childrenIndexArr=realloc(NULL,(nodeInfoArr[root2Index].childrenNumLimit)*sizeof(int));//extend array memory size
			for(i=0;i<numOfChildren;i++)//copy all value back from temp storage
				nodeInfoArr[root2Index].childrenIndexArr[i]=tempArr[i];
			nodeInfoArr[root2Index].childrenIndexArr[numOfChildren]=root1Index;//add new child
		}
	}
}
struct Node makeSet(struct Node *xPtr, int value){
	(xPtr->parentPtr)=xPtr;
	(xPtr->rank)=0;
	(xPtr->value)=value;
	return (*xPtr);
}
struct Node* linkFunc(struct Node *xPtr, struct Node *yPtr){
	if ((xPtr->rank)>(yPtr->rank)){
		(yPtr->parentPtr)=xPtr;
		return xPtr;
	}
	else{
		(xPtr->parentPtr)=yPtr;
		if ((xPtr->rank)==(yPtr->rank))
			(yPtr->rank)++;
		return yPtr;
	}
}
struct Node* findSet(struct Node *xPtr){
	if ((xPtr->parentPtr)!=xPtr)
		(xPtr->parentPtr)=findSet(xPtr->parentPtr);
	return (xPtr->parentPtr);
}
struct additionalInfoForPrintUnionPerNode makeSetUpdateInfo(struct additionalInfoForPrintUnionPerNode* newInfoNodePtr){
	(newInfoNodePtr->numOfChildren)=0;
	(newInfoNodePtr->childrenNumLimit)=2;
	(newInfoNodePtr->childrenIndexArr)=realloc(NULL,(newInfoNodePtr->childrenNumLimit)*sizeof(int));
	return (*newInfoNodePtr);
}