chromium/third_party/mediapipe/src/mediapipe/framework/deps/topologicalsorter.h

// Copyright 2019 The MediaPipe Authors.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//      http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

#ifndef MEDIAPIPE_DEPS_TOPOLOGICALSORTER_H_
#define MEDIAPIPE_DEPS_TOPOLOGICALSORTER_H_

#include <functional>
#include <queue>
#include <vector>

namespace mediapipe {

// TopologicalSorter provides topologically sorted traversal of the nodes of a
// directed acyclic graph (DAG) with up to INT_MAX nodes. The sorter requires
// that all nodes and edges be added before traversing the nodes, otherwise it
// will die with a fatal error. If a cycle is detected during the traversal,
// the sorter will stop the traversal, and set the cycle_nodes vector.
//
// Sample usage:
//   TopologicalSorter sorter(num_nodes);
//   sorter.AddEdge(ObjToIndex(obj_a), ObjToIndex(obj_b));
//   sorter.AddEdge(ObjToIndex(obj_a), ObjToIndex(obj_c));
//   ...
//   sorter.AddEdge(ObjToIndex(obj_b), ObjToIndex(obj_c));
//   int idx;
//   bool cyclic = false;
//   std::vector<int> cycle_nodes;
//   while (sorter.GetNext(&idx, &cyclic, &cycle_nodes)) {
//     if (cyclic) {
//       PrintCycleNodes(cycle_nodes);
//     } else {
//       ABSL_LOG(INFO) << idx;
//     }
//   }
class TopologicalSorter { … };

}  // namespace mediapipe

#endif  // MEDIAPIPE_DEPS_TOPOLOGICALSORTER_H_