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. 

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