Dependency(Improved)
A. Second edition
This is second edition of my dependency class.
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.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