Kruskal--A greedy algorithm in graph
A.First Edition
This is actually another application of my BFS class, or you can call it sixth edition of BFS class, whatever.
The base framework remains basically same except that I create a new class Kruskal which inherited from Prim class.
Originally I thought Kruskal is a much easier than Prim and planned to finish it within one morning. However, it
turned out to be not the case. The biggest problem I run into is how to justify whether the graph has a simple
circuit or not when a new edge is added. The first idea is to make a trace, however, you need to record all vertices
you tracked and make comparison. The first time that you see a repeated vertices in your tracing path, it means a
circuit. It is simply too costly expensive! A BFS within a BFS! No way! So I was stuck. It rang a bell when I asked
teacher about his suggestion. At that moment, I realized that I have the clue---The maximum of edges in a simple
non-circuit graph with n vertices is simply n-1. So simple, so easy!
A minimum spanning tree can be obtained by Kruskal algorithm, it creates a root among the connected graph by choosing
the smallest edge. Then every time it adds a minimum edge into that graph so that there is no circuits created by
the edge. It does not necessarily need to be connected during procedure. But after n-1 edges are added, it is
definitely a tree, if you keep the graph to be non-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 justify if the edge added will form a circuit or not.
1. bool Kruskal::validateOption(int sonData)
This is the only function implemented in Kruskal class. I first need to check if the added edge will make the
number of vertices are equal to number of edges. If so, it is a circuit. Then I need to check the smallest
edge not inside graph is added.
C.Further improvement
1. The input is really a pain! The most bugs are coming from the huge Matrix.
2. I have not finished the test as I was too tired and tomorrow is my exam day for English writing.
#include <iostream>
#include <cmath>
#include <fstream>
using namespace std;
const int MaxSonCount =24;
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
{
protected:
static bool vertexOption[MaxRow];
static BasicMatrix Mx;
static int smallest;
void findSmallest();
bool isTheOne(int sonData);
BFS* createSon();
bool validateOption(int sonData);
void onNextNode();
void onVisit(int& counter);
void setVertexOption();
public:
void readFromFile(char* fileName);
void display();
};
int Prim::smallest = 0;
BasicMatrix Prim::Mx;
bool Prim::vertexOption[MaxRow]={false};
class Kruskal: public Prim
{
protected:
BFS* createSon();
void onNextNode();
bool validateOption(int sonData);
};
int main()
{
Kruskal K;
K.readFromFile("c:\\nickedge.txt");
K.setOptionArray(VertexOption, 24);
K.beginCount(15);
return 0;
}
BFS* Kruskal::createSon()
{
BFS* ptr = new Kruskal;
return ptr;
}
void Kruskal::onNextNode()
{
trackBack();
}
bool Kruskal::validateOption(int sonData)
{
bool inPath=false;
bool theSmall =false;
int theLength=INFINITE;
int dataLength=0;
int count=0;
//if it is in the tree, no way
if (choiceTaken[sonData])
{
return false;
}
setVertexOption();
//cannot be circuit
for (int r=0; r< Mx.row(); r++)
{
if (vertexOption[r]||Mx.items(r, sonData)<INFINITE)//if new vertex is counted
{
count++;
}
}
for (int c=0; c<Mx.col(); c++)
{
if (choiceTaken[c])
{
count--;
}
}
if (count==1)//vertices-edges=0
{
return false;
}
//find the smallest
for (c=0; c<Mx.col(); c++)
{
if (!choiceTaken[c])//among edge outside tree
{
for (int r=0; r<Mx.row(); r++)
{
if (c==sonData&&Mx.items(r, c)<INFINITE)//find
{
dataLength = Mx.items(r,c);
}
if (Mx.items(r, c)<theLength)//of course small than INFINITE
{
theLength=Mx.items(r,c);
}
if (dataLength>theLength)
{
return false;
}
}
}
}
return true;
}
void Prim::setVertexOption()
{
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;
}
}
}
}
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;
}
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();
setVertexOption();
for (int 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);
}
}
}
}
}
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