Function PruneForReverseReachability

tensorflow/core/graph/algorithm.cc:209–243

}

bool PruneForReverseReachability(Graph* g,
                                 std::unordered_set<const Node*> start) {
  // Compute set of nodes that we need to traverse in order to reach
  // the nodes in "start" by performing a breadth-first search from those
  // nodes, and accumulating the visited nodes.
  std::vector<bool> visited(g->num_node_ids());
  for (auto node : start) {
    visited[node->id()] = true;
  }
  std::deque<const Node*> queue(start.begin(), start.end());
  while (!queue.empty()) {
    const Node* n = queue.front();
    queue.pop_front();
    for (const Node* in : n->in_nodes()) {
      if (!visited[in->id()]) {
        visited[in->id()] = true;
        queue.push_back(in);
        VLOG(2) << "Reverse reach : " << n->name() << " from " << in->name();
      }
    }
  }

  // Make a pass over the graph to remove nodes not in "visited".
  bool any_removed = false;
  for (int i = 0; i < visited.size(); ++i) {
    if (!visited[i]) {
      Node* n = g->FindNodeId(i);
      if (n != nullptr && !n->IsSource() && !n->IsSink()) {
        g->RemoveNode(n);
        any_removed = true;
      }
    }
  }
  return any_removed;
}

bool FixupSourceAndSinkEdges(Graph* g) {
  // Connect all nodes with no incoming edges to source.