1 // Copyright (C) 2018 Intel Corporation
3 // SPDX-License-Identifier: Apache-2.0
6 #include "passes/topological_sort.hpp"
9 #include <unordered_set>
17 using sorted_t = std::vector<NodeHandle>;
18 using visited_t = std::unordered_set<Node*>;
20 static void visit(sorted_t& sorted, visited_t& visited, const NodeHandle& node)
22 if (visited.end() == visited.find(node.get()))
25 util::map(node->inEdges(), [](const EdgeHandle& e) { return e->srcNode(); }))
27 visit(sorted, visited, adj);
29 sorted.push_back(node);
30 visited.insert(node.get());
34 void TopologicalSort::operator()(TypedPassContext<TopologicalSortData> context) const
38 for (auto node: context.graph.nodes())
40 visit(sorted, visited, node);
42 context.graph.metadata().set(TopologicalSortData(std::move(sorted)));
45 const char* TopologicalSort::name()
47 return "TopologicalSort";
50 const char* TopologicalSortData::name()
52 return "TopologicalSortData";
55 bool LazyTopologicalSortChecker::nodeCreated(const Graph& /*graph*/, const NodeHandle& /*node*/)
57 // We need to rebuild nodes list after nodes creation
61 bool LazyTopologicalSortChecker::nodeAboutToBeDestroyed(const Graph& /*graph*/, const NodeHandle& /*node*/)
63 // Removing node cannot change topological order and sorter nodes list can correctly handle nodes removal
67 bool LazyTopologicalSortChecker::edgeCreated(const Graph& /*graph*/, const EdgeHandle& /*edge*/)
69 // Adding edge CAN change topological order
73 bool LazyTopologicalSortChecker::edgeAboutToBeDestroyed(const Graph& /*graph*/, const EdgeHandle& /*edge*/)
75 // Removing edge cannot change topological order
79 bool LazyTopologicalSortChecker::edgeAboutToBeRelinked(const Graph& /*graph*/,
80 const EdgeHandle& /*edge*/,
81 const NodeHandle& /*newSrcNode*/,
82 const NodeHandle& /*newDstNode*/)
84 // Relinking edge CAN change topological order