Dependency(Improved)

A. Second edition
This is second edition of my dependency class.
B.The problem
The problem is going into details. Suppose you want to list all pre-requisite courses, how should you
do? You have to update the dependency link list whenever one node is defined. And continually check
to see if new definition of a node can be found. 
C.The idea of program
 
The manipulation of link list is a painful job! Suppose you want to merge two link list to make one
 
to contain the union set of all two nodes. How should you do?
 
The topological sort of this kind of dependency graph is actually use DFS and BFS. Originally I want
 
to avoid recursive call to improve efficiency. That is why I wrote two useless simple class--
 
SimpleStack and SimpleQueue. DFS is difficult to implement with a stack instead of recursion.
D.The major functions
C.Further improvement
 
#include <iostream>

using namespace std;

const int MaxListSize=40;

struct Link
{
	int data;
	Link* next;
};

struct Vertex
{
	int mark;
	char* str;
	Link* depend;
};

template<class T>
class SimpleStack
{
private:
	T lst[MaxListSize];
	int top;
public:
	SimpleStack(){ top=0;}
	void push(T& t){ lst[top++]=t;}
	T pop(){return lst[--top];}
	bool empty(){ return top==0;}
};

template<class T>
class SimpleQueue
{
private:
	T lst[MaxListSize];
	int head, tail;
public:
	SimpleQueue(){ head=tail=0;}
	void enqueue(T& t){ lst[tail++]=t; tail%=MaxListSize;}
	void dequeue(T& t) { t=lst[head++]; head%=MaxListSize;}
	int length(){return (tail-head)%MaxListSize;}
};


class Depend
{
private:
	Vertex* lst[MaxListSize];
	int size;
	void addNode(const char* str);
	void addSon(int index, int son);
	void DFS();
	void BFS();
	void initMark(bool useDFS);
	void printNode(int index);
	void doDFS(int index);
	void update(int index);
	void mergeLink(int i, int index);
	Link* insertLink(Link* father);
	bool find(Link* head, int key);
	void appendData(int index, int son);
public:
	Depend();
	~Depend();
	int getSize() { return size;}
	int find(const char* str);
	bool append(const char* str);
	bool remove(const char* str);
	void readFromFile(const char* fileName);
	void addDepend(int index, const char* str);
	void print();
	void topsort(bool useDFS=true);

};


int main()
{
	Depend D;
	D.readFromFile("c:\\depend.txt");
	D.print();
	cout<<"\nDFS topsort\n";
	D.topsort(true);
	cout<<"\nBFS topsort\n";
	D.topsort(false);
	cout<<endl;

	return 0;
}

void Depend::appendData(int index, int son)
{
	Link* target=lst[index]->depend;

	if (lst[index]->depend==NULL)
	{
		lst[index]->depend=new Link;
		target=lst[index]->depend;
		target->data=son;
		target->next=NULL;
		return;
	}

	//find the tail which is the last non-NULL node
	while (target->next!=NULL)
	{
		target=target->next;
	}
	target->next=new Link;
	target->next->data=son;
	target->next->next=NULL;
}

bool Depend::find(Link* head, int key)
{
	while (head!=NULL)
	{
		if (head->data==key)
		{
			return true;
		}
		head=head->next;
	}
	return false;
}


//head has at least one node
void Depend::mergeLink(int i, int index)
{
	Link* source=lst[index]->depend;
	Link* target=lst[i]->depend;

	while (source!=NULL)
	{
		if (!find(target, source->data))
		{
			appendData(i, source->data);
		}
		source=source->next;
	}
}

void Depend::update(int index)
{
	Link* temp;
	for (int i=0; i<size; i++)
	{
		temp=lst[i]->depend;
		if (find(temp, index))
		{
			mergeLink(i, index);
		}

	}
}

	
void Depend::printNode(int index)
{
	cout<<"no."<<index<<": "<<lst[index]->str<<"  ";
}

void Depend::initMark(bool useDFS)
{
	Link* temp;
	for (int i=0; i<size; i++)
	{
		lst[i]->mark=0;		
	
	}
	if (useDFS)
	{
		return;//do nothing;
	}
	for (i=0; i<size; i++)
	{
		temp=lst[i]->depend;
		while (temp!=NULL)
		{
			lst[temp->data]->mark++;
			temp=temp->next;
		}
	}
}

void Depend::doDFS(int index)
{
	Link* temp;

	if (lst[index]->mark!=0)
	{	
		return;
	}
	temp = lst[index]->depend;
	while (temp!=NULL)
	{
		doDFS(temp->data);
		temp=temp->next;
	}
	printNode(index);
	lst[index]->mark=1;
	
}

void Depend::DFS()
{
	for (int index=0; index<size; index++)
	{
		doDFS(index);		
	}
}

void Depend::BFS()
{
	SimpleQueue<int> Q;
	Link* temp;
	int index;
	for (int i=0; i<size; i++)
	{
		if (lst[i]->mark==0)
		{
			Q.enqueue(i);		
		}
	}
	while (Q.length()!=0)
	{
		Q.dequeue(index);
		printNode(index);
		temp=lst[index]->depend;
		while (temp!=NULL)
		{
			lst[temp->data]->mark--;
			if (lst[temp->data]->mark==0)
			{
				Q.enqueue(temp->data);
			}
			temp=temp->next;
		}
	}
}


void Depend::topsort(bool useDFS)
{
	initMark(useDFS);

	if (useDFS)
	{
		DFS();
	}
	else
	{
		BFS();
	}
}
	

void Depend::print()
{
	Link* ptr;
	for (int i=0; i<size; i++)
	{
		cout<<"node no."<<i<<":"<<lst[i]->str<<" : ";
		ptr=lst[i]->depend;
		while (ptr!=NULL)
		{
			cout<<lst[ptr->data]->str<<"  ";
			ptr=ptr->next;
		}
		cout<<endl;
	}
}

void Depend::addSon(int index, int son)
{
	if (!find(lst[index]->depend, son))
	{
		appendData(index, son);
	}
	update(son);
}

void Depend::addDepend(int index, const char* str)
{
	int pos= find(str);
	Link* ptr;
	if (pos==-1)
	{
		append(str);
		pos=size-1;//size++
		addSon(index, pos);
	}
	else
	{
		addSon(index, pos);
		ptr= lst[pos]->depend;
		while (ptr!=NULL)
		{
			addSon(index, ptr->data);
			ptr=ptr->next;
		} 
	}
}

void Depend::addNode(const char* str)
{
	char buffer[100];
	int index;
	strcpy(buffer, str);
	char* ptr=buffer;
	ptr=strtok(ptr, " :\n");

	index=find(ptr);
	if (index==-1)
	{
		append(ptr);
		index=size-1;
	}
	ptr=NULL;
	ptr=strtok(ptr, " :\n");
	while (ptr!=NULL)
	{
		addDepend(index, ptr);		
		ptr=NULL;
		ptr=strtok(ptr, " :\n");
	}
	update(index);
}


void Depend::readFromFile(const char* fileName)
{
	FILE* stream;
	char buffer[100];
	if ((stream=fopen(fileName, "r"))==NULL)
	{
		cout<<"fail to read file "<<fileName<<endl;
		return;
	}
	while (fgets(buffer, 100, stream)!=NULL)
	{
		addNode(buffer);
	}
	fclose(stream);
}

Depend::~Depend()
{
	for (int i=0; i<size; i++)
	{
		//delete [] lst[i]->str;//do we need????
		delete lst[i];
	}
}

Depend::Depend()
{
	size=0;
}

int Depend::find(const char* str)
{
	for (int i=0; i<size; i++)
	{
		if (strcmp(str, lst[i]->str)==0)
		{
			return i;
		}
	}
	return -1;
}


bool Depend::append(const char* str)
{
	if (find(str)!=-1)
	{
		return false;
	}	
	lst[size]=new Vertex;
	lst[size]->mark=0;
	lst[size]->depend=NULL;
	lst[size]->str=new char[strlen(str)+1];
	strcpy(lst[size]->str, str);
	size++;
	return true;
}

bool Depend::remove(const char* str)
{
	int index = find(str);
	if (index==-1)
	{
		return false;
	}
	delete [] lst[index]->str;
	lst[index]->str=NULL;
	delete lst[index];
	size--;
	for (int i=index; i<size; i++)
	{
		lst[i]=lst[i+1];
	}
	return true;
}



Here is the result:(Note DFS and BFS gives almost opposite result.)
node no.0:354 : 352 239 249 238 248
node no.1:352 : 239 249 238 248
node no.2:442 : 229 335 352 239 249 228 248 238
node no.3:229 : 228 248
node no.4:335 : 239 238 249 248
node no.5:465 : 335 352 239 249 238 248
node no.6:472 : 352 239 249 238 248
node no.7:473 : 352 239 249 238 248
node no.8:353 : 352 239 249 238 248
node no.9:346 : 229 352 239 249 228 248 238
node no.10:326 : 346 229 352 239 249 228 248 238
node no.11:239 : 238
node no.12:249 : 238 248
node no.13:228 :
node no.14:248 :
node no.15:238 :
node no.16:348 : 249 238 248

DFS topsort
no.15: 238 no.11: 239 no.14: 248 no.12: 249 no.1: 352 no.0: 354 no.13: 228 no.3: 229 no.4: 3
35 no.2: 442 no.5: 465 no.6: 472 no.7: 473 no.8: 353 no.9: 346 no.10: 326 no.16: 348
BFS topsort
no.0: 354 no.2: 442 no.5: 465 no.6: 472 no.7: 473 no.8: 353 no.10: 326 no.16: 348 no.4: 335
no.9: 346 no.3: 229 no.1: 352 no.13: 228 no.11: 239 no.12: 249 no.15: 238 no.14: 248
Press any key to continue
Here is the input file:(actually these are courses that I am interested in.)

354 : 352
442 : 229 335 352
465 : 335 352
472 : 352
473 : 352
353 : 352
346 : 229 352
326 : 346
352 : 239 249
229 : 228 248
239 : 238
249 : 238 248
348 : 249
335 : 239 249



	


                                 back.gif (341 bytes)       up.gif (335 bytes)         next.gif (337 bytes)