0

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();
}
2
Contributors
2
Replies
3
Views
7 Years
Discussion Span
Last Post by yznk
0

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".

0

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 topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.