I am writing a program that implements a topological sort. The actual question is as follows : Given a collection of n items and dependency lists for each item, determine whether the dependencies support a topological sort. If not, report this fact. Otherwise, find a topological sort of the vertices with respect to the given dependency lists. A topological sort of the items is a permutation of the items with the property that every item in the permutation is to the right of all items in its dependency list.
However i am stuck and cannot figure out why my code is not working, can anyone help?
#include <iostream>
#include <fstream>
#include <cstdlib>
using namespace std;
class Object{
public:
char *id;
Object **depends;
int ndepends;
enum Color { BLUE, BROWN, YELLOW };
Color color;
Object (char *id){
this->id = new char[strlen(id)+1];
strcpy(this->id, id);
color = BLUE;
}
void setDeps(Object **deps, int ndeps){
ndepends = ndeps;
depends = deps;
}
~Object () {
delete id;
delete depends;
}
void topo(){
if (color = YELLOW)
return;
if (color = BROWN){
cout << "uh oh\n";
exit(0);
}
color = BROWN;
for(int i=0; i<ndepends; i++)
depends[i]->topo();
cout << " " << id;
color = YELLOW;
}
void Show(){
cout << id << " : ";
for( int i=0; i < ndeps; i++) cout << depends[i]->id
<< " ";
cout << "\n";
}
void init (char *);
};
class Graph{
public:
Object *objects;
int nobjects;
fstream fin;
char buffer[1024];
Graph (char *filename){
fin.open(filename, ios::in);
if (fin.fail()){
cerr << "Cannot Open " << filename << "\n";
exit (0);
}
}
~Graph () {
delete objects;
}
void getObjects () {
for ( nobjects = 0; fin >> buffer ; nobjects++ )
if (buffer == "-") break;
objects = new Object[nobjects];
fin.seekg(0 , ios::beg);
for (int i=0; fin >> buffer && buffer[0] != '-'; i++)
objects[i].init(buffer);
}
void setDepends (int i) {
size_t mark = fin.tellg();
for (int ndeps=0; fin >> buffer && buffer[0] != '-'; ndeps++)
Object **deps = new Object*[ndeps];
fin.seekg(mark, ios::beg);
for (int ndeps=0; fin >> buffer && buffer[0] != '-'; ){
int n=atoi(buffer);
if (0<=n && n<nobjects) deps[ndeps++]=&objects[n];
}
objects[i].setDeps(deps, ndeps);
}
void setDepend (){
for (int i=0; i < nobjects; i++)
setDepends(i);
}
void Sort() {
for (int i=0; i < nobjects; i++)
objects[i].topo();
cout << "\n";
}
void Show(){ for (int i=0; i<nobjects; i++) graph[i]->Show();
}
};
int main(int argc, char **argv)
{
if (argc != 2) {
cout << "\nUsage: " << argv[0] << " <filename>\n";
exit (0);
}
Graph *graph = new Graph(argv[1]);
graph->getObjects();
graph->setDepend();
graph->Sort();
graph->Show();
}