Topic: Help! Shortest Path
Author: g8174011@cchp01.cc.cycu.edu.tw (Y.M.lin)
Date: Fri, 20 May 1994 08:00:35 GMT Raw View
Hi!
I have some trouble in this program. When it run many times, the memory
was not enough. The "new" and "delete" seem not wrong. It can run in the
Compact model but not in Large or Huge. Does any one can help me? Thanks.
This program is to find the shortest path in network. As in main(),
give the network name, start node (and excepted node(s)), to find the
next node in shortest path.
///////////////////////////////////////////////////////////////////////////////
// pm.cpp //
///////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
#include <stddef.h>
template <class T> class SNode
{
public:
SNode(T *a);
SNode<T> *Next;
T *Data;
};
template <class T> SNode<T>::SNode(T *a)
{
Next = 0;
Data = a;
}
template <class T> class SList
{
friend PartManager;//for test!!
protected:
SNode<T> *Tail;
SNode<T> *Flag;
public:
SList();
void Put(T *a);
void NewGet();
T *Get();
};
template <class T> SList<T>::SList()
{
Tail = 0;
Flag = 0;
}
template <class T>void SList<T>::Put(T *a)
{
SNode<T> *t = new SNode<T>(a);
if(!t)
{
printf ("SList::Put Error ");
return ;
}
if(Tail)
{
t->Next = Tail->Next;
Tail=Tail->Next = t;
}
else
{
Tail = t;
Tail->Next= Tail;
}
}
template <class T> void SList<T>::NewGet()
{
Flag=0;
}
template <class T> T *SList<T>::Get()
{
if(!Tail)
return 0;
if(!Flag)
{
Flag = Tail->Next;
return Flag->Data;
}
else if (Flag==Tail)
{
Flag=0;
return 0;
}
else
{
Flag = Flag->Next;
return Flag->Data;
}
}
template<class T> class Stack
{
SNode<T> *Tail;
void Delete();
public:
Stack(void);
~Stack(void);
void Push(T *data);
T *Pop(void);
};
template<class T>Stack<T>::Stack(void)
{
Tail = 0;
}
template<class T>Stack<T>::~Stack(void)
{
while(Tail) Delete();
}
template<class T>void Stack<T>::Push(T *data)
{
SNode<T> *p = new SNode<T>(data);
if (!p)
{
printf("Memory is not enough Stack::Push\n");
return;
}
if(Tail)
{
p->Next = Tail->Next;
Tail->Next = p;
}
else
{
Tail = p;
Tail->Next = Tail;
}
}
template<class T>void Stack<T>::Delete()
{
if(Tail==Tail->Next)
{
Tail=0;
delete Tail;
}
else
{
SNode<T> *p = Tail->Next;
Tail->Next = p->Next;
delete p;
}
}
template<class T>T *Stack<T>::Pop(void)
{
if(Tail)
{
T *d = Tail->Next->Data;
Delete();
return d;
}
return 0;
}
template<class T> class DNode
{
public:
DNode<T> *Pre;
DNode<T> *Next;
DNode(T *data);
T *Data;
};
template<class T> class InList
{
protected:
DNode<T> *Head;
DNode<T> *Tail;
public:
InList();
void Put(T *data);
T *Get();
void Delete();
};
template<class T> class LinkList: virtual public InList<T>
{
public:
void Delete();
};
template <class T> class SSList: virtual public InList<T>
{
void SS(DNode<T> *n);
public:
void Put(T *data);
};
template<class T> class SortList: public LinkList<T>, public SSList<T>{};
template<class T>DNode<T>::DNode(T *data)
{
Pre = 0;
Next = 0;
Data = data;
}
template<class T>InList<T>::InList()
{
Head = 0;
Tail = 0;
}
template<class T>void InList<T>::Put(T *data)
{
DNode<T> *p = new DNode<T>(data);
if (!p)
{
printf("Memory is not enough from InList::Put\n");
return;
}
if (!Tail) Head = Tail = p;
else
{
Tail->Next = p;
p->Pre = Tail;
Tail = p;
}
}
template<class T>T *InList<T>::Get()
{
if(Head) return Head->Data;
return 0;
}
template<class T>void InList<T>::Delete()
{
if(!Head) printf("Error InList::delete()");
else if(Head==Tail)
{
Head=0;
Tail=0;
delete Head;
}
else
{
DNode<T> *p;
p = Head;
Head = Head->Next;
Head->Pre= 0;
delete p;
}
}
template<class T>void LinkList<T>::Delete()
{
if(!Head) printf("Error LinkLIst::delete()");
else
{
DNode<T> *p;
p = Head;
Head = Head->Next;
if (Head)Head->Pre= 0;
delete p->Data;
delete p;
}
}
template<class T> void SSList<T>::Put(T *data)
{
InList<T>::Put(data);
if(Head != Tail && Tail->Data->Get() < Tail->Pre->Data->Get())
SS(Tail);
}
template <class T>void SSList<T>::SS(DNode<T> *n)
{
if(n==Tail)
{
if(n->Pre==Head)
{
n->Next = n->Pre;
n->Pre->Pre = n;
n->Pre = 0;
n->Next->Next = 0;
Head = n;
Tail = n->Next;
}
else
{
n->Pre = n->Pre->Pre;
n->Pre->Next->Next = 0;
n->Pre->Next->Pre = n;
n->Next = n->Pre->Next;
n->Pre->Next = n;
Tail = n->Next;
}
}
else
{
if(n->Pre==Head)
{
n->Pre->Next = n->Next;
n->Next->Pre = n->Pre;
n->Next = n->Pre;
n->Next->Pre = n;
n->Pre = 0;
Head = n;
}
else
{
n->Pre = n->Pre->Pre;
n->Next->Pre = n->Pre->Next;
n->Next->Pre->Pre = n;
n->Pre->Next->Next = n->Next;
n->Next = n->Pre->Next;
n->Pre->Next = n;
}
}
if(n->Pre && n->Data->Get() < n->Pre->Data->Get())
SS(n);
}
#define DATAFILE "pm.dat"
class Process
{
public:
int ProcessName;
int MachineType;
float MachineTime;
SList<int> *Next; // input Process Name
Process(void);
};
class Candidate
{
public:
float Time;
float Get(void);
Process *Data;
Candidate(Process *data);
};
class PartData: public SList<Process>
{
friend PartManager;
int PartType;
int PreProcess(Process *New, Process *Old);
Process *Address(int pn);
public:
Process* NextProcess(int start, int ex1, int ex2, int ex3, int ex4, int ex5);
PartData(int i);
};
class PartManager
{
FILE *PartFile;
SList<PartData> *Part;
public:
Process* NextProcess(int type, int start, int except1 = 999,
int except2 = 999,
int except3 = 999,
int except4 = 999,
int except5 = 999);
PartManager(void);
};
Process::Process(void)
{
Next = new SList<int>;
}
float Candidate::Get(void)
{
return Time;
}
Candidate::Candidate(Process *data)
{
Data = data;
Time = Data->MachineTime;
}
PartData::PartData(int i)
{
PartType = i;
}
int PartData::PreProcess(Process *New, Process *Old)
{
New->Next->NewGet();
int *p;
while((p=New->Next->Get()) !=0)
if(*p == Old->ProcessName)
return 1;
return 0;
}
PartManager::PartManager(void)
{
Part = new SList<PartData>;
int processNumber, partTypeNumber;
int processName, machineType, nexts, nextProcessName;
float machineTime;
if( (PartFile = fopen(DATAFILE, "r")) == NULL )
{
printf("Errot on opening file");
}
fscanf(PartFile, "%d", &partTypeNumber );
for(int i = 0; i<partTypeNumber; i++ )
{
PartData *p = new PartData(i);
fscanf(PartFile, "%d", &processNumber );
for(int j = 0; j<processNumber; j++ )
{
Process *e = new Process;
fscanf(PartFile, "%d %d %f %d", &processName, &machineType, &machineTime,&nexts);
e->ProcessName = processName;
e->MachineType = machineType;
e->MachineTime = machineTime;
if(nexts>0)
{
for(int k = 0;k<nexts;k++)
{
fscanf( PartFile,"%d", &nextProcessName);
int *q = new int;
*q = nextProcessName;
e->Next->Put(q);
}
}
p->Put(e);
}
Part->Put(p);
}
fclose( PartFile );
}
Process* PartManager::NextProcess(int type, int start, int except1,
int except2, int except3, int except4, int except5)
{
PartData *p;
Part->NewGet();
p=Part->Get();
while((p->PartType)!=type)
p=Part->Get();
return p->NextProcess(start, except1, except2, except3, except4, except5);
}
Process* PartData::Address(int pn)
{
NewGet();
Process *p;
while((p=Get())!=0)
if(p->ProcessName==pn)
return p;
return 0;
}
Process* PartData::NextProcess(int start,
int ex1, int ex2, int ex3, int ex4, int ex5)
{
SortList<Candidate> *MinTime = new SortList<Candidate>;
Stack<Process> *Record = new Stack<Process>;
Process *ThisProcess;
Process *Selected ;
int k1, k2;
k1 = 0;
k2 = 0;
int *Flag;
ThisProcess = Address(start);
Candidate *TotalTime ;
TotalTime = new Candidate(ThisProcess);
MinTime->Put(TotalTime);
while(ThisProcess->MachineType<999)
{
ThisProcess->Next->NewGet();
Flag = ThisProcess->Next->Get();
while(Flag)
{
if(*Flag != ex1 && *Flag != ex2 && *Flag != ex3 && *Flag != ex4 && *Flag != ex5)
{
Process *NextProcess;
NextProcess = Address(*Flag);
TotalTime = new Candidate(NextProcess);
TotalTime->Time += MinTime->Get()->Time;
MinTime->Put(TotalTime);
k1 = 1;
k2 = 1;
}
Flag = ThisProcess->Next->Get();
}
if(k1 == 1)
{
Record->Push(MinTime->Get()->Data);
MinTime->Delete();
ThisProcess = MinTime->Get()->Data;
k1 = 0;
}
else break;
}
if (k2==0)
{
delete MinTime;
delete Record;
printf(" NO PATH !! "); //test !!
return 0;
}
ThisProcess = Record->Pop();
Selected = ThisProcess;
while(ThisProcess)
{
ThisProcess = Record->Pop();
if(PreProcess(ThisProcess, Selected)>0 && ThisProcess->ProcessName!=start)
Selected = ThisProcess;
}
delete MinTime;
delete Record;
return Selected;
}
void main(void)
{
PartManager *Paul = new PartManager;
for (int i=0;i<30000;i++)
{
printf("NextProccess 0: %d\n",Paul->NextProcess(0,1)->ProcessName);
printf("NextProccess 1: %d\n",Paul->NextProcess(1,4)->ProcessName);
printf("NextProccess 2: %d\n",Paul->NextProcess(2,4)->ProcessName);
printf("NextProccess 3: %d\n",Paul->NextProcess(3,1)->ProcessName);
printf("NextProccess 4: %d\n",Paul->NextProcess(4,3)->ProcessName);
printf("NextProccess 5: %d\n",Paul->NextProcess(5,5)->ProcessName);
printf("NextProccess a0: %d\n",Paul->NextProcess(0,1,2)->ProcessName);
printf("NextProccess a1: %d\n",Paul->NextProcess(1,4,8)->ProcessName);
printf("NextProccess a2: %d\n",Paul->NextProcess(2,4,8)->ProcessName);
printf("NextProccess a3: %d\n",Paul->NextProcess(3,1,2)->ProcessName);
printf("NextProccess a4: %d\n",Paul->NextProcess(4,3,9)->ProcessName);
printf("NextProccess a5: %d\n",Paul->NextProcess(5,5,10)->ProcessName);
}
delete Paul;
}
///////////////////////////////////////////////////////////////////////////////
// pm.dat //
///////////////////////////////////////////////////////////////////////////////
6
10
1 0 0. 2 2 3
2 1 7.1 2 4 5
3 5 4.3 1 6
4 4 4.3 1 8
5 7 2.2 1 7
6 8 7.2 2 7 9
7 2 4.3 1 8
8 3 2.1 1 10
9 2 3.2 1 10
10 999 0. 0
14
1 0 0. 3 2 3 4
2 4 3.2 2 5 6
3 2 4.3 1 7
4 3 2.1 1 8
5 8 4.4 1 11
6 2 3.9 1 9
7 7 7.8 2 9 10
8 4 2.1 1 10
9 5 5.6 1 12
10 7 4.3 1 13
11 2 7.9 1 14
12 3 2.1 1 14
13 3 3.4 1 14
14 999 0. 0
17
1 0 0. 2 2 3
2 1 3.4 1 4
3 3 7.3 3 5 6 7
4 2 9.2 2 8 9
5 4 4.1 1 9
6 2 2.1 1 10
7 7 5.6 1 11
8 6 6.7 1 12
9 7 5.1 1 13
10 4 4.3 1 13
11 8 7.2 1 14
12 7 2.1 1 17
13 5 4.3 1 12
14 6 5.7 2 15 16
15 2 4.3 1 17
16 1 6.6 1 17
17 999 0. 0
15
1 0 0. 2 2 3
2 8 3.7 2 4 5
3 2 9.6 1 7
4 4 4.3 1 6
5 3 5.2 2 8 9
6 2 6.7 2 10 11
7 7 8.2 2 11 12
8 4 2.3 1 10
9 7 4.3 1 13
10 6 6.3 1 13
11 5 2.1 1 13
12 3 9.6 1 14
13 1 4.3 1 15
14 6 1.2 1 15
15 999 0. 0
20
1 0 0. 4 2 3 4 5
2 4 2.3 2 6 7
3 3 1.4 2 8 9
4 8 3.2 1 10
5 7 1.7 1 10
6 3 7.8 1 11
7 2 9.2 1 11
8 4 5.4 2 12 13
9 7 5.6 1 14
10 2 3.7 1 14
11 6 6.4 2 15 16
12 2 2.7 1 17
13 5 3.8 1 17
14 3 4.2 1 18
15 5 3.3 1 19
16 8 4.3 1 19
17 1 9.6 1 20
18 4 5.6 1 20
19 1 6.5 1 20
20 999 0. 0
// end
Lin, Yi-Ming
g8174011@cchp01.cc.cycu.edu.tw