CXXGraph
v4.1.0
CXXGraph是一个管理图算法的综合 C++ 库。这个仅包含头文件的库可作为 Boost Graph Library (BGL) 的替代方案。
我们正在寻找：
如果您有兴趣，请通过 [email protected] 联系我们或为该项目做出贡献。我们正在等你！
| 完全的 | 描述 | 完成日期 |
|---|---|---|
| ✔️ | 版本0.4.0 | 2022 年 10 月 7 日 |
| ✔️ | 版本0.5.0 | 2023 年 3 月 23 日 |
| ✔️ | 第一个稳定版本 1.0.0 | 2023 年 3 月 28 日 |
| ✔️ | 版本1.0.1 | 2023 年 5 月 7 日 |
| ✔️ | 版本1.1.0 | 2023 年 5 月 8 日 |
| ✔️ | 稳定版2.0.0 | 2023 年 6 月 1 日 |
| ✔️ | 稳定版3.0.0 | 2023 年 11 月 3 日 |
| ✔️ | 版本3.1.0 | 2023 年 1 月 9 日 |
| 引入超图 #122 | 待定 | |
| 稳定版 4.0.0 | 待定 |
要在 Unix/Linux 系统上安装，请从命令行执行以下命令：
$ sudo tar xjf CXXGraph-{version}.tar.bz2
卸载：
$ sudo rm -f /usr/include/Graph.hpp /usr/include/CXXGraph*
要在 Fedora/CentOS/RedHat 系统上安装，请从命令行执行以下命令：
$ sudo rpm -ivh CXXGraph-{version}.noarch.rpm
卸载：
$ sudo rpm -e CXXGraph-{version}
要在 Debian/Ubuntu 系统上安装，请从命令行执行以下命令：
$ sudo dpkg -i CXXGraph_{version}.deb
卸载：
$ sudo apt-get remove CXXGraph
对于使用 CMake 的自编译安装，编译完成后从命令行执行以下命令：
$ sudo make install
类说明可以在 Doxygen 文档的类部分找到
要使用该库，只需将头文件放在需要的位置即可。就是这么简单！
正在进行的工作
单元测试需要 CMake 3.9 及更高版本以及GoogleTest库。
谷歌测试
git clone https://github.com/google/googletest.git
cd googletest # Main directory of the cloned repository
mkdir -p build # Create a directory to hold the build output
cd build
cmake .. # Generate native build scripts for GoogleTest
make # Compile
sudo make install # Install in /usr/local/ by default从基本目录：
mkdir -p build # Create a directory to hold the build output
cd build # Enter the build folder
cmake -DTEST=ON .. # Generate native build scripts for GoogleTest,
make # Compile编译构建后，使用以下命令运行“build”目录中的“test_exe”可执行文件：
./test_exe
Benchmark 需要 CMake 3.9 及更高版本、 GoogleTest库和Google Benchmark库。
谷歌基准测试
# Check out the library
$ git clone https://github.com/google/benchmark.git
# Google Benchmark requires GoogleTest as a dependency. Add the source tree as a subdirectory
$ git clone https://github.com/google/googletest.git benchmark/googletest
# Go to the library's root directory
$ cd benchmark
# Make a build directory to place the build output
$ cmake -E make_directory " build "
# Generate the build system files with CMake
$ cmake -E chdir " build " cmake -DCMAKE_BUILD_TYPE=Release ../
# If starting with CMake 3.13, you can use the following:
# cmake -DCMAKE_BUILD_TYPE=Release -S . -B "build"
# Build the library
$ cmake --build " build " --config Release
# Install the library
$ sudo cmake --build " build " --config Release --target install从基本目录：
mkdir -p build # Create a directory to hold the build output
cd build # Enter the build folder
cmake -DBENCHMARK=ON .. # Generate native build scripts for Google Benchmark
make # Compile编译构建后，使用以下命令运行“build”目录中的“benchmark”可执行文件：
./benchmark
您可以使用此链接检查基准测试结果。
要创建 tarball 包，请从命令行执行以下命令：
# Enter Packaging Directory
$ cd packaging
# Execute the script to generate tarballs
$ ./tarballs.sh要创建 RPM 包，请从命令行执行以下命令：
# Enter Packaging Directory
$ cd packaging/rpm
# Execute the script to generate tarballs
$ ./make_rpm.sh要创建 deb 包，请从命令行执行以下命令：
# Enter Packaging Directory
$ cd packaging/deb
# Execute the script to generate tarballs
$ ./make_deb.sh图Dijkstras最短路径算法（Dijkstra's Shortest Path） 【Dijkstra算法】 （https://www.interviewbit.com/blog/find-shortest-path-dijkstras-algorithm/）用于查找从源节点到图中的所有其他可到达的节点。该算法最初假设所有节点都无法从给定的源节点到达，因此我们将所有节点的距离标记为无穷大。 （无穷大）来自源节点（INF/无穷大表示无法到达）。
Dijkstra 算法的 Dial 专业化。
当边权重是小整数（受参数C限制）时，利用这一事实的专用队列可用于加速 Dijkstra 算法。这种类型的第一个算法是 Dial 算法（Dial 1969），用于具有正整数边权重的图，该算法使用桶队列来获得运行时间O(|E|+|V|C) 。（来源维基百科）
下面是完整的算法：
在此链接中您可以找到分步说明。
Prim 算法 Prim 算法是一种贪心算法，可为带权无向图找到最小生成树。这意味着它找到形成包含每个顶点的树的边的子集，其中树中所有边的总权重最小化。该算法的运行方式是：从任意起始顶点开始，每次构建一个顶点，在每一步添加从树到另一个顶点的最便宜的可能连接。
步骤：
(广度优先搜索) 广度优先搜索算法(Breadth First Search)广度优先搜索，也称为BFS ，是一种图遍历算法。时间复杂度 O(|V| + |E|)，其中 V 是图中的顶点数，E 是图中的边数。广度优先搜索的应用有：
还有更多...
（深度优先搜索） 深度优先搜索算法（深度优先搜索）深度优先搜索，也称为DFS ，是一种图遍历算法。时间复杂度 O(|V| + |E|)，其中 V 是图中的顶点数，E 是图中的边数。深度优先搜索的应用有：
还有更多...
最佳优先搜索 最佳优先搜索是一类搜索算法，它通过探索根据评估函数选择的最有希望的节点来遍历图。最坏情况的时间复杂度为 O(n * log n)，其中 n 是图中的节点数。
循环（图论）
有向图和无向图中环的存在可以通过深度优先搜索（DFS）是否找到指向当前顶点的祖先的边（它包含后边）来确定。 DFS 跳过的所有后沿都是循环的一部分。在无向图中，到节点父节点的边不应被算作后边，但找到任何其他已访问过的顶点将指示后边。在无向图的情况下，在 n 顶点图中找到循环只需要 O(n) 时间，因为最多 n − 1 条边可以是树边。
许多拓扑排序算法也会检测循环，因为它们是拓扑顺序存在的障碍。此外，如果有向图被划分为强连通分量，则循环仅存在于分量内部，而不存在于分量之间，因为循环是强连通的。
对于有向图，可以使用基于分布式消息的算法。这些算法依赖于这样的想法：循环中顶点发送的消息将返回到自身。分布式循环检测算法对于在计算机集群（或超级计算机）上使用分布式图处理系统处理大规模图非常有用。
循环检测的应用包括使用等待图来检测并发系统中的死锁。
Bellman-Ford 算法可用于查找源节点和目标节点之间的最短距离。时间复杂度 O(|V| . |E|)，其中 V 是图中的顶点数，E 是图中的边数，高于 Dijkstra 的最短路径算法。 dijkstra算法的时间复杂度为O(|E| + |V| log |v| )。 Bellman-Ford 相对于 Dijkstra 的优势在于它可以处理具有负边权重的图。此外，如果图表包含负权循环，则算法可以检测并报告负循环的存在。
该视频很好地概述了算法的实现。麻省理工学院的这次演讲证明了贝尔曼-福特的正确性及其检测负循环的能力。应用：
弗洛伊德·沃歇尔算法
作为第一步，我们初始化与输入图矩阵相同的解矩阵。然后我们通过将所有顶点视为中间顶点来更新解矩阵。其思想是一一选取所有顶点并更新所有最短路径，其中包括选取的顶点作为最短路径中的中间顶点。当我们选择顶点编号 k 作为中间顶点时，我们已经将顶点 {0, 1, 2, .. k-1} 视为中间顶点。对于每对 (i, j) 源顶点和目标顶点，有两种可能的情况。
传递归约
该算法用于构造一个具有相同可达性且满足传递闭包、边数尽可能少的有向图。更具体地说，它创建一个具有尽可能少边的最小等效图，从而消除了穿过该图的“短路”路径。
这是通过迭代每个节点对来完成的，检查是否存在从第一个节点或最后一个节点引出的两条边，如果存在则删除节点对边。
在伪代码中： foreach x in graph.vertices foreach y in graph.vertices foreach z in graph.vertices 如果边 xy 和 yz 存在，则删除边 xz
我们的实现具有 if 门，可以在多个位置对边缘进行早期检查，这使其运行时间比此处的三次伪代码稍快。
Kruskal 算法可用于查找无向边加权图的最小生成森林。时间复杂度 O(E log E) = O(E log V)，其中 V 是图中的顶点数，E 是图中的边数。该算法的主要速度限制是对边缘进行排序。
要快速了解算法过程，请观看此视频。一些现实生活中的应用是：
其他寻找最小生成森林的算法有 Prim 算法或 Borůvka 算法。
Borůvka 算法是一种贪心算法，可用于在图中查找最小生成树，或者在图不连通的情况下查找最小生成林。
该算法首先找到与图的每个顶点相关的最小权重边，并将所有这些边添加到森林中。然后，它重复类似的过程，从迄今为止构建的每棵树到另一棵树中找到最小权重边，并将所有这些边添加到森林中。此过程的每次重复都会将图的每个连接组件内的树数量减少到最多前一个值的一半，因此在对数次重复之后，该过程完成。当它这样做时，它添加的边集形成最小生成森林。
Borůvka 的算法可以显示为外循环进行 O(log V) 次迭代直至终止，因此运行时间为 O(E log V)，其中 E 是边数，V 是循环中的顶点数G（假设 E ≥ V）。
问题的数学定义：设 G 为图中的节点集合，n 为该集合中的给定节点。令 C 为 G 的非严格子集，包含 n 和从 n 可达的所有节点，并令 C' 为其补集。还有第三个集合 M，它是 C 的非严格子集，包含可从 C' 中的任何节点到达的所有节点。问题包括找到属于 C 但不属于 M 的所有节点。
目前实施的算法：
应用：
该算法用于垃圾收集系统，以在一个对象即将被释放的情况下决定需要释放哪些其他对象。
Ford-Fulkerson 算法是一种用于在流网络中寻找最大流的贪心算法。该算法背后的思想如下：只要存在从源（起始节点）到汇点（结束节点）的路径，并且路径中所有边上都有可用容量，我们就沿着其中一条路径发送流量。然后我们找到另一条路，依此类推。具有可用容量的路径称为增广路径。
Kosaraju 算法是一种线性时间算法，用于查找有向图的强连通分量。它基于这样的想法：如果一个人能够从顶点 u 开始到达顶点 v，那么一个人应该能够从顶点 v 开始到达顶点 u，如果是这种情况，我们可以说顶点 u 和 v 是强连接 - 它们位于强连接子图中。下面是一个例子：
1）。创建一个空堆栈“S”并对图进行 DFS 遍历。在DFS遍历中，对某个顶点的相邻顶点调用递归DFS后，将该顶点压入堆栈。 2）。将所有弧的方向反转以获得转置图。 3）。当S不为空时，从S中一一弹出一个顶点。令弹出的顶点为“v”。以 v 作为源并进行 DFS（调用 DFSUtil(v)）。从 v 开始的 DFS 打印 v 的强连通分量。
卡恩算法通过迭代删除图中没有传入边的节点来找到拓扑排序。当从图中删除节点时，它将添加到拓扑排序中，并且删除其所有边，从而允许选择没有传入边的下一组节点。
威尔士鲍威尔着色算法是一种贪婪的顶点着色算法。该算法也用于查找图的色数。
威尔士鲍威尔算法包括以下步骤：
该算法返回一个 std::map<Node, int> 结果，该结果将每个节点分配给按整数排序的颜色。用户还可以通过查询结果图中的最高值来查询图的最小色阶。
std::map<Node, int > result = graph.welshPowellColoring();
auto chromatic_color = std::max_element(result.begin(), result.end(),
[]( const auto & lhs, const auto & rhs) {
return lhs. second < rhs. second ;
}最小着色从 1 开始，而不是从 0 开始。
该算法假设图是无向的。所有的来源和灵感都链接在算法和测试用例的声明中。
顶点切割分区将图的边划分为大小相等的分区。保存边端点的顶点也放置在与边本身相同的分区中。但是，顶点在分区之间并不唯一，并且由于其边分布在不同的分区上，因此可能必须复制（剪切）。
复制因子量化了与原始输入图的顶点数量相比，通过计算机复制的顶点数量。
该算法是循环方式中的简单顶点切割。它获取原始图的边并将它们分配给分区，将其划分为相等（或相似）的大小。该算法不考虑顶点复制（复制因子）的优化，而仅平衡分区中的边。
贪婪分区算法使用边缘分配的整个历史来做出下一个决策。该算法存储每个已观察到的顶点 v 已分配到的分区集 A(v) 以及当前分区大小。当处理连接顶点 vi, vj ∈ V 的边 e ∈ E 时，贪心算法遵循以下一组简单的规则：
高度（are）复制优先（HDRF）算法是本文描述的一种贪婪顶点切割算法。该算法尝试通过使用边缘分配的历史记录和增量顶点度数来优化复制因子。使用考虑这两个因素的函数计算分配分析边缘的最佳分区。创建的副本是基于顶点的度数的，复制的顶点可能是所谓的“Hub-Node”，即度数较高的顶点。
高效平衡顶点切割（EBV）是本文描述的一种离线顶点切割算法。该算法尝试根据每个分区的边数和顶点数以及复制因子来平衡分区。它应用一个公式来评估分配边的分区，同时还考虑图的边和顶点的总数。评价公式如下：
取最小值作为分区Id。
度矩阵是一个方阵，可深入了解图中节点的连接性。对于有向图，它反映每个节点的传入和传出边的数量，而对于无向图，它表示关联到每个节点的边的数量。
拉普拉斯矩阵是从图的邻接矩阵和度矩阵导出的方阵。它有助于分析图的各种属性，例如连通性、生成树的计数以及其他频谱特征。
转移矩阵通常用于马尔可夫链和随机过程的研究。在图的上下文中，它表示从一个节点转换到另一个节点的概率，通常基于边权重或预定标准。该矩阵在网络分析、机器学习和优化等各个领域都有应用。
如果您想提供支持，您可以创建拉取请求或报告问题。如果您想更改代码、解决问题或实现新功能，请阅读我们的贡献指南。
如果您想讨论新功能或者对库有任何疑问或建议，请打开讨论或简单地聊天
CXXGraph 站点
电子邮件：[email protected]
GitHub 简介
为了支持我，请为项目添加星星或关注我
要了解最新动态，请观看该项目
我们被引用：
感谢 TheAlgorithms 社区提供的一些算法灵感。
感谢 GeeksForGeeks 提供的一些算法灵感。
感谢所有已经为 CXXGraph 做出贡献的人们！
如果您使用此软件，请遵循 CITATION 说明。谢谢你！
我们参加了 Hacktoberfest 2021。感谢所有贡献者！
我们参加了 Hacktoberfest 2022。感谢所有贡献者！
我们参加了 Hacktoberfest 2023。感谢所有贡献者！
查看项目的估计价值
@ZigRazor |
|---|
