Population

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