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