Source

IntroToAlgorithm3ed / src / NCKUAlg / ProgHW5 / disjointSetForest_v1.c

Full commit
/*
 * 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>
struct Node {
	struct Node *parentPtr;
	int value;
	int rank;
};
struct allSets {
	struct Node *nodeArr;
	int allSetsNodeLimit;
};
void printUnion(struct Node *rootPtr, struct allSets *setsPtr, int totalNodeNum,FILE *outputFile);
struct Node* unionFunc(struct Node *xPtr, struct Node *yPtr);
struct Node makeSet(struct Node *xPtr, int value);
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);
	}
	int nodeNumLimit=1000;
	struct allSets sets={realloc(NULL,nodeNumLimit*sizeof(struct Node)),nodeNumLimit};
	const int maxCharLength = 128;
	char aLine[maxCharLength],*numberStr;
	struct Node *tempNodeArr=realloc(NULL,nodeNumLimit*sizeof(struct Node));
	int totalNodeNum=0,number1,number2;
	while (fgets(aLine, sizeof aLine, inputFile) != NULL) //read a line
	{
		printf("Command: %s",aLine);
		fprintf(outputFile, "Command: %s",aLine);
		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);
				//need to exclude timing for following search routine
				int foundIndex1=0,foundIndex2=0,index,found1=0,found2=0;
				for(index=0;index<totalNodeNum;index++)
				{	
                                        if(((sets.nodeArr[index]).value)==number1){
						foundIndex1=index;
						found1=1;
						if(found2==1)
							break;
					}
					else if(((sets.nodeArr[index]).value)==number2){
						foundIndex2=index;
						found2=1;
						if(found1==1)
							break;
					}
                                }
				printf("Uniting 2 sets...\n");
				fprintf(outputFile, "Uniting 2 sets...\n");
				//start timing
				struct Node *rootPtr=unionFunc(&(sets.nodeArr[foundIndex1]),&(sets.nodeArr[foundIndex2]));
				//stops timing
				//print all nodes in the newly created union
				printf("Resulting union:\n");
				fprintf(outputFile, "Resulting union:\n");
				printUnion(rootPtr,&sets,totalNodeNum,outputFile);
				break;
			case 'm'://makeSet
				if(totalNodeNum+1>nodeNumLimit){
					printf("Info: Add additional memory for another 1000 nodes\n");
					fprintf(outputFile, "Info: Add additional memory for another 1000 nodes\n");
					nodeNumLimit+=1000;
					sets.allSetsNodeLimit=nodeNumLimit;
					tempNodeArr=realloc(tempNodeArr,nodeNumLimit*sizeof(struct Node));
					int i;
					for(i=0;i<nodeNumLimit;i++)
						tempNodeArr[i]=sets.nodeArr[i];
					sets.nodeArr=realloc(sets.nodeArr,nodeNumLimit*sizeof(struct Node));
					for(i=0;i<nodeNumLimit;i++)
						sets.nodeArr[i]=tempNodeArr[i];
				}
				printf("Making a new set with value: %d\n",number1);
				fprintf(outputFile, "Making a new set with value: %d\n",number1);
				//start timing
				struct Node *newNodePtr=realloc(NULL,sizeof(struct Node));
				sets.nodeArr[totalNodeNum]=makeSet(newNodePtr,number1);
				//stop timing
				totalNodeNum++;
				break;
			case 'f'://findSet
				printf("Trying to find the representative of node: %d\n",number1);
				fprintf(outputFile, "Trying to find the representative of node: %d\n",number1);
				//need to exclude timing for following search routine
				int foundIndex;
				for(foundIndex=0;foundIndex<totalNodeNum;foundIndex++)
					if(((sets.nodeArr[foundIndex]).value)==number1)
						break;//not sure i will maintain outside this loop to serve next line? A: seems yes
				//start timing
				struct Node *representativePtr=findSet(&(sets.nodeArr[foundIndex]));
				//stop timing
				printf("The representative found: %d\n",(representativePtr->value));
				fprintf(outputFile, "The representative found: %d\n",(representativePtr->value));
				break;
			default:
				printf("Fatal Error!\n");
				exit(1);
		}
		printf("\n");
		fprintf(outputFile, "\n");
	}
	printf("Finish processing all commands!\n");
	fprintf(outputFile,"Finish processing all commands!\n");
	fclose(inputFile);
	fclose(outputFile);
	return 0;
}
void printUnion(struct Node *rootPtr, struct allSets *setsPtr, int totalNodeNum,FILE *outputFile){
	int i;
	struct Node *nodePtr,*origNodePtr;
	printf("[ ");
	fprintf(outputFile, "[ ");
	for(i=0;i<totalNodeNum;i++){
		nodePtr=&(setsPtr->nodeArr)[i];
		origNodePtr=nodePtr;
		while(nodePtr!=(nodePtr->parentPtr)){
			nodePtr=(nodePtr->parentPtr);
		}
		if(nodePtr==rootPtr){
			printf("%d ",origNodePtr->value);
			fprintf(outputFile, "%d ",origNodePtr->value);
		}
	}
	printf("]\n");
	fprintf(outputFile, "]\n");
}
struct Node* unionFunc(struct Node *xPtr, struct Node *yPtr){
	return linkFunc(findSet(xPtr),findSet(yPtr));
}
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);
}