I am trying to implement a topological graph sort, and my program is compiling however I am not getting a populated vector. I have tried running a debugger to track where my variables are going and I am not too sure why. Currently, I have made a graph data structure, which contains a vector of vertices. This gets generated during when I generate a new graph (std:: vector vertices;)
My graph is structure like such:
lass Graph {
struct Edge{
int dest = -1;
Edge* next = nullptr;
Edge(int dest, Edge* next) : dest(dest), next(next){};
~Edge() {delete next;}
};
struct vertex{
int id =0;
int degree = 0;
int colour = 0;
vertex* next = nullptr;
vertex* previous = nullptr;
};
Edge** edges = nullptr;
std:: vector<vertex> vertices;
std:: vector<vertex*> ordering;
All of which get set during the graph generation.
I would really appreciate any help with this sorting.
void Graph::myOwnOrderingHelper(int v, bool *visited, std::stack<vector<vertex*>> &Stack) {
vector<vertex*> hope;
visited[v] = true;
for (int i = 0; i < vertices[v].degree; i++) {
int neighbour = vertices[v].id;
if (!visited[neighbour]){
myOwnOrderingHelper(i, visited, Stack);
cout << vertices[v].next->id;
hope.push_back(vertices[v].next);
}
}
Stack.push(hope);
}
void Graph::myOwnOrdering() {
std:: stack<vector<vertex*>> Stack;
bool* visited = new bool[size];
for(int i = 0; i < size; i++){
visited[i] = false;
}
for (int i = 0; i < size; i++){
if (visited[i] == false){
myOwnOrderingHelper(i, visited, Stack);
}
}
while (Stack.empty() == false){
std::vector<vertex*> temp = Stack.top();
for(int i = 0; i < temp.size(); i++){
cout << temp[i]->degree << endl;
ordering.push_back(temp[i]);
}
Stack.pop();
}
}
Look at this code:
for (int i = 0; i < vertices[v].degree; i++) {
int neighbour = vertices[v].id;
if (!visited[neighbour]){
Every time through this for loop the value of neighbour
will always be the same.
Whatever your for loop is intended to accomplish ( your code is undocumented so it is not easy to guess ) it will in fact always do exactly the same over and over again.