C++ 有向图拓扑排序算法

代码#include algorithm #include cassert #include functional #include map #include memory #include queue #include set #include unordered_set #include vector namespace jc { template typename K, typename V struct DAGNode { K k; V v; std::setDAGNodeK, V* in; std::setDAGNodeK, V* out; }; template typename K, typename V class DAGGraph { public: bool AddEdge(const K from, const K to); V operator[](const K key); bool Exist(const K key) const; void Clear(); std::size_t Size() const; void Walk(std::functionvoid(const K k, const V v) f, bool start_from_head true); void WalkHeads(std::functionvoid(const K k, const V v) f); void WalkTails(std::functionvoid(const K k, const V v) f); std::unordered_setK NextKeys(); std::unordered_setK NextKeys(const K key); private: bool IsCyclic(const DAGNodeK, V from, const DAGNodeK, V to) const; void RefreshWalkSequences(); std::vectorstd::setK ConnectedComponents() const; void DFS(const K k, std::unordered_setK* visited, std::setK* connected_components) const; std::vectorK TopologicalSequence(const std::setK connected_components, bool start_from_head) const; private: std::mapK, DAGNodeK, V bucket_; std::unordered_setK heads_; std::unordered_setK tails_; std::vectorstd::vectorK sequences_start_from_head_; std::vectorstd::vectorK sequences_start_from_tail_; private: bool allow_modify_ true; std::vectorstd::vectorK sequences_start_from_head_for_next_; std::unordered_setK current_heads_for_next_; }; template typename K, typename V inline bool DAGGraphK, V::AddEdge(const K from, const K to) { assert(allow_modify_); if (from to || !bucket_.count(from) || !bucket_.count(to) || IsCyclic(bucket_.at(from), bucket_.at(to))) { return false; } bucket_.at(from).out.emplace(bucket_.at(to)); bucket_.at(to).in.emplace(bucket_.at(from)); heads_.erase(to); tails_.erase(from); sequences_start_from_head_.clear(); sequences_start_from_tail_.clear(); return true; } template typename K, typename V inline V DAGGraphK, V::operator[](const K key) { if (!bucket_.count(key)) { assert(allow_modify_); bucket_[key].k key; heads_.emplace(key); tails_.emplace(key); sequences_start_from_head_.clear(); sequences_start_from_tail_.clear(); } return bucket_.at(key).v; } template typename K, typename V inline bool DAGGraphK, V::Exist(const K key) const { return bucket_.count(key); } template typename K, typename V inline void DAGGraphK, V::Clear() { allow_modify_ true; bucket_.clear(); heads_.clear(); tails_.clear(); sequences_start_from_head_.clear(); sequences_start_from_tail_.clear(); } template typename K, typename V inline std::size_t DAGGraphK, V::Size() const { return bucket_.size(); } template typename K, typename V inline void DAGGraphK, V::Walk(std::functionvoid(const K k, const V v) f, bool start_from_head) { if (sequences_start_from_head_.empty()) { RefreshWalkSequences(); } const std::vectorstd::vectorK seqs_to_walk start_from_head ? sequences_start_from_head_ : sequences_start_from_tail_; for (const std::vectorK seq : seqs_to_walk) { std::for_each(std::begin(seq), std::end(seq), [](const K key) { const DAGNodeK, V node bucket_.at(key); f(node.k, node.v); }); } } template typename K, typename V inline void DAGGraphK, V::WalkHeads( std::functionvoid(const K k, const V v) f) { if (sequences_start_from_head_.empty()) { RefreshWalkSequences(); } for (const std::vectorK seq : sequences_start_from_head_) { std::for_each(std::begin(seq), std::end(seq), [](const K key) { if (heads_.count(key)) { const DAGNodeK, V node bucket_.at(key); f(node.k, node.v); } }); } } template typename K, typename V inline void DAGGraphK, V::WalkTails( std::functionvoid(const K k, const V v) f) { if (sequences_start_from_head_.empty()) { RefreshWalkSequences(); } for (const std::vectorK seq : sequences_start_from_tail_) { std::for_each(std::begin(seq), std::end(seq), [](const K key) { if (tails_.count(key)) { const DAGNodeK, V node bucket_.at(key); f(node.k, node.v); } }); } } template typename K, typename V inline std::unordered_setK DAGGraphK, V::NextKeys() { assert(allow_modify_); // allowed call once unless Clear() allow_modify_ false; current_heads_for_next_ heads_; if (sequences_start_from_head_.empty()) { RefreshWalkSequences(); } return heads_; } template typename K, typename V inline std::unordered_setK DAGGraphK, V::NextKeys(const K key) { assert(!allow_modify_); // must call NextKeys() before assert(current_heads_for_next_.count(key)); current_heads_for_next_.erase(key); std::unordered_setK res; for (std::vectorK seq : sequences_start_from_head_for_next_) { auto it std::find(begin(seq), std::end(seq), key); if (it std::end(seq)) { continue; } seq.erase(it); const std::setDAGNodeK, V* nodes bucket_.at(key).out; for (DAGNodeK, V* v : nodes) { const std::setDAGNodeK, V* prev_nodes v-in; bool no_prev_node_in_seq std::all_of(std::begin(prev_nodes), std::end(prev_nodes), [](DAGNodeK, V* in_node) { return std::find(std::begin(seq), std::end(seq), in_node-k) std::end(seq); }); if (no_prev_node_in_seq) { current_heads_for_next_.emplace(v-k); res.emplace(v-k); } } break; } return res; } template typename K, typename V inline bool DAGGraphK, V::IsCyclic(const DAGNodeK, V from, const DAGNodeK, V to) const { std::queueDAGNodeK, V* q; for (DAGNodeK, V* v : from.in) { q.emplace(v); } std::unordered_setDAGNodeK, V* visited; while (!q.empty()) { DAGNodeK, V* node q.front(); q.pop(); if (visited.count(node)) { continue; } if (node to) { return true; } visited.emplace(node); for (DAGNodeK, V* v : node-in) { q.emplace(v); } } return false; } template typename K, typename V inline void DAGGraphK, V::RefreshWalkSequences() { sequences_start_from_head_.clear(); sequences_start_from_tail_.clear(); const std::vectorstd::setK connected_components ConnectedComponents(); for (const std::setK x : connected_components) { const std::vectorK seq_from_head TopologicalSequence(x, true); const std::vectorK seq_from_tail TopologicalSequence(x, false); assert(!seq_from_head.empty()); assert(!seq_from_tail.empty()); sequences_start_from_head_.emplace_back(seq_from_head); sequences_start_from_tail_.emplace_back(seq_from_tail); } sequences_start_from_head_for_next_ sequences_start_from_head_; } template typename K, typename V inline std::vectorstd::setK DAGGraphK, V::ConnectedComponents() const { std::vectorstd::setK res; std::unordered_setK visited; for (auto x : bucket_) { std::setK tmp; DFS(x.second.k, visited, tmp); if (!tmp.empty()) { res.emplace_back(tmp); } } std::sort(std::begin(res), std::end(res), [](const std::setK lhs, const std::setK rhs) { return lhs.size() rhs.size(); }); return res; } template typename K, typename V inline void DAGGraphK, V::DFS(const K k, std::unordered_setK* visited, std::setK* connected_components) const { if (visited-count(k)) { return; } visited-emplace(k); connected_components-emplace(k); if (!bucket_.at(k).in.empty()) { for (DAGNodeK, V* v : bucket_.at(k).in) { DFS(v-k, visited, connected_components); } } if (!bucket_.at(k).out.empty()) { for (DAGNodeK, V* v : bucket_.at(k).out) { DFS(v-k, visited, connected_components); } } } template typename K, typename V inline std::vectorK DAGGraphK, V::TopologicalSequence( const std::setK connected_components, bool start_from_head) const { std::mapK, std::vectorK adjacency_list; std::mapK, int32_t in_degree; for (const K key : connected_components) { if (!in_degree.count(key)) { in_degree.emplace(key, 0); } const std::setDAGNodeK, V* nodes start_from_head ? bucket_.at(key).out : bucket_.at(key).in; for (DAGNodeK, V* v : nodes) { adjacency_list[key].emplace_back(v-k); in_degree[v-k]; } } std::queueK q; for (auto x : in_degree) { if (x.second 0) { q.emplace(x.first); } } std::vectorK res; while (!q.empty()) { const K key q.front(); q.pop(); res.emplace_back(key); for (const K k : adjacency_list[key]) { if (--in_degree.at(k) 0) { q.emplace(k); } } } assert(res.size() connected_components.size()); // graph is DAG return res; } } // namespace jc namespace jc::test { class MockPipelineEngine { public: void Start() {} void Stop() {} void Destroy() {} }; void test() { DAGGraphint, std::unique_ptrMockPipelineEngine d; // Make Direct Acyclic Graph: // 0 6 11 13 // / \ | | // 1 3 7 8 12 // | x | \ / // 2 4 9 // \ / | // 5 10 // Traverse each child graph in order whose size smaller // Start Order: // 13 // 6 - 7 // 8 - 11 - 12 - 9 - 10 // 0 - 1 - 3 - 2 - 4 - 5 // Stop Order: // 13 // 7 - 6 // 10 - 9 - 8 - 12 - 11 // 5 - 2 - 4 - 1 - 3 - 0 constexpr int nodes_count 14; for (int i 0; i nodes_count; i) { d[i].reset(new MockPipelineEngine); } assert(d.AddEdge(0, 1)); assert(d.AddEdge(0, 3)); assert(d.AddEdge(1, 2)); assert(d.AddEdge(3, 4)); assert(d.AddEdge(1, 4)); assert(d.AddEdge(3, 2)); assert(d.AddEdge(2, 5)); assert(d.AddEdge(4, 5)); assert(d.AddEdge(6, 7)); assert(d.AddEdge(8, 9)); assert(d.AddEdge(9, 10)); assert(d.AddEdge(11, 12)); assert(d.AddEdge(12, 9)); assert(d.Size() nodes_count); for (int i 0; i nodes_count; i) { assert(d.Exist(i)); } assert(!d.AddEdge(1, 0)); assert(!d.AddEdge(2, 0)); assert(!d.AddEdge(4, 0)); assert(!d.AddEdge(7, 6)); assert(!d.AddEdge(10, 11)); assert(!d.AddEdge(13, 13)); assert(!d.AddEdge(13, 14)); constexpr bool start_from_head true; { std::vectorint v; std::vectorint start_order{ 13, 6, 7, 8, 11, 12, 9, 10, 0, 1, 3, 2, 4, 5 }; std::vectorint start_order2{ 13, 6, 7, 8, 11, 12, 9, 10, 0, 3, 1, 4, 2, 5 }; d.Walk( [](int key, const std::unique_ptrMockPipelineEngine pipeline) { pipeline-Start(); v.emplace_back(key); }, start_from_head); assert(v start_order || v start_order2); } { std::vectorint v; std::vectorint stop_order{ 13, 7, 6, 10, 9, 8, 12, 11, 5, 2, 4, 1, 3, 0 }; std::vectorint stop_order2{ 13, 7, 6, 10, 9, 12, 8, 11, 5, 2, 4, 1, 3, 0 }; d.Walk( [](int key, const std::unique_ptrMockPipelineEngine pipeline) { pipeline-Stop(); v.emplace_back(key); }, !start_from_head); assert(v stop_order || v stop_order2 ); } { std::vectorint v; std::vectorint heads_order{ 13, 6, 8, 11, 0 }; d.WalkHeads( [](int key, const std::unique_ptrMockPipelineEngine pipeline) { pipeline-Destroy(); v.emplace_back(key); }); assert(v heads_order); } { std::vectorint v; std::vectorint tails_order{ 13, 7, 10, 5 }; d.WalkTails( [](int key, const std::unique_ptrMockPipelineEngine pipeline) { pipeline-Destroy(); v.emplace_back(key); }); assert(v tails_order); } { std::vectorint test_sequence{ 13, 6, 7, 0, 1, 3, 4, 2, 5, 8, 11, 12, 9, 10 }; std::unordered_setint heads{ 0, 6, 8, 11, 13 }; assert(d.NextKeys() heads); std::vectorstd::unordered_setint next_keys{ {}, {7}, {}, {1, 3}, {}, {2, 4}, {}, {5}, {}, {}, {12}, {9}, {10}, {}, }; assert(test_sequence.size() nodes_count); assert(next_keys.size() nodes_count); for (int i 0; i nodes_count; i) { assert(d.NextKeys(test_sequence[i]) next_keys[i]); } } d.Clear(); assert(d.Size() 0); for (int i 0; i nodes_count; i) { assert(!d.Exist(i)); } } } // namespace jc::test //int main() { jc::test::test(); }效果