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?