Population

Dependency

    A. First edition

    This is first edition of my dependency class.

    B.The problem

    Can you imagine what is a dependency problem?

    1. Suppose you have a sequence of courses to take and each course has 0 or more pre-requisite

    courses. I want you to list all dependency relations.

    2. Suppose you are writing a compiler, one of basic part is how to solve the forward references.

    That is A is defined by B, B is defined by C... So, how to book keep the dependency relations.

    3. Suppose you are writing a file to implement the functionality of "makefile". You need to establish

    a dependency tree of all files.

C.The idea of program
กก

    It is actually a kind of edge list implementation of graph. Each node of list is actually a struct

    which has a string as data, a link list of other strings which depends on it.

    D.The major functions

    C.Further improvement

    กก

    #include <iostream>

    using namespace std;

    const int MaxListSize=40;

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

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

    class Depend
    {
    private:
    	Vertex* lst[MaxListSize];
    	int size;
    	void addNode(const char* str);
    	void addSon(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();

    };

    int main()
    {
    	Depend D;
    	D.readFromFile("c:\\depend.txt");
    	D.print();
    	return 0;
    }

    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)
    {
    	Link* ptr;
    	ptr= lst[index]->depend;
    	if (ptr==NULL)
    	{
    		ptr=new Link;
    		ptr->data= son;
    		ptr->next=NULL;
    		lst[index]->depend=ptr;
    		return;
    	}
    	while (ptr->next!=NULL)
    	{
    		if (ptr->next->data==son)
    		{
    			return;//already there
    		}
    		ptr=ptr->next;
    	}
    	//add new link
    	ptr->next= new Link;
    	ptr->next->data=son;
    	ptr->next->next=NULL;
    }

    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");
    	}
    }

    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;
    		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]->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:

    node no.0:238 : 228
    node no.1:228 :
    node no.2:229 : 228 248
    node no.3:248 :
    node no.4:239 : 238 228
    node no.5:249 : 238 228 248
    node no.6:352 : 239 238 228 249 248
    node no.7:348 : 249 238 228 248
    node no.8:335 : 239 238 228 249 248
    Press any key to continue

    Here is the input file:

    238 : 228
    229 : 228 248
    239 : 238
    249 : 238 248
    352 : 239 249
    348 : 249
    335 : 239 249