Topological Graph Sorting

Question

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

}

Answer 1

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.