8 #include <boost/assert.hpp> 29 template <
typename TNodeId>
31 std::function<std::vector<TNodeId>(TNodeId)> getIncomingEdges,
32 std::map<TNodeId, NodeState>& nodeStates)
34 for (TNodeId childNode : getIncomingEdges(node))
36 if (nodeStates.find(childNode) == nodeStates.end())
42 if (nodeStates.find(childNode)->second == NodeState::Visiting)
52 template<
typename TNodeId>
53 bool TopologicallySort(
55 std::function<std::vector<TNodeId>(TNodeId)> getIncomingEdges,
56 std::vector<TNodeId>& outSorted,
57 std::map<TNodeId, NodeState>& nodeStates)
59 std::stack<TNodeId> nodeStack;
62 if (nodeStates.find(initialNode) == nodeStates.end())
64 nodeStack.push(initialNode);
67 while (!nodeStack.empty())
69 TNodeId current = nodeStack.top();
71 nodeStates[current] = NodeState::Visiting;
73 auto nextChildOfCurrent = GetNextChild(current, getIncomingEdges, nodeStates);
75 if (nextChildOfCurrent)
77 TNodeId nextChild = nextChildOfCurrent.value();
80 if (nodeStates.find(nextChild) == nodeStates.end())
82 nodeStack.push(nextChild);
87 if (nodeStates[nextChild] == NodeState::Visiting)
95 nodeStates[current] = NodeState::Visited;
96 outSorted.push_back(current);
110 template<
typename TNodeId,
typename TTargetNodes>
112 const TTargetNodes& targetNodes,
113 std::function<std::vector<TNodeId>(TNodeId)> getIncomingEdges,
114 std::vector<TNodeId>& outSorted)
117 std::map<TNodeId, NodeState> nodeStates;
119 for (TNodeId targetNode : targetNodes)
121 if (!TopologicallySort(targetNode, getIncomingEdges, outSorted, nodeStates))
bool GraphTopologicalSort(const TTargetNodes &targetNodes, std::function< std::vector< TNodeId >(TNodeId)> getIncomingEdges, std::vector< TNodeId > &outSorted)