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 |
|---|
