Function StrongConnect

tensorflow/core/grappler/utils/scc.cc:57–115

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) {
  // Iterative version of Tarjan's StrongConnect function.
  // The "call stack" state is composed of a SCCNodeData's caller and
  // caller_loop_location properties.
  v->ResetStack(*index /* index */, nullptr /* caller */);
  ++*index;
  stack->push(v);

  // No one put v on a StrongConnect call stack, reset caller values.
  v->caller = nullptr;
  v->caller_loop_location = 0;

  SCCNodeData* last = v;
  while (true) {
    if (last->caller_loop_location < last->children.size()) {
      // Recursive equivalent: Looping over the children of v (possibly
      // continuing at v->caller_loop_location after having finished a
      // recursive call.
      SCCNodeData* w = last->children[last->caller_loop_location];
      ++(last->caller_loop_location);  // For loop iterator increment
      if (w->index == -1) {
        w->ResetStack(*index /* index */, last /* caller */);
        ++*index;
        stack->push(w);
        last = w;
      } else if (w->onstack == true) {
        last->lowlink = std::min(last->lowlink, w->index);
      }
    } else {
      // At the end of v's children
      if (last->lowlink == last->index) {
        // v is the root of a strongly connected component
        SCCNodeData* top;
        while (true) {
          top = stack->top();
          stack->pop();
          top->onstack = false;
          (*components)[top->node] = *scc_index;
          if (top == last) {
            break;
          }
        }
        ++*scc_index;
      }

      // Go up the recursive call stack
      SCCNodeData* next_last = last->caller;
      if (next_last == nullptr) {
        // All nodes have been seen; finished.
        break;
      } else {
        next_last->lowlink = std::min(next_last->lowlink, last->lowlink);
        last = next_last;
      }
    }
  }