Advertisement
Guest User

Untitled

a guest
Dec 8th, 2016
72
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.42 KB | None | 0 0
  1. void Graph::tarjan(int node, Stack &successors, Stack &recStack, Hashtable &visited, Hashtable &explored, int &index){
  2.     int j, last, dummy = -1, indexOut, flag = 0;;
  3.     index++;
  4.     visited.addVisited(node, dummy);
  5.     successors.push(node, index, index);
  6.     recStack.push(node, index, index);
  7.     while(recStack.getSize() > 0){
  8.         //check top's low_rank and save it in min_lowrank
  9.         last = -1;
  10.         indexOut = nodeIndexOut_.getListHead(node);
  11.         if(indexOut < 0)
  12.             countOut = 0;
  13.         else
  14.             countOut = bufferOut_.getTotalNodeCount(indexOut);
  15.         for(j = 0; j < countOut; j++){
  16.             neighbor = bufferOut_.getNeighbor(indexOut, j, last, node);
  17.             if(!visited.searchVisited(neighbor, dummy)){ //TODO: too slow, checks marked neighbors multiple times
  18.                 explored.addVisited(neighbor, dummy);
  19.                 node = neighbor;
  20.                 index++;
  21.                 visited.addVisited(node, dummy);
  22.                 successors.push(node, index, index);
  23.                 recStack.push(node, index, index);
  24.                 flag = 1;
  25.                 break;
  26.             }
  27.             else{
  28.                 explored.addVisited(neighbor, dummy);
  29.                 node.lowlink = min(node.lowlink, neighbor.lowlink);
  30.             }
  31.         }
  32.         if(flag){ //if we ended up here from break, recurse
  33.             flag = 0;
  34.             continue;
  35.         }
  36.         if(node.lowlink < node.index){
  37.             node1 = recStack.pop();
  38.             node = recStack.top();
  39.             node.lowlink = min(node.lowlink, node1.lowlink);
  40.         }
  41.         else{
  42.             do{
  43.                 x = successors.pop();
  44.                 //fix x's SCC
  45.             }(while x != node);
  46.             recStack.pop();
  47.         }
  48.     }
  49. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement