Pythonのグラフは、いくつかの異なる方法で表現することができます。最も顕著なものは、隣接行列、隣接リスト、そしてエッジのリストです。このガイドでは、それらすべてをカバーします。グラフを実装する際には、これらの表現方法を自由に切り替えて使うことができます。
まず、グラフの理論を簡単に復習し、グラフを表現するためのデータ構造を説明し、最後に各表現方法の実用的な実装方法を説明します。
>
注意：このレッスンで紹介した実装は、以下のGitHubレポで見ることができます。
グラフとは何か – 簡単に言うと
グラフに関する基本的な定義について、もう一度簡単に説明しておきましょう。グラフとは、オブジェクト間の階層や関係をモデル化するためのデータ構造である。ノードの集合とエッジの集合で構成される。ノードは個々のオブジェクトを表し、エッジはそれらのオブジェクト間の関係を示す。
注：繰り返しになるが、「ノード」と「頂点」（「ノード」と「バーテックス」）という用語は、しばしば同じ意味で使われる。この講座では、ノードという用語を使うことにしたが、これは頂点という用語と同じ意味である。
グラフのすべての辺が双方向のつながりを示す場合、そのグラフを無向性と呼びます。一方、各辺を一方向にしかたどることができない場合、そのグラフは有向である。
グラフのすべてのノードが他のノードと接続されている必要はない。グラフのどのノードからも各ノードにアクセスできる場合、そのグラフを連結と呼びます。しかし、時には、グラフのどのノードからもアクセスできないノードがある – これが不連結グラフである。よくある誤解は、すべてのグラフは連結していなければならないということですが、実際はそうではありません。実際、グラフにはエッジがなく、ノードだけが存在することもあります。
実装の観点からは、最後にエッジの重みを説明する必要がある。これは、エッジに割り当てられる数値で、そのエッジを横断するのに必要なコストを表している。エッジの重みが小さいほど、そのエッジを横断するコストが安くなる。このことから、辺に重みをつけたグラフを重みつきグラフと呼ぶ。
基本的な知識を身につけたら、グラフの実装方法についてもっと深く掘り下げてみましょう。
グラフの表現方法として最も一般的な3つの方法
このセクションでは、グラフを表現する最も一般的な方法について説明します。それぞれの背景にある直感を説明し、いくつかの例を挙げます。その後、その知識を使ってPythonでグラフを実装することができます。
一般的に、任意のグラフのノードは、実装を簡単にするために、（0から始まる）数字でラベル付けされます。そのため、以下の例や実装ではその表記を使うことにします。
以下の節では、以下の重み付き有向グラフを例にして説明します。
注：重み付き有向グラフを例に挙げたのは、実装のニュアンスをほぼ説明するためである。一般に、重み付きグラフと無重みグラフの切り替えは、非常に簡単である。有向グラフと無向グラフの切り替えも、かなり簡単なことです。以下の節で、必要に応じてそれぞれのトピックを取り上げることにする。
エッジのリスト
辺のリストはおそらくグラフを表現する最も単純な方法ですが、適切な構造を持たないため、単に説明のために使われることが多いようです。いくつかのグラフアルゴリズムの説明に使うのは、オーバーヘッドがほとんどなく、グラフ自体の実装ではなく、アルゴリズムの実装に集中できるためです。
すでにご存知のように、各辺は2つのノードを結び、それに重みが割り当てられている場合がある。したがって、各辺は次のようにリストで表現されます： [node1, node2, weight], ここで weight はオプションのプロパティです（重みのないグラフの場合は必要ありません）。その名前が示すように、エッジのリストは、グラフを記述された方法で表現されたエッジのリストとして保存します。
ある有向重み付きグラフとその辺のリストを見てみよう．
見ての通り、辺のリストは事実上テーブルである。表の各行は1つの辺を表し、その辺の2つのノードとその辺の重みを表す。これは重みつきグラフなので、エッジの表現におけるノードの順番は、エッジの方向を示している。エッジは node1 から node2 へとしかたどることができません。
一方、無向グラフを扱うには、2つのアプローチがあります。まず、各ノードに対して、エッジの方向ごとに2つの行を追加する方法である。この方法はスペース効率が悪いが、有向グラフと無向グラフの両方を使い分ける場合には、必ず使わなければならない。2番目の方法は、無向グラフしか扱わないことが確定している場合のみ、使用することができる。その場合、各辺を無向とみなして、各辺に1行という表現を維持することができる。
長所
- シンプルで理解しやすい
- 説明のために最適
- グラフの定義（ノードの集合とエッジの集合）を表現できる
欠点
- どのような形であれ、構造化されていない
- 実世界のアプリケーションのために資格がない
- 効率的ではない
- 有向グラフと無向グラフを互換的に表現できるほど汎用性は高くない
隣接行列
隣接行列は，グラフを表現する最も一般的な方法の1つです．なぜなら，最も理解しやすく実装しやすい方法であり，多くの用途でそれなりにうまく機能するからです．これは，グラフを表現するために nxn 行列を用います (n はグラフのノード数です)．言い換えると，行と列の数はグラフのノードの数に等しくなります．
初期状態では，行列の各フィールドには， inf, 0, -1, False などの任意の値がセットされ，グラフにノードが存在しないことが示されます．この初期段階の後、グラフの各エッジのフィールドに 1 (重みなしグラフの場合) またはエッジの重み (重み付きグラフの場合) を入力することで、グラフのエッジを追加することができます。
この行列は、基本的には表であり、各行と各列はグラフの1つのノードを表します。例えば，行 3 はノード 3 を表します．そのため，隣接行列を用いることで，数字がラベル付けされたノードからなるグラフのみを表現することができます．
注：実際には，異なる名前のノードを扱えるように隣接行列の実装を変更することができますが，通常は追加作業が必要になるため，潜在的な利益が損なわれてしまいます．そのため、より単純な実装、つまり、番号の付いたノードのみを使用することにしたのである。
行 i と列 j の交点にあるフィールドは、ノード i と j の間のエッジの存在や重みを表す。例えば、行 1 と列 4 の交点を埋めるフィールドは、ノード 1 と 4 (この順) を結ぶエッジが存在することを示します。重みつきグラフの場合は、その辺の重みを、無重みグラフの場合は 1 をフィールドに入力します。
無向グラフの場合は、各エッジに対して2つのエントリを追加しなければなりません。
先ほどの説明ではよくわからなかったので、次のようなグラフを例にして、隣接行列の作り方を簡単に説明しましょう。
このグラフには、ノードが n 個あります。そこで、行と列が n 個の表を作成し、すべてのセルを 0 – 2つのノード間にエッジが存在しないことを示す特別な値 – で初期化しました。この例のグラフは重み付き有向グラフなので、次のことが必要になります。
- グラフのすべての辺をスキャンする
- そのエッジの開始ノードと終了ノードを決定する。
- そのエッジの重みを決定する
- 行列の適切なフィールドを重みの値で埋める
例として、エッジ 3-4 を使ってみましょう。開始ノードが 3 で終了ノードが 4 なので、行 3 と列 4 の交点をフィールドに埋める必要があることがわかります。画像から、エッジの重みが 11 であることが読み取れるので、該当するフィールドを 11 で埋め尽くします。これでエッジ 3-4 があることを示すマークができました。この作業を、グラフのすべてのエッジをマークするまで繰り返すのです。
長所
- ルックアップにかかる時間が短い – エッジが存在するかどうかを
O(1)の時間で判断することができます。 - エッジの追加/削除に要する時間は
O(1)である。 - 実装が簡単で理解しやすい
短所
- ノードの追加に
O(num_of_nodes²)の時間を要する。 - ノードの追加に
O(num_of_nodes²)の時間を要する． - 選択されたノードの隣接ノードを探すのにコストがかかる –
O(num_of_nodes). - グラフを走査するのに必要なコスト –
O(num_of_nodes²). - ラベル付けや辺の列挙にかかるコスト –
O(num_of_nodes²).
Adjacency List
隣接リストは、グラフを保存する最も効率的な方法です。グラフに存在する辺だけを格納することができます。これは、存在する辺と存在しない辺の両方を含むすべての可能な辺を明示的に格納する隣接行列の逆です。隣接行列は当初、重みのないグラフだけを表現するために開発されましたが、最も効果的な方法として、1つの配列だけを用いて表現します。
下の図に見られるように、12個の整数値からなる配列だけで、例のグラフを表現することができます。隣接行列と比較してみましょう。隣接行列は n² 個の要素で構成されますが (n はグラフのノード数)、 隣接リストは n+e 個の要素で済みます (e はエッジの数)。グラフが密でない (エッジの数が少ない) 場合は、はるかに空間効率がよい。
問題は、隣接行列に比べて隣接リストが理解しにくいことです。
まず、隣接表を作成するために必要なことは、グラフのノードの数です。例えば、インデックス 1 の要素は、ノード 1 を表します。例えば、インデックス 1 の要素はノード 1 を表します。リストの最初の5つの場所を確保したら、リストを埋めていきます。インデックス i の値は、リスト内でノード i に隣接するノードのインデックスを見つけることができるインデックスを指します。
例えば、インデックス 0 の値は 5 で、これは隣接リストのインデックス 5 を見て、ノード 0 に接続されているノードを探すことを意味します – これらはノード 0、1、2 です。しかし、隣接するノードを探すのをやめるタイミングはどうやって知るのでしょうか？それはとても簡単です。リストの 0 の隣にあるインデックスの値を見てみましょう。次のインデックスは 1 で、これはノード 1 を表し、その値は 8 です。つまり、隣接リストのインデックス 8 からは、ノード 1 に隣接するノードを見つけることができる、ということです。したがって、ノード 0 に隣接するノードは、リストのインデックス 5 と 8 の間の値として見つけることができる。
この構造をより理解しやすくするために、隣接リストの要素をより構造的に並べ替えることができる。そうすると、結果として得られる構造はリンクリストによく似ていることがわかるでしょう。
さらに、リンクリストの構造は、辞書（あるいはマップ）によく似ている。リンクリストは、キーとなるノードと、そのキーに隣接するノードの集合を持つ。重みつきグラフを表現したい場合は、隣接するノード以外に重みを保存する方法を見つけなければならない（以下の図にあるように）。しかし、実装の詳細については、後の節で説明する。
次の図は、例のグラフの隣接リストを示したもので、重みのあるものとないものの両方があります。
重みのある隣接リストを見ると、例のグラフのエッジの集合を簡単に構築することができる。ノード 0 には 3 つの隣接ノード 0, 1, 2 があり、グラフにはエッジ 0-0, 0-1, 0-2 があることになります。これらの辺の重みは、隣接関係リストから読み取ることもできます。0-0のエッジの重みは25であり、0-1のエッジの重みは5` であり、グラフのすべてのエッジに対して同じ重みがある。
長所
- 選択されたノードの隣接ノードを見つけるのが簡単 –
O(1). - あまり密でないグラフ（ノード数に比べてエッジ数が少ない）に対して効率的である。
- 文字ラベル付きノードと数字ラベル付きノードの両方に利用可能
- グラフのトラバースにかかるコストが低い –
O(length_of_list). - ラベル付けや辺の列挙にかかるコストが低い –
O(length_of_list).
短所
- ルックアップ時間が長い –
O(length_of_list). - エッジを削除する際のコストが高い –
O(length_of_list)(ルックアップ時間の論理的延長)
注: length_of_list は、グラフ内のノード数とエッジ数の和に等しい。
Pythonでグラフを実装する方法
これで、最も一般的なデータ構造でグラフを表現する方法がわかりましたね! 次に行うべきことは、これらのデータ構造をPythonで実装することです。このガイドのゴールは、できるだけ普遍的なグラフの実装を与え、なおかつ軽量にすることです。それによって、データ構造としてのグラフではなく、グラフアルゴリズムの実装に集中することができるのです。理想的には、グラフデータ構造を表すラッパークラスを用意し、後で実装したいグラフアルゴリズ ムメソッドを包むのに使えるようにすることです。
注意：このガイドで作成する単純な実装は、高度に特殊でないすべてのユースケースをカバーするはずです。例えば、ここではすべてのノードが0から始まる数字でラベル付けされていると仮定します。しかし、より包括的な実装が必要な場合は、私たちがサポートします。完全な実装は次の GitHub リポジトリで見ることができます。
Graph` クラスはグラフ表現と、グラフを操作するために必要な他のすべてのメソッドを保持します。ここでは、その一般的な構造を説明し、その後に実装を説明します。
class Graph:
# Constructor
# Number of edges
# Adjacancy matrix, adjacency list, list of edges
# Methods for adding edges
# Methods for removing edges
# Methods for searching a graph
# BFS, DFS, Dijkstra, A*...
# Methods for finding a minimum spanning tree
# Prim's algorithm, Kruskal's algorithm, Borůvka's algorithm...
# Other interesting methods
見てわかるように、Graphクラスには実装すべきいくつかの「セクション」があります。このセクションで最も重要なのはコンストラクタのセクションです。ここには、グラフの実装(データ構造の表現)を置きます。その後、このクラスのメソッドとして、任意のグラフ関連のアルゴリズムを実装することができます。また、任意のグラフ探索/走査アルゴリズムを独立したメソッドとして実装し、グラフそのものを渡すこともできます。その違いは、文字通り、アルゴリズムが self (親グラフ) を参照するか、渡された graph を参照するかの違いに過ぎない。
それでは、 Graph クラスに上記のようなグラフ表現を実装する方法を見てみましょう。このセクションでは、先に示したサンプルグラフを使って、それぞれの実装をテストします。
PythonでEdgeのリストを実装する####方法
前にも述べたように、辺のリストは実世界ではあまり使われませんが、説明のために使われることがよくあります。アルゴリズムの実装を不必要に複雑にしない、シンプルなグラフの実装が必要なときに使うことができます。
ここでは、グラフを表現するために辺のリストを使用する Graph クラスの実装を見てみましょう。
class Graph:
# Constructor
def __init__(self, num_of_nodes, directed=True):
self.m_num_of_nodes = num_of_nodes
self.m_directed = directed
# Different representations of a graph
self.m_list_of_edges = []
# Add edge to a graph
def add_edge(self, node1, node2, weight=1):
# Add the edge from node1 to node2
self.m_list_of_edges.append([node1, node2, weight])
# If a graph is undirected, add the same edge,
# but also in the opposite direction
if not self.m_directed:
self.m_list_of_edges.append([node1, node2, weight])
# Print a graph representation
def print_edge_list(self):
num_of_edges = len(self.m_list_of_edges)
for i in range(num_of_edges):
print("edge ", i+1, ": ", self.m_list_of_edges[i])
見ての通り、この実装はとてもシンプルです。グラフは辺のリストで表現され、各辺は [node1, node2, weight] のようなリストで表現される。したがって、グラフは事実上行列であり、各行が1つのエッジを表す。
それでは、グラフを作成し、エッジのリストがどのように格納されるかを見てみましょう。
graph = Graph(5)
graph.add_edge(0, 0, 25)
graph.add_edge(0, 1, 5)
graph.add_edge(0, 2, 3)
graph.add_edge(1, 3, 1)
graph.add_edge(1, 4, 15)
graph.add_edge(4, 2, 7)
graph.add_edge(4, 3, 11)
graph.print_edge_list()
まず、このグラフには5つのノードがあるので、コンストラクタで5つのノードを持つグラフを作ります。そして、作成したグラフにすべてのエッジを追加し、グラフを表示します。すると、次のように出力されます。
edge 1 : [0, 0, 25]
edge 2 : [0, 1, 5]
edge 3 : [0, 2, 3]
edge 4 : [1, 3, 1]
edge 5 : [1, 4, 15]
edge 6 : [4, 2, 7]
edge 7 : [4, 3, 11]
見ての通り、この出力はこれまでのセクションで紹介したエッジのリストの例と一致しています。
注：もし、このグラフを無向グラフにしたい場合は、コンストラクタを次のように変更してください： graph = Graph(5, directed=False).
Pythonで隣接行列を実装する方法
隣接行列は基本的に単純な nxn 行列であり、 n はグラフのノード数である。したがって、ここでは num_of_nodes 個の行と列を持つ行列として実装することにします。ここでは、リスト内包を用いてこれを構築し、すべてのフィールドを 0 で初期化することにする。
この場合、 0 はグラフにエッジが存在しないことを意味する特別な値です。グラフに重みがあるかないかに応じて、行列の適切なフィールドに 1 または weight をセットするだけです。
class Graph:
def __init__(self, num_of_nodes, directed=True):
self.m_num_of_nodes = num_of_nodes
self.m_directed = directed
# Initialize the adjacency matrix
# Create a matrix with `num_of_nodes` rows and columns
self.m_adj_matrix = [[0 for column in range(num_of_nodes)]
for row in range(num_of_nodes)]
def add_edge(self, node1, node2, weight=1):
self.m_adj_matrix[node1][node2] = weight
if not self.m_directed:
self.m_adj_matrix[node2][node1] = weight
def print_adj_matrix(self):
print(self.m_adj_matrix)
では、先に説明した方法でこの実装をテストしてみましょう。
graph = Graph(5)
graph.add_edge(0, 0, 25)
graph.add_edge(0, 1, 5)
graph.add_edge(0, 2, 3)
graph.add_edge(1, 3, 1)
graph.add_edge(1, 4, 15)
graph.add_edge(4, 2, 7)
graph.add_edge(4, 3, 11)
graph.print_edge_list()
上のコードを実行すると、次のような出力が得られます。
[25, 5, 3, 0, 0]
[0, 0, 0, 1, 15]
[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0]
[0, 0, 7, 11, 0]
予想通り、出力は前のセクションで紹介したものと同じ行列です。
注：もし、このグラフを無向グラフにしたい場合は、コンストラクタを次のようにします：graph = Graph(5, directed=False). この場合、隣接行列は対称になります。
Pythonで隣接リストを実装する方法
前のセクションで説明したように、Pythonで隣接リストを表現する最も良い方法は、辞書を使うことです – それはキーと対応する値のセットを持ちます。
各ノードに対して1つのキーを作成し、各キーに対して隣接するノードの集合を作成します。こうすることで、グラフの各ノードに対して、隣接するノードのセットを効果的に作成することができます。隣接ノードとは、キーとなるノードと隣接するノードとの間のエッジを意味するため、各エッジに重みを与える必要がある。そこで、各隣接ノードをタプル（隣接ノードの名前とエッジの重みのペア）で表現する。
class Graph:
def __init__(self, num_of_nodes, directed=True):
self.m_num_of_nodes = num_of_nodes
self.m_nodes = range(self.m_num_of_nodes)
# Define the type of a graph
self.m_directed = directed
self.m_adj_list = {node: set() for node in self.m_nodes}
def add_edge(self, node1, node2, weight=1):
self.m_adj_list[node1].add((node2, weight))
if not self.m_directed:
self.m_adj_list[node2].add((node1, weight))
def print_adj_list(self):
for key in self.m_adj_list.keys():
print("node", key, ": ", self.m_adj_list[key])
もう一度、前述した方法で実装をテストしてみよう。
graph = Graph(5)
graph.add_edge(0, 0, 25)
graph.add_edge(0, 1, 5)
graph.add_edge(0, 2, 3)
graph.add_edge(1, 3, 1)
graph.add_edge(1, 4, 15)
graph.add_edge(4, 2, 7)
graph.add_edge(4, 3, 11)
graph.print_edge_list()
出力は前節で説明したリンクリストと全く同じである。
node 0 : {(2, 3), (0, 25), (1, 5)}
node 1 : {(3, 1), (4, 15)}
node 2 : set()
node 3 : set()
node 4 : {(2, 7), (3, 11)}
注意：もし、このグラフを無向グラフにしたい場合は、コンストラクタを次のように変更してください：graph = Graph(5, directed=False).
結論
このガイドを読んだ後、「最終的にどのようなグラフ表現を使えばいいのか？しかし、その答えはいつも通り、一筋縄ではいきません。
グラフ表現にはそれぞれ長所と短所があり、あるユースケースでは優れているが、他のケースではパフォーマンスが低いということがあります。そのため、本ガイドでは、グラフ表現について包括的に解説しています。このガイドを読めば、グラフ表現について直感的に理解でき、それぞれの実装方法と、長所と短所をまとめた便利なリストに基づいて、どのような場合にグラフを使用すればよいかがわかるはずです。したがって、グラフ関連のアルゴリズムの実装をより深く追求したいのであれば、このガイドが良い出発点となるはずです。
一方、グラフの実装そのものを深く掘り下げたい場合は、以下のGitHubリポジトリを参照することをお勧めします。そこでは、グラフのデータ構造について、より深く、包括的な実装を見つけることができます。