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

2024-08-20 21:36
文章标签 算法 c++ 有向图 排序 拓扑

本文主要是介绍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::set<DAGNode<K, V>*> in;std::set<DAGNode<K, 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::function<void(const K& k, const V& v)> f,bool start_from_head = true);void WalkHeads(std::function<void(const K& k, const V& v)> f);void WalkTails(std::function<void(const K& k, const V& v)> f);std::unordered_set<K> NextKeys();std::unordered_set<K> NextKeys(const K& key);private:bool IsCyclic(const DAGNode<K, V>& from, const DAGNode<K, V>& to) const;void RefreshWalkSequences();std::vector<std::set<K>> ConnectedComponents() const;void DFS(const K& k, std::unordered_set<K>* visited,std::set<K>* connected_components) const;std::vector<K> TopologicalSequence(const std::set<K>& connected_components,bool start_from_head) const;private:std::map<K, DAGNode<K, V>> bucket_;std::unordered_set<K> heads_;std::unordered_set<K> tails_;std::vector<std::vector<K>> sequences_start_from_head_;std::vector<std::vector<K>> sequences_start_from_tail_;private:bool allow_modify_ = true;std::vector<std::vector<K>> sequences_start_from_head_for_next_;std::unordered_set<K> current_heads_for_next_;};template <typename K, typename V>inline bool DAGGraph<K, 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& DAGGraph<K, 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 DAGGraph<K, V>::Exist(const K& key) const {return bucket_.count(key);}template <typename K, typename V>inline void DAGGraph<K, 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 DAGGraph<K, V>::Size() const {return bucket_.size();}template <typename K, typename V>inline void DAGGraph<K, V>::Walk(std::function<void(const K& k, const V& v)> f,bool start_from_head) {if (sequences_start_from_head_.empty()) {RefreshWalkSequences();}const std::vector<std::vector<K>>& seqs_to_walk =start_from_head ? sequences_start_from_head_ : sequences_start_from_tail_;for (const std::vector<K>& seq : seqs_to_walk) {std::for_each(std::begin(seq), std::end(seq), [&](const K& key) {const DAGNode<K, V>& node = bucket_.at(key);f(node.k, node.v);});}}template <typename K, typename V>inline void DAGGraph<K, V>::WalkHeads(std::function<void(const K& k, const V& v)> f) {if (sequences_start_from_head_.empty()) {RefreshWalkSequences();}for (const std::vector<K>& seq : sequences_start_from_head_) {std::for_each(std::begin(seq), std::end(seq), [&](const K& key) {if (heads_.count(key)) {const DAGNode<K, V>& node = bucket_.at(key);f(node.k, node.v);}});}}template <typename K, typename V>inline void DAGGraph<K, V>::WalkTails(std::function<void(const K& k, const V& v)> f) {if (sequences_start_from_head_.empty()) {RefreshWalkSequences();}for (const std::vector<K>& seq : sequences_start_from_tail_) {std::for_each(std::begin(seq), std::end(seq), [&](const K& key) {if (tails_.count(key)) {const DAGNode<K, V>& node = bucket_.at(key);f(node.k, node.v);}});}}template <typename K, typename V>inline std::unordered_set<K> DAGGraph<K, 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_set<K> DAGGraph<K, V>::NextKeys(const K& key) {assert(!allow_modify_);  // must call NextKeys() beforeassert(current_heads_for_next_.count(key));current_heads_for_next_.erase(key);std::unordered_set<K> res;for (std::vector<K>& 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::set<DAGNode<K, V>*>& nodes = bucket_.at(key).out;for (DAGNode<K, V>* v : nodes) {const std::set<DAGNode<K, V>*>& prev_nodes = v->in;bool no_prev_node_in_seq =std::all_of(std::begin(prev_nodes), std::end(prev_nodes),[&](DAGNode<K, 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 DAGGraph<K, V>::IsCyclic(const DAGNode<K, V>& from,const DAGNode<K, V>& to) const {std::queue<DAGNode<K, V>*> q;for (DAGNode<K, V>* v : from.in) {q.emplace(v);}std::unordered_set<DAGNode<K, V>*> visited;while (!q.empty()) {DAGNode<K, V>* node = q.front();q.pop();if (visited.count(node)) {continue;}if (node == &to) {return true;}visited.emplace(node);for (DAGNode<K, V>* v : node->in) {q.emplace(v);}}return false;}template <typename K, typename V>inline void DAGGraph<K, V>::RefreshWalkSequences() {sequences_start_from_head_.clear();sequences_start_from_tail_.clear();const std::vector<std::set<K>> connected_components = ConnectedComponents();for (const std::set<K>& x : connected_components) {const std::vector<K> seq_from_head = TopologicalSequence(x, true);const std::vector<K> 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::vector<std::set<K>> DAGGraph<K, V>::ConnectedComponents() const {std::vector<std::set<K>> res;std::unordered_set<K> visited;for (auto& x : bucket_) {std::set<K> tmp;DFS(x.second.k, &visited, &tmp);if (!tmp.empty()) {res.emplace_back(tmp);}}std::sort(std::begin(res), std::end(res),[&](const std::set<K>& lhs, const std::set<K>& rhs) {return lhs.size() < rhs.size();});return res;}template <typename K, typename V>inline void DAGGraph<K, V>::DFS(const K& k, std::unordered_set<K>* visited,std::set<K>* connected_components) const {if (visited->count(k)) {return;}visited->emplace(k);connected_components->emplace(k);if (!bucket_.at(k).in.empty()) {for (DAGNode<K, V>* v : bucket_.at(k).in) {DFS(v->k, visited, connected_components);}}if (!bucket_.at(k).out.empty()) {for (DAGNode<K, V>* v : bucket_.at(k).out) {DFS(v->k, visited, connected_components);}}}template <typename K, typename V>inline std::vector<K> DAGGraph<K, V>::TopologicalSequence(const std::set<K>& connected_components, bool start_from_head) const {std::map<K, std::vector<K>> adjacency_list;std::map<K, int32_t> in_degree;for (const K& key : connected_components) {if (!in_degree.count(key)) {in_degree.emplace(key, 0);}const std::set<DAGNode<K, V>*>& nodes =start_from_head ? bucket_.at(key).out : bucket_.at(key).in;for (DAGNode<K, V>* v : nodes) {adjacency_list[key].emplace_back(v->k);++in_degree[v->k];}}std::queue<K> q;for (auto& x : in_degree) {if (x.second == 0) {q.emplace(x.first);}}std::vector<K> 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 DAGreturn res;}}  // namespace jcnamespace jc::test {class MockPipelineEngine {public:void Start() {}void Stop() {}void Destroy() {}};void test() {DAGGraph<int, std::unique_ptr<MockPipelineEngine>> 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 -> 0constexpr 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::vector<int> v;std::vector<int> start_order{ 13, 6, 7, 8, 11, 12, 9, 10, 0, 1, 3, 2, 4, 5 };std::vector<int> start_order2{ 13, 6, 7, 8, 11, 12, 9, 10, 0, 3, 1, 4, 2, 5 };d.Walk([&](int key, const std::unique_ptr<MockPipelineEngine>& pipeline) {pipeline->Start();v.emplace_back(key);},start_from_head);assert(v == start_order || v == start_order2);}{std::vector<int> v;std::vector<int> stop_order{ 13, 7, 6, 10, 9, 8, 12, 11, 5, 2, 4, 1, 3, 0 };std::vector<int> stop_order2{ 13, 7, 6, 10, 9, 12, 8, 11, 5, 2, 4, 1, 3, 0 };d.Walk([&](int key, const std::unique_ptr<MockPipelineEngine>& pipeline) {pipeline->Stop();v.emplace_back(key);},!start_from_head);assert(v == stop_order || v == stop_order2);}{std::vector<int> v;std::vector<int> heads_order{ 13, 6, 8, 11, 0 };d.WalkHeads([&](int key, const std::unique_ptr<MockPipelineEngine>& pipeline) {pipeline->Destroy();v.emplace_back(key);});assert(v == heads_order);}{std::vector<int> v;std::vector<int> tails_order{ 13, 7, 10, 5 };d.WalkTails([&](int key, const std::unique_ptr<MockPipelineEngine>& pipeline) {pipeline->Destroy();v.emplace_back(key);});assert(v == tails_order);}{std::vector<int> test_sequence{ 13, 6, 7, 0,  1,  3, 4,2,  5, 8, 11, 12, 9, 10 };std::unordered_set<int> heads{ 0, 6, 8, 11, 13 };assert(d.NextKeys() == heads);std::vector<std::unordered_set<int>> 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(); }
效果

 

这篇关于C++ 有向图拓扑排序算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1091239。

相关文章

c++ 类成员变量默认初始值的实现

c++ 类成员变量默认初始值的实现

《c++类成员变量默认初始值的实现》本文主要介绍了c++类成员变量默认初始值,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录C++类成员变量初始化c++类的变量的初始化在C++中，如果使用类成员变量时未给定其初始值，那么它将被
阅读更多...
C++中NULL与nullptr的区别小结

C++中NULL与nullptr的区别小结

《C++中NULL与nullptr的区别小结》本文介绍了C++编程中NULL与nullptr的区别,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编... 目录C++98空值——NULLC++11空值——nullptr区别对比示例 C++98空值——NUL
阅读更多...
C++ Log4cpp跨平台日志库的使用小结

C++ Log4cpp跨平台日志库的使用小结

《C++Log4cpp跨平台日志库的使用小结》Log4cpp是c++类库,本文详细介绍了C++日志库log4cpp的使用方法,及设置日志输出格式和优先级,具有一定的参考价值,感兴趣的可以了解一下... 目录一、介绍1. log4cpp的日志方式2.设置日志输出的格式3. 设置日志的输出优先级二、Window
阅读更多...
Java中的雪花算法Snowflake解析与实践技巧

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.
阅读更多...
从入门到精通C++11 ＜chrono＞ 库特性

从入门到精通C++11 ＜chrono＞ 库特性

《从入门到精通C++11＜chrono＞库特性》chrono库是C++11中一个非常强大和实用的库,它为时间处理提供了丰富的功能和类型安全的接口,通过本文的介绍,我们了解了chrono库的基本概念... 目录一、引言1.1 为什么需要<chrono>库1.2<chrono>库的基本概念二、时间段（Durat
阅读更多...
C++20管道运算符的实现示例

C++20管道运算符的实现示例

《C++20管道运算符的实现示例》本文简要介绍C++20管道运算符的使用与实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录标准库的管道运算符使用自己实现类似的管道运算符我们不打算介绍太多，因为它实际属于c++20最为重要的
阅读更多...
Visual Studio 2022 编译C++20代码的图文步骤

Visual Studio 2022 编译C++20代码的图文步骤

《VisualStudio2022编译C++20代码的图文步骤》在VisualStudio中启用C++20import功能,需设置语言标准为ISOC++20,开启扫描源查找模块依赖及实验性标... 默认创建Visual Studio桌面控制台项目代码包含C++20的import方法。右键项目的属性：
阅读更多...
c++中的set容器介绍及操作大全

c++中的set容器介绍及操作大全

《c++中的set容器介绍及操作大全》：本文主要介绍c++中的set容器介绍及操作大全,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录​​一、核心特性​​️ ​​二、基本操作​​​​1. 初始化与赋值​​​​2. 增删查操作​​​​3. 遍历方
阅读更多...
解析C++11 static_assert及与Boost库的关联从入门到精通

解析C++11 static_assert及与Boost库的关联从入门到精通

《解析C++11static_assert及与Boost库的关联从入门到精通》static_assert是C++中强大的编译时验证工具,它能够在编译阶段拦截不符合预期的类型或值,增强代码的健壮性,通... 目录一、背景知识：传统断言方法的局限性1.1 assert宏1.2 #error指令1.3 第三方解决
阅读更多...
C++11委托构造函数和继承构造函数的实现

C++11委托构造函数和继承构造函数的实现

《C++11委托构造函数和继承构造函数的实现》C++引入了委托构造函数和继承构造函数这两个重要的特性,本文主要介绍了C++11委托构造函数和继承构造函数的实现,具有一定的参考价值,感兴趣的可以了解一下... 目录引言一、委托构造函数1.1 委托构造函数的定义与作用1.2 委托构造函数的语法1.3 委托构造函
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2