Function ValidateGraphHasNoCycle

tensorflow/core/graph/validate.cc:64–116

}

Status ValidateGraphHasNoCycle(const Graph& graph) {
  // A node is ready when all of its inputs have been visited.
  std::vector<const Node*> ready;
  std::vector<int> pending_count(graph.num_node_ids(), 0);

  for (int i = 0; i < graph.num_node_ids(); ++i) {
    const Node* n = graph.FindNodeId(i);
    if (n == nullptr) continue;
    pending_count[i] = n->in_edges().size();
    if (n->IsMerge()) {
      // While-loop cycles are legal cycles so we manually adjust the
      // pending_count to make sure that the loop is visited.
      for (const Edge* e : n->in_edges()) {
        if (!e->IsControlEdge() && e->src()->IsNextIteration()) {
          pending_count[i]--;
        }
      }
    }
    if (pending_count[i] == 0) {
      ready.push_back(n);
    }
  }

  int processed = 0;
  while (!ready.empty()) {
    const Node* node = ready.back();
    ready.pop_back();
    ++processed;

    for (const Edge* out : node->out_edges()) {
      const int output_id = out->dst()->id();
      pending_count[output_id]--;
      if (pending_count[output_id] == 0) {
        ready.push_back(out->dst());
      }
    }
  }

  if (processed < graph.num_nodes()) {
    std::vector<string> nodes_in_cycle;
    for (int i = 0; i < pending_count.size() && nodes_in_cycle.size() < 3;
         ++i) {
      if (pending_count[i] != 0) {
        nodes_in_cycle.push_back(graph.FindNodeId(i)->name());
      }
    }
    return errors::InvalidArgument(
        "Graph is invalid, contains a cycle with ",
        graph.num_nodes() - processed,
        " nodes, including: ", absl::StrJoin(nodes_in_cycle, ", "));
  }
  return Status::OK();
}

Status VerifyNoDuplicateNodeNames(const GraphDef& graph) {
  absl::flat_hash_set<absl::string_view> nodes;