Commits

Eric Chen  committed 4a33a83

(1)this version is more flexible in memory allocation.
(2)this version preallocates memory for 100000 nodes, and dfsPrint() was
implemented to assist printUnion(). Additionally, a different struct
type was implemented to be used in dfsPrint().
(3)this python program can generate commands automatically(but takes
hours to generate 100000 commands).
(4)test case 1 that I wrote manually.
(5)test case 2 that I wrote manually.
(6),(7) nothing

  • Participants
  • Parent commits 52bf23e
  • Branches dev

Comments (0)

Files changed (7)

File src/NCKUAlg/ProgHW4/dynamicTable/dynamic.c

 /*
  * Copyright (C) 2012 Eric Chen(G+ page:HencriceFOSS, gmail:hencrice+FOSS+AlgNCKU@gmail.com)
- * This file is a part of AlgNCKU.
+ * This file is a part of introtoalgorithm3ed.
  *
- * AlgNCKU is a free software; you can redistribute it and/or modify it under the terms of the GNU General
+ * 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.
  *

File src/NCKUAlg/ProgHW4/knapsack01/knapsack01.c

 /*
  * Copyright (C) 2012 Eric Chen(G+ page:HencriceFOSS, gmail:hencrice+FOSS+HW4@gmail.com)
- * This file is a part of HW4.
+ * This file is a part of introtoalgorithm3ed.
  *
- * HW4 is a free software; you can redistribute it and/or modify it under the terms of the GNU General
+ * 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.
  *

File src/NCKUAlg/ProgHW5/disjointSetForest_v1.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>
+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);
+}

File src/NCKUAlg/ProgHW5/disjointSetForest_v2.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>
+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);
+	}
+	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 totalNodeNum=0,number1,number2,timesCmdUExec=0,timesCmdMExec=0,timesCmdFExec=0;
+	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);
+				printf("Uniting 2 sets...\n");
+				fprintf(outputFile, "Uniting 2 sets...\n");
+				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);
+				//test
+//				printf("nodeInfoArr[%d].numOfChildren=%d\n",1,sets.nodeInfoArr[1].numOfChildren);
+				//test
+				//print all nodes in the newly created union
+				printf("Resulting union:\n");
+				fprintf(outputFile, "Resulting union:\n");
+				printUnion(rootPtr,&sets,nodeNumLimit,outputFile);
+				timesCmdUExec++;
+				break;
+			case 'm'://makeSet
+				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[number1-1]=makeSet(newNodePtr,number1);
+				//stop timing
+				struct additionalInfoForPrintUnionPerNode *newNodeInfoPtr=realloc(NULL,sizeof(struct additionalInfoForPrintUnionPerNode));
+				sets.nodeInfoArr[number1-1]=makeSetUpdateInfo(newNodeInfoPtr);
+				totalNodeNum++;
+				timesCmdMExec++;
+				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);
+				//start timing
+				struct Node *representativePtr=findSet(&(sets.nodeArr[number1-1]));
+				//stop timing
+				printf("The representative found: %d\n",(representativePtr->value));
+				fprintf(outputFile, "The representative found: %d\n",(representativePtr->value));
+				timesCmdFExec++;
+				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");
+	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, total memory usage=%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, total memory usage=%ld bytes\n",sizeof(struct Node),timesCmdMExec,timesCmdMExec*sizeof(struct Node));
+	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);
+}

File src/NCKUAlg/ProgHW5/genCommands.py

+#! /usr/bin/python2.7
+# -*- coding: UTF-8 -*-
+'''
+Copyright (C) 2011 Eric Chen(G+ page:HencriceFOSS, gmail:hencrice+FOSS+introtoalgorithm3ed@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
+'''
+from random import randint,choice #10**6
+possibleCommands=('m','f','u')
+nodesAlreadyCreated=set() #add remove
+numOfCmdGonnaGenerate=10**6
+with open('./testLong.txt', 'w') as cmdFile:
+    for i in xrange(numOfCmdGonnaGenerate):
+        cmd=choice(possibleCommands)
+        if cmd=='m':
+            newValue=randint(1,numOfCmdGonnaGenerate)
+            while newValue in nodesAlreadyCreated:
+                newValue=randint(1,numOfCmdGonnaGenerate)
+            cmdFile.write('{0} {1}\n'.format(cmd,newValue))
+            nodesAlreadyCreated.add(newValue)
+        elif cmd=='f' and len(nodesAlreadyCreated)>0:
+            valWantToFind=choice(tuple(nodesAlreadyCreated))
+            cmdFile.write('{0} {1}\n'.format(cmd,valWantToFind))
+        elif len(nodesAlreadyCreated)>1:
+            value1=choice(tuple(nodesAlreadyCreated))
+            nodesAlreadyCreated.remove(value1)
+            value2=choice(tuple(nodesAlreadyCreated))
+            nodesAlreadyCreated.add(value1)
+            cmdFile.write('{0} {1} {2}\n'.format(cmd,value1,value2))

File src/NCKUAlg/ProgHW5/test1.txt

+m 1
+f 1
+m 2
+f 2
+m 3
+f 3
+m 4
+f 4
+u 1 2
+f 1
+u 3 4
+f 3
+u 1 4
+f 2

File src/NCKUAlg/ProgHW5/test2.txt

+m 7
+m 1
+m 9
+u 7 1
+f 1
+u 7 9
+f 9
+m 57
+u 7 57
+f 57