tensorflow/core/grappler/utils/scc.cc
// Core DFS step of Tarjan's Strongly Connected Component algorithm
// (implemented using iteration instead of recursion).
Core DFS step of Tarjan's Strongly Connected Component algorithm
(implemented using iteration instead of recursion).
Core DFS step of Tarjan ' s Strongly Connected Component algorithm ( implemented using iteration instead of recursion ) .
void StrongConnect(SCCNodeData* v, std::stack<SCCNodeData*>* stack, int* index,
                   std::unordered_map<const NodeDef*, int>* components,
                   int* scc_index) {
  v->ResetStack(*index , nullptr );
  ++*index;
  stack->push(v);
  v->caller = nullptr;
  v->caller_loop_location = 0;
  SCCNodeData* last = v;
  while (true) {
    if (last->caller_loop_location < last->children.size()) {
      SCCNodeData* w = last->children[last->caller_loop_location];
      ++(last->caller_loop_location);  
      if (w->index == -1) {
        w->ResetStack(*index , last );
        ++*index;
        stack->push(w);
        last = w;
      } else if (w->onstack == true) {
        last->lowlink = std::min(last->lowlink, w->index);
      }
    } else {
      if (last->lowlink == last->index) {
        SCCNodeData* top;
        while (true) {
          top = stack->top();
          stack->pop();
          top->onstack = false;
          (*components)[top->node] = *scc_index;
          if (top == last) {
            break;
          }
        }
        ++*scc_index;
      }
      SCCNodeData* next_last = last->caller;
      if (next_last == nullptr) {
        break;
      } else {
        next_last->lowlink = std::min(next_last->lowlink, last->lowlink);
        last = next_last;
      }
    }
  }
}
void StrongConnect ( SCCNodeData * v , std :: stack < SCCNodeData * > * stack , int * index , std :: unordered_map < const NodeDef * , int > * components , int * scc_index ) { v -> ResetStack ( * index , nullptr ) ; ++ * index ; stack -> push ( v ) ; v -> caller = nullptr ; v -> caller_loop_location = 0 ; SCCNodeData * last = v ; while ( true ) { if ( last -> caller_loop_location < last -> children . size ( ) ) { SCCNodeData * w = last -> children [ last -> caller_loop_location ] ; ++ ( last -> caller_loop_location ) ; if ( w -> index == -1 ) { w -> ResetStack ( * index , last ) ; ++ * index ; stack -> push ( w ) ; last = w ; } else if ( w -> onstack == true ) { last -> lowlink = std :: min ( last -> lowlink , w -> index ) ; } } else { if ( last -> lowlink == last -> index ) { SCCNodeData * top ; while ( true ) { top = stack -> top ( ) ; stack -> pop ( ) ; top -> onstack = false ; ( * components ) [ top -> node ] = * scc_index ; if ( top == last ) { break ; } } ++ * scc_index ; } SCCNodeData * next_last = last -> caller ; if ( next_last == nullptr ) { break ; } else { next_last -> lowlink = std :: min ( next_last -> lowlink , last -> lowlink ) ; last = next_last ; } } } }
Core DFS step of Tarjan's Strongly Connected Component algorithm
(implemented using iteration instead of recursion).
Core DFS step of Tarjan ' s Strongly Connected Component algorithm ( implemented using iteration instead of recursion ) .
// Iterative version of Tarjan's StrongConnect function. // The "call stack" state is composed of a SCCNodeData's caller and // caller_loop_location properties. /* index */ /* caller */ // No one put v on a StrongConnect call stack, reset caller values. // Recursive equivalent: Looping over the children of v (possibly // continuing at v->caller_loop_location after having finished a // recursive call. // For loop iterator increment /* index */ /* caller */ // At the end of v's children // v is the root of a strongly connected component // Go up the recursive call stack // All nodes have been seen; finished.