Prim --A greedy algorithm in graph
A.First Edition
This is actually another application of my BFS class, or you can call it fifth edition of BFS class, whatever.
The base framework remains basically same except that I create a new class which inherited from BFS class. Also
I simplified the Matrix class and make a light-weight "BasicMatrix" class. The function is mainly for inputting
and outputting from files. The only two thing I need are "readFromFile" and "items" methods. And I make a static
object inside the new "Prim" class. The Prim class override several virtual method from BFS. The other significant
changes in BFS class is that I make some more virtual functions at different stages, like onBeforeCount, onNextNode,
onNextLevel etc. These particular functions are particular moments during searching at which programmer need to
write their own methods. These are similar in Delphi.
A minimum spanning tree can be obtained by Prim algorithm, it creates a root among the connected graph by choosing
the smallest edge. Then every time it adds a minimum edge into that tree so that there is no circuits created by
the edge. (This is redundant description of tree as tree is a graph with no circuit.)
No matter how complicated a problem may become, we can divide and conquer it by counting! And breadth-first-search
is one of the simplest way to do it. This is an application of my BFS class which allow user to override several
key method to do the BFS. In this case, user need to override two method: createSon() and validateOption().
The most important part is how to determine the smallest edge outside the tree which will not create a circuit after
being add into tree. I implement this awkwardly from a long way.
Firstly please take notice that the matrix is not adjacency matrix, it is incidence matrix because the former
one simply won't work! The key element in algorithm is the edge not the vertices!
Secondly an edge would only connects with exactly two vertices and one vertices may connect with any number of
edges. A big, big idea! In order to simplify the job, I create two array of bool to hold edges (the options) and
the vertices. They are choiceTaken, and vertexOption. The first one is in BFS class as I thought it could be a
general way for programmer to record whatever he had chosen from options. The second one is specific for Prim class.
Third idea is the trackBack function which is add into BFS class along with dataRec array. As it should be a general
method when programmer want to backtrack the node in the tree. and it should be standardized.
1. void BFS::trackBack()
This is a new method in BFS class to standardize the backtrack of nodes in tree and they are stored in dataRec[].
2.void Prim::findSmallest()
This is one of heart of Prim. It was invoked whenever a new node is going to be checked in method onNextNode.
At the very beginning, only the smallest edge should be selected.
Then it should first store all vertices into vertexOption. Then for all edges not in the tree and has a vertex in
the tree, it compare and find the smallest edge. That is it!
3. bool Prim::isTheOne(int sonData)
This is another heart of Prim. At very beginning, the correct choice is the smallest edge. Then in successive
level, it should find the edges outside tree and doesn't have both vertex in tree, but only one vertex in tree and
has the value of edge exactly same as smallest. (A lot of conditions, right?)
C.Further improvement
1. The input is really a pain! The most bugs are coming from the huge Matrix.
#include <iostream>
#include <cmath>
#include <fstream>
using namespace std;
const int MaxSonCount =10;
const int MaxLevel = 24;
const int MaxOptionCount = 24;
const int MaxRow = 24;
const int MaxCol = 24;
const double LIMIT = 0.01;
const int INFINITE =1000;
enum VertexName
{A_B,B_C,C_D,A_E,B_F,C_G,D_H,E_F,F_G,G_H,E_I,F_J,G_K,H_L,I_J,J_K,K_L,I_M,J_N,K_O,
L_P,M_N,N_O,O_P};
char* VertexString[24] =
{"ab","bc","cd","ae","bf","cg","dh","ef","fg","gh","ei","fj","gk",
"hl","ij","jk","kl","im","jn","ko","lp","mn","no","op"};
int VertexOption[24] = {A_B,B_C,C_D,A_E,B_F,C_G,D_H,E_F,F_G,G_H,E_I,F_J,G_K,H_L,I_J,
J_K,K_L,I_M,J_N,K_O,L_P,M_N,N_O,O_P};
class BasicMatrix
{
private:
int rowNum;
int colNum;
double lst[MaxRow][MaxCol];
protected:
public:
BasicMatrix();
int row() const {return rowNum;}
int col() const {return colNum;}
void setRow(const int newRow) { rowNum = newRow;}
void setCol(const int newCol) { colNum = newCol;}
void display(bool displayNumber= false);
double& items(int r, int c);
void initialize();
void readFromFile(const char* fileName);
};
class BFS
{
protected:
static BFS *root;
static int level;
static int optionArray[MaxOptionCount];
static int optionCount;
static int maxLevel;
static int dataRec[MaxLevel];
static bool choiceTaken[MaxOptionCount];
int depth;
BFS* parent;
BFS* sonArray[MaxSonCount];
int data;
int sonCount;
int sonIndex;
void addSon(int sonData);
BFS* findBrother();
BFS* findUncle();
bool hasBrother();
BFS* nextBrother();
BFS* diving();
void trackBack();
void initialize(BFS* now);
bool touchDown();
bool canDive();
bool generate();
void traverse();
void setMaxLevel(int max) { maxLevel = max;}
void assignString(char** nameString);
virtual BFS* createSon();
virtual bool lastChance();
virtual void doGenerate();
virtual bool validateOption(int sonData);
virtual void onVisit(int& counter);
virtual void onBeforeCount();
virtual void onNextLevel();
virtual void onNextNode();
public:
int getData(){return data;}
BFS* getParent() { return parent;}
void setOptionArray(int* array, int arraySize);
void beginCount(int max);
};
int BFS::level = 0;
BFS* BFS::root;
int BFS::dataRec[MaxLevel];
int BFS::optionArray[MaxOptionCount] = {0};
int BFS::optionCount = 0;
int BFS::maxLevel = 0;
bool BFS::choiceTaken[MaxOptionCount];
class Prim: public BFS
{
private:
static bool vertexOption[MaxRow];
static BasicMatrix Mx;
static int smallest;
void findSmallest();
void onBeforeCount();
bool isTheOne(int sonData);
protected:
BFS* createSon();
bool validateOption(int sonData);
void onNextLevel();
void onNextNode();
void onVisit(int& counter);
public:
void readFromFile(char* fileName);
void display();
};
int Prim::smallest = 0;
BasicMatrix Prim::Mx;
bool Prim::vertexOption[MaxRow]={false};
int main()
{
Prim thePrim;
thePrim.readFromFile("c:\\nickedge.txt");
thePrim.display();
thePrim.setOptionArray(VertexOption, 24);
thePrim.beginCount(16);
return 0;
}
void Prim::onBeforeCount()
{
// findSmallest();
}
void Prim::display()
{
Mx.display();
}
void Prim::onNextNode()
{
findSmallest();//choiceTaken is useless here
}
void Prim::onVisit(int& counter)
{
int total=0;
cout<<"now it is:"<<++counter;
assignString(VertexString);
trackBack();
for (int i=0; i<depth; i++)
{
for (int r=0; r<Mx.row(); r++)
{
if (vertexOption[r]&&Mx.items(r, dataRec[i])<INFINITE)
{
total+= Mx.items(r, dataRec[i]);
break;
}
}
}
cout<<" total="<<total<<endl;
}
bool Prim::isTheOne(int sonData)
{
bool theSmall=false;
bool inPath=false;
if (depth==0) //first time
{
for (int r=0; r<Mx.row(); r++)
{
if (Mx.items(r, sonData)==smallest)
{
return true;
}
}
return false;
}
//trackBack();
if (choiceTaken[sonData])
{
return false;//
}
for (int r=0; r< Mx.row(); r++)
{
if (vertexOption[r])
{
if (Mx.items(r, sonData)!=INFINITE)
{
if (!inPath)
{
inPath = true;//find the candidate
}
else
{
return false;
}
if (Mx.items(r, sonData)==smallest)
{
theSmall= true;
}
}
}
}
return theSmall;
}
void Prim::findSmallest()
{
smallest = INFINITE;
if (level==0)
{
for (int r=0;r<Mx.row(); r++)
{
for (int c=0;c<Mx.col(); c++)
{
if (Mx.items(r,c)<smallest)
{
smallest = Mx.items(r,c);
}
}
}
}
else
{
trackBack();
for (int r=0; r<Mx.row(); r++)
{
vertexOption[r] = false;
}
for (int i=0; i<depth; i++)
{
for (int r=0; r<Mx.row(); r++)
{
if (Mx.items(r, dataRec[i])!= INFINITE)
{
vertexOption[r] = true;
}
}
}
for (r=0; r<Mx.row(); r++)
{
for (int c=0; c<Mx.col(); c++)
{
if (!choiceTaken[c]&&vertexOption[r]&&Mx.items(r, c)<smallest)
{
smallest = Mx.items(r, c);
}
}
}
}
}
void Prim::onNextLevel()
{
//findSmallest();
}
bool Prim::validateOption(int sonData)
{
return isTheOne(sonData);
}
BFS* Prim::createSon()
{
BFS* ptr;
ptr = new Prim;
return ptr;
}
void Prim::readFromFile(char* fileName)
{
Mx.readFromFile(fileName);
}
void BFS::setOptionArray(int *array, int arraySize)
{
optionCount = arraySize;
for (int i=0; i< optionCount; i++)
{
optionArray[i] = array[i];
}
}
BFS* BFS::createSon()
{
BFS* ptr = new BFS;
return ptr;
}
void BFS::onBeforeCount()
{
}
void BFS::trackBack()
{
for (int i=0; i<optionCount; i++)
{
choiceTaken[i]=false;
}
BFS* ptr = this;
while(ptr!=NULL)
{
if (ptr->parent==NULL)
{
break;
}
dataRec[ptr->depth-1] = ptr->data;
choiceTaken[ptr->data]= true;
ptr = ptr->parent;
}
}
void BFS::assignString(char** nameString)
{
int temp[MaxLevel] = {0};
BFS* ptr = this;
while (ptr->parent!=NULL)
{
temp[ptr->depth-1] = ptr->data;
ptr = ptr->parent;
}
cout<<" The route is:";
for (int i=0; i<depth; i++)//depth is one more than level!!!!!!
{
cout<<nameString[temp[i]]<<", ";
}
cout<<endl;
}
void BFS::onNextLevel()
{
}
void BFS::onVisit(int& counter)
{
cout<<"now it is:"<<++counter;
assignString(VertexString);
}
bool BFS::validateOption(int sonData)
{
return true;
}
void BFS::doGenerate()
{
for (int i=0; i<optionCount; i++)
{
if (validateOption(optionArray[i]))
{
addSon(optionArray[i]);
}
}
}
bool BFS::lastChance()
{
return level==maxLevel-1;
}
void BFS::traverse()
{
int counter=0;
BFS* ptr= root;
while (ptr!=NULL)
{
while(ptr->canDive())
{
ptr= ptr->sonArray[0];
}
ptr->onVisit(counter);
if (ptr->hasBrother())
{
ptr= ptr->nextBrother();
}
else
{
ptr=ptr->findUncle();
}
}
cout<<"The total number is :"<<counter<<endl;
}
void BFS::beginCount(int max)
{
setMaxLevel(max);
initialize(this);
onBeforeCount();
while (generate())
{
if (!lastChance()) //true to keep go on
{
onNextLevel();
level++;
}
else
{
break;
}
}
traverse();
}
bool BFS::generate()
{
BFS* ptr= this;
ptr = root->diving();
if (ptr==NULL)
{
return false;
}
while (ptr!=NULL)
{
ptr->onNextNode();
ptr->doGenerate();
ptr = ptr->findBrother();
}
return true;
}
bool BFS::touchDown()
{
return depth ==level;
}
bool BFS::canDive()
{
return sonCount>0;
}
void BFS::initialize(BFS* now)
{
root = now;
root->depth = 0;
root->sonCount = 0;
root->sonIndex = -1;
root->parent = NULL;
root->data = 0;
level = 0;
}
//NULL only when there is no more brother
BFS* BFS::diving()
{
BFS* ptr = this;
while (!ptr->touchDown())
{
if (ptr->canDive())
{
ptr = ptr->sonArray[0];
}
else
{
if (ptr->hasBrother())
{
ptr = ptr->nextBrother();
}
else
{
ptr = ptr->findUncle();
}
}
if (ptr==NULL)
{
break; //no more way to dive
}
}
return ptr;
}
bool BFS::hasBrother()
{
if (parent!=NULL)
{
if (parent->sonCount > sonIndex+1)//has little brother
{
return true;
}
}
return false;
}
BFS* BFS::nextBrother()
{
if (parent!=NULL)
{
if (parent->sonCount > sonIndex+1)//has little brother
{
return parent->sonArray[sonIndex+1]; //next little brother
}
}
return NULL;
}
BFS* BFS::findUncle()
{
BFS* ptr= this;
while (!(ptr->hasBrother()))
{
ptr = ptr->parent;
if (ptr==NULL)
{
return NULL;
}
}
return ptr->nextBrother();
}
BFS* BFS::findBrother()
{
BFS* ptr = this;
if (ptr->hasBrother())
{
return ptr->nextBrother();
}
else
{
ptr = ptr->findUncle();
if (ptr==NULL)
{
return NULL;
}
else
{
return ptr->diving();
}
}
}
void BFS::addSon(int sonData)
{
BFS* ptr;
if (sonCount+1<MaxSonCount)
{
ptr = createSon();
ptr->data = sonData;
ptr->sonCount = 0;
ptr->parent = this;
ptr->depth = level+1;
sonArray[sonCount] = ptr;
ptr->sonIndex = sonCount;
sonCount++;
}
else
{
cout<<"Exceed max of sons!";
}
}
void BasicMatrix::readFromFile(const char* fileName)
{
int r=0, c=0;
char ch;
ifstream f;
f.open(fileName);
while (!f.eof())
{
ch = f.peek();
if (ch!=10) //return char
{
f>>lst[r][c];
c++;
if (c>colNum)
colNum = c;
}
else
{
f.ignore();
r++;
setCol(c);
c =0;
}
}
if (r!=0)
{
setRow(r+1);
}
}
void BasicMatrix::initialize()
{
for (int r=0; r < rowNum; r++)
{
for (int c=0; c< colNum; c++)
{
lst[r][c] = 0;
}
}
}
void BasicMatrix::display(bool displayNumber)
{
// int temp;
long preFlag;
int number=0;
preFlag = cout.flags();
// temp = cout.precision(4);
// cout.setf(ios::fixed);
cout<<"\nrow\\col";
for (int c=0; c< colNum; c++)
{
cout<<" "<<c;
}
cout<<"\n\n";
for (int r = 0; r< rowNum; r++)
{
cout<<r<<"\t ";
number = 0;
for (c = 0; c< colNum; c++)
{
cout<<(fabs(lst[r][c])<LIMIT?0:lst[r][c])<<" ";
if (fabs(lst[r][c])>=LIMIT)
{
number++;
}
}
if (displayNumber)
{
cout<<number;
}
cout<<endl;
}
// cout.precision(temp);
cout.flags(preFlag);
}
BasicMatrix::BasicMatrix()
{
rowNum = 5;
colNum = 5;
initialize();
}
void BFS::onNextNode()
{
}
double& BasicMatrix::items(int r, int c)
{
return lst[r][c];
}
The following is the input of program: (This is really a pain! It costs me hours.)
1 1000 1000 1 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1 2 1000 1000 3 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 2 1 1000 1000 3 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1 1000 1000 1000 1 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1 1000 1000 1000 2 1000 1000 2 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 3 1000 1000 2 3 1000 1000 3 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 3 1000 1000 3 2 1000 1000 4 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1 1000 1000 2 1000 1000 1000 3 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 2 1000 1000 1000 3 1000 1000 3 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 3 1000 1000 3 4 1000 1000 4 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 4 1000 1000 4 3 1000 1000 3 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 3 1000 1000 3 1000 1000 1000 2 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 3 1000 1000 1000 2 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 4 1000 1000 2 2 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 3 1000 1000 2 3 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 2 1000 1000 3
The result is too many! 4480!
...
...
now it is:4463 The route is:dh, cd, gh, bc, ab, ae, ei, ef, im, mn, no, ko, fj, op, lp, total=30 now it is:4464 The route is:dh, cd, gh, bc, ab, ae, ei, ef, im, mn, no, ko, hl, lp, fj, total=30 now it is:4465 The route is:dh, cd, gh, bc, ab, ae, ei, ef, im, mn, no, ko, hl, lp, ij, total=30 now it is:4466 The route is:dh, cd, gh, bc, ab, ae, ei, ef, im, mn, no, ko, ij, hl, lp, total=30 now it is:4467 The route is:dh, cd, gh, bc, ab, ae, ei, ef, im, mn, no, ko, ij, kl, lp, total=30 now it is:4468 The route is:dh, cd, gh, bc, ab, ae, ei, ef, im, mn, no, ko, ij, op, lp, total=30 now it is:4469 The route is:dh, cd, gh, bc, ab, ae, ei, ef, im, mn, no, ko, kl, lp, fj, total=30 now it is:4470 The route is:dh, cd, gh, bc, ab, ae, ei, ef, im, mn, no, ko, kl, lp, ij, total=30 now it is:4471 The route is:dh, cd, gh, bc, ab, ae, ei, ef, im, mn, no, ko, op, lp, fj, total=30 now it is:4472 The route is:dh, cd, gh, bc, ab, ae, ei, ef, im, mn, no, ko, op, lp, ij, total=30 now it is:4473 The route is:dh, cd, gh, bc, ab, ae, ei, ef, im, mn, no, op, lp, fj, kl, total=30 now it is:4474 The route is:dh, cd, gh, bc, ab, ae, ei, ef, im, mn, no, op, lp, fj, ko, total=30 now it is:4475 The route is:dh, cd, gh, bc, ab, ae, ei, ef, im, mn, no, op, lp, ij, kl, total=30 now it is:4476 The route is:dh, cd, gh, bc, ab, ae, ei, ef, im, mn, no, op, lp, ij, ko, total=30 now it is:4477 The route is:dh, cd, gh, bc, ab, ae, ei, ef, im, mn, no, op, lp, kl, fj, total=30 now it is:4478 The route is:dh, cd, gh, bc, ab, ae, ei, ef, im, mn, no, op, lp, kl, ij, total=30 now it is:4479 The route is:dh, cd, gh, bc, ab, ae, ei, ef, im, mn, no, op, lp, ko, fj, total=30 now it is:4480 The route is:dh, cd, gh, bc, ab, ae, ei, ef, im, mn, no, op, lp, ko, ij, total=30 The total number is :4480