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ライブラリが必要です。
Googleテスト
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
ベンチマークには、CMake 3.9 以降、 GoogleTestライブラリ、およびGoogle Benchmarkライブラリが必要です。
Google ベンチマーク
# 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.shRPM パッケージを作成するには、コマンド ラインから次のコマンドを実行します。
# Enter Packaging Directory
$ cd packaging/rpm
# Execute the script to generate tarballs
$ ./make_rpm.shdeb パッケージを作成するには、コマンド ラインから次のコマンドを実行します。
# Enter Packaging Directory
$ cd packaging/deb
# Execute the script to generate tarballs
$ ./make_deb.shグラフ ダイクストラ最短パス アルゴリズム (ダイクストラの最短パス) [ダイクストラのアルゴリズム] (https://www.interviewbit.com/blog/find-shortest-path-dijkstras-algorithm/) は、ソース ノードからノードへの最短パスを見つけるために使用されます。グラフ内の他のすべての到達可能なノード。アルゴリズムは最初に、指定されたソース ノードからすべてのノードが到達不可能であると想定するため、すべてのノードの距離を無限大としてマークします。ソースノードからの (無限大) (INF / 無限大は到達できないことを示します)。
ダイクストラアルゴリズムのダイヤル特化。
エッジの重みが小さい整数 (パラメーターCによって制限される) の場合、この事実を利用する特殊なキューを使用して、ダイクストラのアルゴリズムを高速化できます。このタイプの最初のアルゴリズムは、正の整数エッジ重みを持つグラフ用の Dial のアルゴリズム (Dial 1969) で、バケット キューを使用して実行時間O(|E|+|V|C)を取得します。(出典 wikipedia)
以下は完全なアルゴリズムです。
このリンクでは、ステップバイステップの図を見つけることができます。
プリムのアルゴリズム プリムのアルゴリズムは、重み付き無向グラフの最小スパニング ツリーを見つける貪欲なアルゴリズムです。これは、ツリー内のすべてのエッジの合計重みが最小化される、すべての頂点を含むツリーを形成するエッジのサブセットを見つけることを意味します。このアルゴリズムは、任意の開始頂点から一度に 1 頂点ずつこのツリーを構築し、各ステップでツリーから別の頂点への可能な限り安価な接続を追加することによって動作します。
手順:
(幅優先検索) 幅優先検索アルゴリズム(幅優先検索) BFSとも呼ばれる幅優先検索 は、グラフ トラバーサル アルゴリズムです。時間計算量 O(|V| + |E|) ここで、V はグラフ内の頂点の数、E はエッジの数です。幅優先検索のアプリケーションは次のとおりです。
他にもたくさんあります...
(深さ優先検索) 深さ優先検索アルゴリズム (深さ優先検索) DFSとも呼ばれる深さ優先検索は、グラフ トラバーサル アルゴリズムです。時間計算量 O(|V| + |E|) ここで、V はグラフ内の頂点の数、E はエッジの数です。深さ優先検索のアプリケーションは次のとおりです。
他にもたくさんあります...
Best First Search Best First Search は、評価関数に従って選択された最も有望なノードを探索することによってグラフを横断する検索アルゴリズムのクラスです。最悪の場合の時間計算量は O(n * log n) です。ここで、n はグラフ内のノードの数です。
サイクル（グラフ理論）
有向グラフおよび無向グラフにおけるサイクルの存在は、深さ優先検索 (DFS) が現在の頂点の祖先 (バック エッジを含む) を指すエッジを見つけるかどうかによって判断できます。 DFS がスキップするすべてのバック エッジはサイクルの一部です。無向グラフでは、ノードの親へのエッジはバック エッジとしてカウントされるべきではありませんが、既に訪問した他の頂点が見つかるとバック エッジが示されます。無向グラフの場合、ツリー エッジになり得るエッジは最大でも n − 1 個であるため、n 頂点グラフ内のサイクルを見つけるのに必要な時間は O(n) のみです。
多くのトポロジカルソートアルゴリズムはサイクルも検出します。サイクルはトポロジカルな順序が存在するための障害となるためです。また、有向グラフが強く接続されたコンポーネントに分割されている場合、サイクルは強く接続されているため、サイクルはコンポーネント内にのみ存在し、コンポーネント間には存在しません。
有向グラフの場合、分散メッセージベースのアルゴリズムを使用できます。これらのアルゴリズムは、サイクル内の頂点によって送信されたメッセージは自分自身に戻ってくるという考えに基づいています。分散サイクル検出アルゴリズムは、コンピューター クラスター (またはスーパーコンピューター) 上の分散グラフ処理システムを使用して大規模なグラフを処理する場合に役立ちます。
サイクル検出のアプリケーションには、同時システムでのデッドロックを検出するための待機グラフの使用が含まれます。
Bellman-Ford アルゴリズムを使用して、ソース ノードとターゲット ノード間の最短距離を見つけることができます。時間計算量 O(|V| . |E|) ここで、V はグラフ内の頂点の数、E はダイクストラの最短経路アルゴリズムよりも高いエッジの数です。ダイクストラのアルゴリズムの時間計算量は O(|E| + |V| log |v| ) です。ダイクストラに対する bellman-ford の利点は、負のエッジの重みを持つグラフを処理できることです。さらに、グラフに負の重みサイクルが含まれている場合、アルゴリズムは負のサイクルの存在を検出して報告できます。
このビデオでは、アルゴリズムの実装の概要をわかりやすく説明します。この MIT の講義では、ベルマン フォードの正しさと負のサイクルを検出する能力の証明を示します。アプリケーション:
フロイド・ウォーシャルのアルゴリズム
最初のステップとして、入力グラフ行列と同じソリューション行列を初期化します。次に、すべての頂点を中間頂点とみなして解行列を更新します。このアイデアは、すべての頂点を 1 つずつ選択し、選択した頂点を最短パスの中間頂点として含むすべての最短パスを更新することです。頂点番号 k を中間頂点として選択すると、頂点 {0, 1, 2, .. k-1} がすでに中間頂点として考慮されています。ソース頂点とターゲット頂点の各ペア (i, j) ごとに、2 つのケースが考えられます。
推移的還元
このアルゴリズムは、同じ到達可能性を備え、可能な限り少ないエッジで推移閉包を満たす有向グラフを構築するために使用されます。より具体的には、可能な限りエッジの少ない最小の等価グラフを作成し、グラフ内の「短絡」パスを削除します。
これは、各ノード ペアを反復処理し、最初のノードから出るか、最後のノードから出る 2 つのエッジが存在するかどうかを確認し、存在する場合はノード ペア エッジを削除することによって行われます。
疑似コード: foreach x ingraph.vertices foreach y ingraph.vertices foreach z ingraph.vertices エッジ xy と yz が存在する場合、エッジ xz を削除します。
私たちの実装には、複数の場所でエッジの早期チェックを行う if ゲートがあり、これにより、ここでの 3 次疑似コードよりも実行時間がわずかに速くなります。
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 を、n と n から到達可能なすべてのノードの両方を含む G の非厳密なサブセットとし、C' をその補数とします。 3 番目のセット M があります。これは、C' 内の任意のノードから到達可能なすべてのノードを含む C の非厳密なサブセットです。この問題は、C に属するが M には属さないすべてのノードを見つけることで構成されます。
現在実装されているアルゴリズム:
応用：
このアルゴリズムは、ガベージ コレクション システムで、1 つのオブジェクトが解放されようとしている場合に、他のどのオブジェクトを解放する必要があるかを決定するために使用されます。
Ford-Fulkerson アルゴリズムは、フロー ネットワーク内の最大フローを見つけるための貪欲なアルゴリズムです。このアルゴリズムの背後にある考え方は次のとおりです。ソース (開始ノード) からシンク (終了ノード) までのパスが存在し、パス内のすべてのエッジに利用可能な容量がある限り、いずれかのパスに沿ってフローを送信します。次に、別の道を見つける、というように続きます。使用可能な容量のあるパスは、拡張パスと呼ばれます。
コサラジュのアルゴリズムは、有向グラフの強く接続されたコンポーネントを見つけるための線形時間アルゴリズムです。これは、頂点 u から開始して頂点 v に到達できるのであれば、頂点 v から開始して頂点 u に到達できるはずであり、そのような場合、頂点 u と v は次のように言えるという考えに基づいています。強く接続されている - それらは強く接続されたサブグラフ内にあります。以下に例を示します。
1)。空のスタック「S」を作成し、グラフの DFS 走査を実行します。 DFS トラバーサルでは、頂点の隣接する頂点に対して再帰的 DFS を呼び出した後、頂点をスタックにプッシュします。 2)。すべての円弧の方向を逆にして、転置グラフを取得します。 3)。 S が空ではない間に、S から頂点を 1 つずつポップします。ポップされた頂点を「v」とします。 v をソースとして取得し、DFS を実行します (DFSUtil(v) を呼び出します)。 v から始まる DFS は、v の強結合成分を出力します。
カーンのアルゴリズムは、グラフ内の入力エッジを持たないノードを繰り返し削除することによって、トポロジカルな順序を見つけます。ノードがグラフから削除されると、そのノードはトポロジー順序付けに追加され、そのすべてのエッジが削除され、入力エッジのない次のノードのセットが選択できるようになります。
Welsh Powell カラーリング アルゴリズムは、貪欲な頂点カラーリング アルゴリズムです。このアルゴリズムは、グラフの彩色番号を見つけるためにも使用されます。
ウェルシュ パウエル アルゴリズムは次のステップで構成されます。
このアルゴリズムは、各ノードを整数順の色に割り当てる 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 ;
}最小の色付けは 0 ではなく 1 から始まります。
このアルゴリズムは、グラフが無向であることを前提としています。すべてのソースとインスピレーションは、アルゴリズムとテスト ケースの宣言にリンクされています。
頂点カット パーティショニングは、グラフのエッジを同じサイズのパーティションに分割します。エッジの端点を保持する頂点も、エッジ自体と同じパーティションに配置されます。ただし、頂点はパーティション間で一意ではないため、異なるパーティション間でのエッジの分布により、複製 (切り取り) が必要になる場合があります。
レプリケーション係数は、元の入力グラフの頂点の数と比較して、コンピューター上で複製された頂点の数を定量化します。
このアルゴリズムは、ラウンドロビン方式の単純な頂点カットです。元のグラフのエッジを取得してパーティションに割り当て、等しい（または同様の）サイズに分割します。このアルゴリズムは、頂点レプリケーション (レプリケーション係数) の最適化には対応せず、パーティション内のエッジのバランスを取るだけです。
貪欲な分割アルゴリズムは、エッジ割り当ての履歴全体を使用して次の決定を行います。このアルゴリズムは、すでに観測されている各頂点 v が割り当てられているパーティション A(v) のセットと現在のパーティション サイズを保存します。頂点 vi、vj ∈ V を接続するエッジ e ∈ E を処理する場合、貪欲アルゴリズムは次の単純なルール セットに従います。
High Degree (are) Replicated First(HDRF) アルゴリズムは、この論文で説明されている貪欲な頂点カット アルゴリズムです。このアルゴリズムは、エッジ割り当ての履歴と増分頂点次数を使用して、レプリケーション係数の最適化を試みます。この 2 つの要素を考慮した関数を使用して、分析されたエッジを割り当てる最適なパーティションを計算します。作成されたレプリカは頂点の次数に基づいており、複製された頂点はおそらく、より高い次数をもつ頂点である、いわゆる「ハブ ノード」です。
Efficient and Balanced Vertex-cut(EBV) は、この論文で説明されているオフライン頂点カット アルゴリズムです。このアルゴリズムは、各パーティションのエッジと頂点の数、およびレプリケーション係数に関してパーティションのバランスをとろうとします。グラフのエッジと頂点の合計数も考慮したエッジを割り当てるパーティションを評価する式を適用します。評価式は以下の通りです。
最小値がパーティション ID として取得されます。
次数マトリックスは、グラフ内のノードの接続性についての洞察を提供する正方行列です。有向グラフの場合、各ノードの入出力エッジの数を反映しますが、無向グラフの場合、各ノードに入射するエッジの数を表します。
ラプラシアン行列は、グラフの隣接行列と次数行列から導出される正方行列です。これは、接続性、スパニング ツリーの数、その他のスペクトル特性など、グラフのさまざまなプロパティを分析するのに役立ちます。
遷移行列は、マルコフ連鎖と確率過程の研究で一般的に使用されます。グラフのコンテキスト内では、多くの場合エッジの重みや事前に決定された基準に基づいて、あるノードから別のノードに遷移する確率を表します。このマトリックスは、ネットワーク分析、機械学習、最適化などのさまざまな分野に応用できます。
サポートを提供したい場合は、プル リクエストを作成するか、問題を報告してください。コードを変更したり、問題を修正したり、新しい機能を実装したい場合は、貢献ガイドをお読みください。
新しい機能について議論したい場合、またはライブラリに関する質問や提案がある場合は、ディスカッションを開くか、単にチャットしてください。
CXXグラフサイト
電子メール : [email protected]
GitHub プロファイル
私をサポートするには、プロジェクトにスターを追加するか、私をフォローしてください
最新情報を入手するには、プロジェクトをご覧ください
私たちは以下から参照されています:
アルゴリズムのインスピレーションを与えてくれた TheAlgorithms コミュニティに感謝します。
アルゴリズムのインスピレーションを与えてくれた GeeksForGeeks に感謝します。
すでに CXXGraph に貢献してくださった皆様に感謝します。
このソフトウェアを使用する場合は、CITATION の指示に従ってください。ありがとう！
Hacktoberfest 2021 に参加しました。参加者の皆様、ありがとうございました!
Hacktoberfest 2022 に参加しました。参加者の皆様、ありがとうございました!
Hacktoberfest 2023 に参加しました。参加者の皆様、ありがとうございました!
プロジェクトの推定価値を表示する
@ZigRazor |
|---|
