inference-engine/thirdparty/ade/ade/source/topological_sort.cpp

   1 // Copyright (C) 2018 Intel Corporation
   2 //
   3 // SPDX-License-Identifier: Apache-2.0
   4 //
   5
   6 #include "passes/topological_sort.hpp"
   7
   8 #include <vector>
   9 #include <unordered_set>
  10
  11 #include "graph.hpp"
  12
  13 namespace ade
  14 {
  15 namespace passes
  16 {
  17 using sorted_t = std::vector<NodeHandle>;
  18 using visited_t = std::unordered_set<Node*>;
  19
  20 static void visit(sorted_t& sorted, visited_t& visited, const NodeHandle& node)
  21 {
  22     if (visited.end() == visited.find(node.get()))
  23     {
  24         for (auto adj:
  25              util::map(node->inEdges(), [](const EdgeHandle& e) { return e->srcNode(); }))
  26         {
  27             visit(sorted, visited, adj);
  28         }
  29         sorted.push_back(node);
  30         visited.insert(node.get());
  31     }
  32 }
  33
  34 void TopologicalSort::operator()(TypedPassContext<TopologicalSortData> context) const
  35 {
  36     sorted_t sorted;
  37     visited_t visited;
  38     for (auto node: context.graph.nodes())
  39     {
  40         visit(sorted, visited, node);
  41     }
  42     context.graph.metadata().set(TopologicalSortData(std::move(sorted)));
  43 }
  44
  45 const char* TopologicalSort::name()
  46 {
  47     return "TopologicalSort";
  48 }
  49
  50 const char* TopologicalSortData::name()
  51 {
  52     return "TopologicalSortData";
  53 }
  54
  55 bool LazyTopologicalSortChecker::nodeCreated(const Graph& /*graph*/, const NodeHandle& /*node*/)
  56 {
  57     // We need to rebuild nodes list after nodes creation
  58     return false;
  59 }
  60
  61 bool LazyTopologicalSortChecker::nodeAboutToBeDestroyed(const Graph& /*graph*/, const NodeHandle& /*node*/)
  62 {
  63     // Removing node cannot change topological order and sorter nodes list can correctly handle nodes removal
  64     return true;
  65 }
  66
  67 bool LazyTopologicalSortChecker::edgeCreated(const Graph& /*graph*/, const EdgeHandle& /*edge*/)
  68 {
  69     // Adding edge CAN change topological order
  70     return false;
  71 }
  72
  73 bool LazyTopologicalSortChecker::edgeAboutToBeDestroyed(const Graph& /*graph*/, const EdgeHandle& /*edge*/)
  74 {
  75     // Removing edge cannot change topological order
  76     return true;
  77 }
  78
  79 bool LazyTopologicalSortChecker::edgeAboutToBeRelinked(const Graph& /*graph*/,
  80                                                        const EdgeHandle& /*edge*/,
  81                                                        const NodeHandle& /*newSrcNode*/,
  82                                                        const NodeHandle& /*newDstNode*/)
  83 {
  84     // Relinking edge CAN change topological order
  85     return false;
  86 }
  87
  88 }
  89 }