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

Lines 31 and 33 are assignments instead of comparisons.

PS. In the future, try to be much more detailed than just stating "code is not working".

Sorry. Thanks for that tip. But what i am having trouble with is that in my SetDepends function the "ndeps" and "deps" are not being intitialized. but i have the setdeps function at the top.

This article has been dead for over six months. Start a new discussion instead.