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