グラフ（抽象データ型）

コンピュータサイエンスにおいて、グラフとは、数学におけるグラフ理論の分野における無向グラフと有向グラフの概念を実装することを目的とした抽象データ型である。

グラフデータ構造は、有限個の（場合によっては変更可能な）頂点（ノードまたはポイントとも呼ばれる）の集合と、無向グラフの場合はこれらの頂点の順序付けされていないペアの集合、有向グラフの場合は順序付けされたペアの集合から構成されます。これらのペアはエッジ（リンクまたは線とも呼ばれる）として知られており、有向グラフの場合はエッジとして知られていますが、矢印またはアークと呼ばれることもあります。頂点はグラフ構造の一部である場合もあれば、整数インデックスまたは参照によって表される外部エンティティである場合もあります。

グラフデータ構造では、各エッジに記号ラベルや数値属性（コスト、容量、長さなど）といったエッジ値を関連付けることもできます。

業務

グラフデータ構造Gが提供する基本的な操作は通常次のとおりです。^{[ 1 ]}

adjacent( G , x , y ) : 頂点xから頂点yへのエッジが存在するかどうかをテストします。
neighbors( G , x ) :頂点xから頂点yへの辺が存在するようなすべての頂点yをリストします。
add_vertex( G , x ) : 頂点xが存在しない場合は、それを追加します。
remove_vertex( G , x ) : 頂点xが存在する場合、それを削除します。
add_edge( G , x , y , z ) :頂点xから頂点yへのエッジz が存在しない場合、エッジzを追加します。
remove_edge( G , x , y ) : 頂点xから頂点yへのエッジが存在する場合、それを削除します。
get_vertex_value( G , x ) : 頂点xに関連付けられた値を返します。
set_vertex_value( G , x , v ) : 頂点xに関連付けられた値をvに設定します。

エッジに値を関連付ける構造は通常、次の機能も提供します。^{[ 1 ]}

get_edge_value( G , x , y ) : エッジ ( x , y ) に関連付けられた値を返します。
set_edge_value( G , x , y , v ) : エッジ ( x , y )に関連付けられた値をvに設定します。

グラフ表現のための一般的なデータ構造

隣接リスト^{[ 2 ]}: 頂点はレコードまたはオブジェクトとして格納され、各頂点は隣接する頂点のリストを格納します。このデータ構造により、頂点に関する追加データを格納できます。エッジもオブジェクトとして格納する場合、各頂点は接続するエッジを格納し、各エッジは接続する頂点を格納します。
隣接行列^{[ 3 ]}: 行が始点頂点、列が終点頂点を表す2次元行列。辺と頂点に関するデータは外部に保存する必要がある。各頂点ペア間には、1つの辺のコストのみを保存できる。
発生率マトリックス^{[ 4 ]}: 行が頂点、列が辺を表す2次元行列。各要素は、行の頂点と列の辺との間の接続関係を示す。

以下の表は、グラフの各表現形式における各種操作の実行にかかる時間計算量を示しています。ここで、| V |は頂点の数、| E |は辺の数です。行列表現では、各要素は辺をたどるコストを表します。存在しない辺のコストは無限大とみなされます。

隣接リストは一般的に疎グラフの表現に好まれ、隣接行列はグラフが密な場合、つまりエッジの数が多い場合に好まれる。 $|E|$ 頂点の数の二乗に近い値です。 $|V|^{2}$ あるいは、2 つの頂点を結ぶ辺があるかどうかを素早く調べる必要がある場合。^{[ 5 ]}^{[ 6 ]}

隣接集合のより効率的な表現

隣接リスト表現における操作の時間計算量は、隣接頂点の集合をハッシュテーブルや平衡二分探索木などのより効率的なデータ構造に格納することで改善できます（後者の表現では、頂点は整数や文字列などの線形順序集合の要素によって識別される必要があります）。ハッシュテーブルによる隣接頂点の表現は、償却平均時間計算量をもたらします。 $O(1)$ 与えられた 2 つの頂点の隣接性をテストし、エッジを削除し、償却平均時間計算量^{[ 7 ]}は $O(\deg(x))$ $次数x$ の特定の頂点を削除する $\deg(x)$ 他の操作の時間計算量と漸近的な空間要件は変化しません。

並列表現

グラフ問題の並列化は、データ駆動型計算、非構造化問題、局所性の低さ、計算に対するデータアクセスの比率の高さといった重大な課題に直面しています。^{[ 8 ]}^{[ 9 ]}並列アーキテクチャで使用されるグラフ表現は、これらの課題に対処する上で重要な役割を果たします。不適切な表現を選択すると、アルゴリズムの通信コストが不必要に上昇し、スケーラビリティが低下する可能性があります。以下では、共有メモリアーキテクチャと分散メモリアーキテクチャについて検討します。

共有された記憶

共有メモリモデルの場合、並列処理に使用されるグラフ表現は逐次処理の場合と同じです^{[ 10 ]。}これは、グラフ表現（隣接リストなど）への並列読み取り専用アクセスが共有メモリでは効率的であるためです。

分散メモリ

分散メモリモデルでは、通常、頂点セットを分割するアプローチが取られます。 $V$ グラフを $p$ セット $V_{0},\dots ,V_{p-1}$ 。ここ、 $p$ は利用可能な処理要素 (PE) の数です。頂点セットのパーティションは、対応するエッジに加えて、一致するインデックスを持つ PE に分配されます。各 PE は独自のサブグラフ表現を持ち、別のパーティションにエンドポイントを持つエッジには特別な注意が必要です。MPI のような標準的な通信インターフェースでは、他のエンドポイントを所有する PE の ID を識別できる必要があります。分散グラフアルゴリズムでの計算中、これらのエッジに沿って情報を渡すことは通信を意味します。^{[ 10 ]}

グラフの分割は慎重に行う必要があります。低通信と均等なサイズの分割の間にはトレードオフがあります^{[ 11 ]。}しかし、グラフの分割はNP困難問題であるため、計算することは現実的ではありません。代わりに、次のヒューリスティックが使用されます。

1Dパーティショニング: 各プロセッサは $n/p$ 頂点とそれに対応する出力エッジ。これは隣接行列の行方向または列方向の分解として理解できます。この表現で動作するアルゴリズムでは、全対全通信ステップと ${\mathcal {O}}(m)$ メッセージバッファのサイズは、各PEが他のすべてのPEに対して送信エッジを持つ可能性があるためです。^{[ 12 ]}

2Dパーティショニング：各プロセッサは隣接行列のサブマトリックスを受け取ります。プロセッサは長方形に配置されていると仮定します。 $p=p_{r}\times p_{c}$ 、どこ $p_{r}$ そして $p_{c}$ はそれぞれ、各行および各列の処理要素の数です。次に、各プロセッサは、次元の隣接行列のサブマトリックスを取得します。 $(n/p_{r})\times (n/p_{c})$ これは、マトリックス内の市松模様として視覚化できます。 ^{[ 12 ]}したがって、各処理ユニットは、同じ行と列のPEにのみ出力エッジを持つことができます。これにより、各PEの通信パートナーの数が制限されます。 $p_{r}+p_{c}-1$ から $p=p_{r}\times p_{c}$ 可能性のあるもの。

圧縮表現

機械学習、ソーシャルネットワーク分析、その他の分野では、数兆のエッジを持つグラフが存在します。I/Oとメモリ要件を削減するために、圧縮グラフ表現が開発されてきました。ハフマン符号化などの一般的な手法が適用可能ですが、隣接リストや隣接行列は効率を高めるために特定の方法で処理することができます。^{[ 13 ]}

グラフの応用

幅優先探索と深さ優先探索

幅優先探索(BFS) と深さ優先探索(DFS) は、与えられた連結成分内のすべてのノードを探索するために使用される、密接に関連した 2 つのアプローチです。どちらも任意のノード「ルート」から始まります。^{[ 14 ]}強く連結した成分は、修正された DFS である Kosaraju のアルゴリズムなどのアルゴリズムを使用したグラフの走査によっても見つけることができます。

経路探索

ダイクストラ法は、正の重みを持つグラフ（すべての辺の重みが0以上であるグラフ）および/または有向グラフで使用できる経路探索アルゴリズムです。これは、任意に選択された2つのノード間の最短経路を見つけるために使用でき、ルーティング問題でよく用いられます。

参考文献

1 2例えば、 Goodrich & Tamassia (2015) のセクション 13.1.2: グラフの操作、p. 360 を参照。より詳細な操作については、 Mehlhorn, K. ; Näher, S. (1999) の「第 6 章: グラフとそのデータ構造」、LEDA: 組み合わせおよび幾何計算のためのプラットフォーム(PDF)、Cambridge University Press、pp. 240–282 を参照。
↑コーメンら。 (2001)、528–529 ページ。グッドリッチ&タマッシア (2015)、361-362 ページ。
↑コーメンら。 (2001)、529–530 ページ。グッドリッチ&タマッシア (2015)、p. 363.
↑ Cormen et al. (2001)、演習 22.1-7、p. 531。
↑ Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001). "Section 22.1: Representations of graphs". Introduction to Algorithms (Second ed.). MIT Press and McGraw-Hill. pp. 527–531 . ISBN 0-262-03293-7。
↑ Goodrich, Michael T. ; Tamassia, Roberto (2015). 「第 13.1 節: グラフの用語と表現」. Algorithm Design and Applications . Wiley. pp. 355–364 . ISBN 978-1-118-33591-8。
↑ Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2009). Introduction to Algorithms (3rd ed.). Massachusetts Institute of Technology. pp. 253–280 . ISBN 978-0-262-03384-8。
↑ Bader, David; Meyerhenke, Henning; Sanders, Peter; Wagner, Dorothea (2013年1月).グラフ分割とグラフクラスタリング. Contemporary Mathematics. Vol. 588. American Mathematical Society. doi : 10.1090/conm/588/11709 . ISBN 978-0-8218-9038-7。
↑ Lumsdaine, Andrew; Gregor, Douglas; Hendrickson, Bruce; Berry, Jonathan (2007 年 3 月). "並列グラフ処理における課題". Parallel Processing Letters . 17 (1): 5–20 . doi : 10.1142/s0129626407002843 . ISSN 0129-6264 .
1 2 Sanders, Peter; Mehlhorn, Kurt; Dietzfelbinger, Martin; Dementiev, Roman (2019). Sequential and Parallel Algorithms and Data Structures: The Basic Toolbox . Springer International Publishing. ISBN 978-3-030-25208-3。
↑ 「グラフの並列処理」（PDF）。2021年8月25日にオリジナル（PDF）からアーカイブ済み。2020年3月9日に取得。
1 2 Buluç, A.; Madduri, Kamesh (2011). "アプリケーション".分散メモリシステムにおける並列幅優先探索. 2011 International Conference for High Performance Computing, Networking, Storage and Analysis. CiteSeerX 10.1.1.767.5248 . doi : 10.1145/2063384.2063471 . ISBN 978-1-4503-0771-0. S2CID 6540738 .
↑ Besta, Maciej; Hoefler, Torsten (2019年4月27日). "Survey and Taxonomy of Lossless Graph Compression and Space-Efficient Graph Representations". arXiv : 1806.01799 [ cs.DS ].
↑ Purti (2018年7月～9月) 「グラフ走査とその応用」(PDF) . International Journal of Research and Analytical Reviews . 5 (3): 2.

外部リンク

Boost Graph Library: Boost (C++ ライブラリ)の強力な C++ グラフライブラリ
Networkx: Pythonのグラフライブラリ
GraphMatcherは、有向グラフと無向グラフを整列させるためのJavaプログラムです。
GraphBLAS は、グラフに対する操作を行うためのライブラリインターフェースの仕様であり、特に疎グラフに重点を置いている。

[gt-ops-1] 1 2例えば、 Goodrich & Tamassia (2015) のセクション 13.1.2: グラフの操作、p. 360 を参照。より詳細な操作については、 Mehlhorn, K. ; Näher, S. (1999) の「第 6 章: グラフとそのデータ構造」、LEDA: 組み合わせおよび幾何計算のためのプラットフォーム(PDF)、Cambridge University Press、pp. 240–282 を参照。

[2] コーメンら。 (2001)、528–529 ページ。グッドリッチ&タマッシア (2015)、361-362 ページ。

[3] コーメンら。 (2001)、529–530 ページ。グッドリッチ&タマッシア (2015)、p. 363.

[4] Cormen et al. (2001)、演習 22.1-7、p. 531。

[clrs-5] Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001). "Section 22.1: Representations of graphs". Introduction to Algorithms (Second ed.). MIT Press and McGraw-Hill. pp. 527–531 . ISBN 0-262-03293-7。

[gt-6] Goodrich, Michael T. ; Tamassia, Roberto (2015). 「第 13.1 節: グラフの用語と表現」. Algorithm Design and Applications . Wiley. pp. 355–364 . ISBN 978-1-118-33591-8。

[Cormen_et_al_p253-280_(hashtable)-7] Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2009). Introduction to Algorithms (3rd ed.). Massachusetts Institute of Technology. pp. 253–280 . ISBN 978-0-262-03384-8。

[Bader2013-8] Bader, David; Meyerhenke, Henning; Sanders, Peter; Wagner, Dorothea (2013年1月).グラフ分割とグラフクラスタリング. Contemporary Mathematics. Vol. 588. American Mathematical Society. doi : 10.1090/conm/588/11709 . ISBN 978-0-8218-9038-7。

[9] Lumsdaine, Andrew; Gregor, Douglas; Hendrickson, Bruce; Berry, Jonathan (2007 年 3 月). "並列グラフ処理における課題". Parallel Processing Letters . 17 (1): 5–20 . doi : 10.1142/s0129626407002843 . ISSN 0129-6264 .

[Sanders2019-10] 1 2 Sanders, Peter; Mehlhorn, Kurt; Dietzfelbinger, Martin; Dementiev, Roman (2019). Sequential and Parallel Algorithms and Data Structures: The Basic Toolbox . Springer International Publishing. ISBN 978-3-030-25208-3。

[11] 「グラフの並列処理」（PDF）。2021年8月25日にオリジナル（PDF）からアーカイブ済み。2020年3月9日に取得。

[Buluc2011-12] 1 2 Buluç, A.; Madduri, Kamesh (2011). "アプリケーション".分散メモリシステムにおける並列幅優先探索. 2011 International Conference for High Performance Computing, Networking, Storage and Analysis. CiteSeerX 10.1.1.767.5248 . doi : 10.1145/2063384.2063471 . ISBN 978-1-4503-0771-0. S2CID 6540738 .

[13] Besta, Maciej; Hoefler, Torsten (2019年4月27日). "Survey and Taxonomy of Lossless Graph Compression and Space-Efficient Graph Representations". arXiv : 1806.01799 [ cs.DS ].

[Purti-14] Purti (2018年7月～9月) 「グラフ走査とその応用」(PDF) . International Journal of Research and Analytical Reviews . 5 (3): 2.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]。

[ 11 ]。

[ 12 ]

[ 13 ]

[ 14 ]