yznk 0 Newbie Poster
#include <iostream>
#include <string>
#include <vector>

using namespace std;

class Digraph
{
	public:
	vector<bool> visited;
	vector<string> tasks;
	vector<vector<int> > precede, postcede;
	vector<int> order;
	int numtasks, num1, num2;

	void resetVisited(){
		for(int i=0; i<visited.size(); i++){
			visited[i]=false;
		}
	}
	
	bool check(vector<vector<int> > checking, int pos1)
	//Returns true if there is a viable order, false if there is not.
	//This is the acyclic check.
	{
		if(visited[pos1]){
			resetVisited();
			return false;
		}
		visited[pos1]=true;
		bool flag=true;
		if(checking[pos1][0]==-1){
			resetVisited();
			return true;
		}
		for(int i=0; i<checking[pos1].size(); i++){
			if(!check(checking, checking[pos1][i]-1)){
				flag= false;
			}
		}
		resetVisited();
		return flag;
	}
	
	void edgeAddition(int numB, int numA)
	{
		if(precede[numA-1][0]==-1){
			precede[numA-1][0]=numB;
		}else{
			precede[numA-1].push_back(numB);
		}
		if(postcede[numB-1][0]==-1){
			postcede[numB-1][0]=numA;
		}else{
			postcede[numB-1].push_back(numA);
		}
		if(!check(precede, numA-1)){
			cout << "Infinite Preceding Loop! Cannot Complete Tree." << endl;
			exit(1);
		}
	}
	
	void edgeDelete(int numA, int numB)
	{
		for(int i=0; i<precede[numA-1].size(); i++){
			if(precede[numA-1][i]==numB){
				precede[numA-1].erase(precede[numA-1].begin()+i);
			}
		}
		for(int i=0; i<postcede[numB-1].size(); i++){
			if(postcede[numB-1][i]==numA){
				postcede[numB-1].erase(postcede[numB-1].begin()+i);
			}
		}
	}
	
	Digraph()//Constructor
	{
		string input="?";
		cout << "How many tasks?" << endl;
		cin >> numtasks;
		tasks.resize(numtasks);
		precede.resize(numtasks);
		postcede.resize(numtasks);
		visited.resize(numtasks);
		resetVisited();
		for(int i=0; i<numtasks; i++){
			precede[i].resize(1);
			postcede[i].resize(1);
			precede[i][0]=-1;
			postcede[i][0]=-1;
		}
		getline(cin, input);
		for(int i=1;i<=numtasks;i++){
			cout << i << ". ";
			getline(cin, tasks[i-1]);
		}
		cout << "Now indicate what precedes what (0 terminates):" << endl;
		while(num1){
			string first, second;
			int i=0;
			cin >> num1;
			if(num1!=0){
				cin >> num2;
				edgeAddition(num1,num2);
			}else{
				break;
			}
		}
	}
	
	~Digraph()//Destructor
	{
		visited.~vector();
		tasks.~vector();
		precede.~vector();
	}
	
	void topSort2()
	{
		bool flag;
		vector<int> stack;
		for(int i=0; i<numtasks; i++){
			if(precede[i][0]==-1){
				stack.push_back(i);
				visited[i]=true;
			}
		}
		while(!stack.empty()){
			cout << "work" << endl;
			flag=true;
			for(int j=0; j<postcede[stack[stack.size()-1]].size(); j++){
				if(postcede[stack[stack.size()-1]][0]!=-1&&!visited[postcede[stack[stack.size()-1]][j]]){
					flag=false;
				}
			}
			if(flag){
				cout << stack[stack.size()-1] << endl;
				order.push_back(stack[stack.size()-1]);
				stack.pop_back();
			}else{
				for(int j=0; j<postcede[stack[stack.size()-1]].size(); j++){
					if(!visited[postcede[stack[stack.size()-1]][j]]){
						visited[postcede[stack[stack.size()-1]][j]]=true;
						stack.push_back(postcede[stack[stack.size()-1]][j]);
						break;
					}
				}
			}
		}
	}
	
	void display()
	{
		cout << endl << endl;
		for(int i=0; i<numtasks; i++){
			cout << order[order.size()-i-1] << endl;
		}
	}
};

int main()
{
	Digraph graph;
	graph.topSort2();
	graph.display();
	exit(1);
}

During my toposort2 function this line if(postcede[stack[stack.size()-1]][0]!=-1&&!visited[postcede[stack[stack.size()-1]][j]]) is causing a seg fault. i cannot figure out why. could anyone point me in the right direction? The point of the program is to take a number tasks and then the order and then print out the tasks in topological order.
for example:
1. a
2. b
3. c

3 precedes 1
1 precedes 2
2 precedes 1


and if there is a cycle then the topo sort stops.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.