Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- void Graph::tarjan(int node, Stack &successors, Stack &recStack, Hashtable &visited, Hashtable &explored, int &index){
- int j, last, dummy = -1, indexOut, flag = 0;;
- index++;
- visited.addVisited(node, dummy);
- successors.push(node, index, index);
- recStack.push(node, index, index);
- while(recStack.getSize() > 0){
- //check top's low_rank and save it in min_lowrank
- last = -1;
- indexOut = nodeIndexOut_.getListHead(node);
- if(indexOut < 0)
- countOut = 0;
- else
- countOut = bufferOut_.getTotalNodeCount(indexOut);
- for(j = 0; j < countOut; j++){
- neighbor = bufferOut_.getNeighbor(indexOut, j, last, node);
- if(!visited.searchVisited(neighbor, dummy)){ //TODO: too slow, checks marked neighbors multiple times
- explored.addVisited(neighbor, dummy);
- node = neighbor;
- index++;
- visited.addVisited(node, dummy);
- successors.push(node, index, index);
- recStack.push(node, index, index);
- flag = 1;
- break;
- }
- else{
- explored.addVisited(neighbor, dummy);
- node.lowlink = min(node.lowlink, neighbor.lowlink);
- }
- }
- if(flag){ //if we ended up here from break, recurse
- flag = 0;
- continue;
- }
- if(node.lowlink < node.index){
- node1 = recStack.pop();
- node = recStack.top();
- node.lowlink = min(node.lowlink, node1.lowlink);
- }
- else{
- do{
- x = successors.pop();
- //fix x's SCC
- }(while x != node);
- recStack.pop();
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement