グラフ（抽象データ型）

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

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

グラフ データ構造では、各エッジに、シンボリック ラベルや数値属性 (コスト、容量、長さなど) などの エッジ値を関連付けることもできます。

グラフデータ構造Gが提供する基本的な操作には、通常、次のものが含まれます。^[1]

• neighbor( 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 を追加します（存在しない場合）。
• 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 | は辺の数です。^[要出典]行列表現では、エントリは辺をたどるコストをエンコードします。存在しない辺のコストは ∞ であると想定されます。

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

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

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

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

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

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

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

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

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

幅優先探索（BFS）と深さ優先探索（DFS）は、与えられた連結成分内のすべてのノードを探索するために使用される2つの密接に関連したアプローチです。どちらも任意のノードである「ルート」から始まります。^[14]

• グラフトラバーサルの詳細については、グラフトラバーサルを参照してください。
• グラフ（データ構造）の永続性のためのグラフデータベース
• グラフ（グラフデータ構造）のルールベースの変換のためのグラフ書き換え
• グラフ描画ソフトウェア、グラフ描画システム、グラフ描画システムプロバイダー向け

ウィキメディア・コモンズには、グラフ (抽象データ型)に関連するメディアがあります。

• Boost グラフ ライブラリ: 強力な C++ グラフ ライブラリ(C++ ライブラリ)
• Networkx: Python グラフライブラリ
• GraphMatcher は、有向/無向グラフを整列させる Java プログラムです。
• GraphBLAS グラフ操作用のライブラリ インターフェイスの仕様。特にスパース グラフに重点を置きます。