Topological Sorting Algorithm not working right

Question

Ok I have to do a topological sorting algorithm on a graph. I need to find the node with in degree of 0 and queue it, then print it and remove all the edges going to it. I am removing the edges by decrementing the number of edges going into it in the countList map. I have the adjacency list as a map, and the count of in degrees for each node as a map. My algorithm is only accessing the first element of the adjacency list. so my output queue is only displaying the first key of the adjacency list map. over and over. I stopped the while loop at 25 so it wouldn't be infinite.

            string z = "";
            string a = "";
            cout << "Queue: ";
            do{
                for(it = countList.begin(); it!=countList.end(); ++it){
                    if(it->second == 0){
                        Q.push(it->first);
                                                    countList.at(it->first)--;
                        z = adjList[it->first];
                        cout <<"z: " << z <<endl;
                        //remove edges
                        for(int i = 0; i< z.length(); i++){
                            a = z.at(i);
                            cout << "z at " <<i << " : " <<a <<endl;
                            countList.at(a)--;
                        }//end for
                    }//end if
                    //cout << Q.front() << ", ";
                    //Q.pop();

                }//end for
                cout << Q.front() << ", ";
                Q.pop();
            }while(!Q.empty());

Can someone help me with understanding why it is not iterating through the countList and is only staying on the first element?

Thank you.

So I changed the countList.at(a)-+1, to countList.at(a)-- for proper decrementation. Now the output is more than just the first vertex that was 0 in degree. But the output is still wrong.

Here is the whole thing. My variable declarations

    vector<string> E;   
map<string, string> adjList;
map<string, int>countList;
map<string, int>::iterator it;
queue<string> Q;

I don't want to put up the code for the adjacencyList or countList but here are how they look.

//These represent the edges between the two paired nodes
AdjacencyList: (1,2) (1,4) (1,3) (2,4) (2,5) (3,6) (4,6) (4,7) (4,3) (5,4) (5,7) (7,6)

//The first is the node name and the second element is how many edges come into that node.
countList: (1,0) (2,1) (3,2) (4,3) (5,1) (6,3) (7,2)

My output should be either:

Queue: 1,2,5,4,3,7,6 
//or
Queue: 1,2,5,4,7,3,6

OK I added

countList.at(it->first)--;

after I push the vertex onto the queue. So that should decrement the count of that vertex to -1. This narrowed my output alot.

OK IT WORKS NOW!!! I changed the while loop to stop after the queue is empty and printed the queue in the while loop and it fixed the problem.

My output now is:

Queue: 1, 2, 5, 4, 7, 3, 6, 

Ok this code will only work if the node names are only single values. How would I change the adjList mapping for values that node names are longer than a single character? Perhaps a linked list being pointed to by the key value? And if so how would I do that?

Answer 1

Ok, now we're getting somewhere.

The very first version (before your edit) did decrement the incoming edge count incorrectly.

Now there is another issue: In each iteration, you repeatedly take nodes that have already been taken (node #1 is a good example) because they still have zero count (number of incoming edges). By decrementing their ancestors again and again, some of the counts will drop below zero (such as for node #2).

You have to somehow mark the nodes that have already been used and do not use them again and again in each cycle. This can either be achieved a) by setting some flag for the node, b) using a set of used nodes, c) by removing the node from the list, or (probably the simpliest) d) by setting their edge count to a negative number (for instance, -1) after putting them into the output queue.

After your second edit, the algorithm as such should work (it works for me after some minor tweeks). However, the usage of adjList is pretty strange -- how do you exactly include multiple edges for one node into a map?