グラフ理論とNetworkX¶
グラフ理論は、グラフ・ネットワークに関する学問です。
グラフ・ネットワークで扱えること¶
グラフ・ネットワークは、社会の色々なところに現れています。
通信ネットワーク
物流ネットワーク
鉄道ネットワーク
エネルギーネットワーク
グラフ理論を使うと、以下のような色々な問題を解けます。
最短路問題
最小全域木問題
最小費用流問題
最大マッチング問題
などなど
グラフとは¶
頂点(
vertex, node
)と辺(edge, arc
)からなる構造をグラフ構造(graph
)といいます。通常、頂点や辺は、重み(
weight
)などの属性を持ちます。
辺上にモノを流す場合は、ネットワーク(
network
)といいます。ネットワークでは、辺の重み(
weight
)を考慮します。
※ PyQでは、折れ線グラフのようなグラフと、頂点と辺からなるグラフの 2 種類 に対し、同じグラフという言葉を用いているので、文脈に合わせて適宜解釈してください。
NetworkXとは¶
Pythonでは、グラフ・ネットワークを扱うライブラリーとしてNetworkXがあります。 NetworkXを使うと、色々なアルゴリズムを使えます。
以降では、NetworkXは、import networkx as nx
として使い、nx
として参照します。また、グラフはg
で参照します。
参考
NetworkXのインストール¶
コマンドプロンプトで、pip install -U networkx
でできます(macOSではpip3 install -U networkx
)。
グラフの表記¶
グラフを表記するのに以下の記号を使うことがあります。Vertex, Edge, Graph
から来ています。
V
:頂点の集合E
:辺の集合G
:グラフV
とE
からなることを明示的に表す場合、G(V, E)
と表記します
NetworkXのグラフの種類¶
NetworkXのグラフには4種類あります。
無向グラフ | 有向グラフ | |
---|---|---|
単純グラフなど※ | Graph | DiGraph |
多重グラフ | MultiGraph | MultiDiGraph |
※ 上表の「単純グラフなど」は、単純グラフ、または 自己ループのみ含む多重グラフを指しています。
グラフの用語¶
単純グラフ(
simple graph
):自己ループも多重辺も含まないグラフ多重グラフ(
multi graph
):単純グラフとは限らないグラフ無向グラフ(
undirected graph
):無向辺だけからなるグラフ有向グラフ(
directed graph
):有向辺だけからなるグラフ自己ループ(
loop
):両端が同じ頂点となる辺多重辺(
multiple edges
):2つの頂点の間に複数の辺がある場合、それらを多重辺といいます有向辺(
directed edge
): 向きがある辺無向辺(
undirected edge
): 向きのない辺
歩道:ある頂点から辺をたどって別の頂点へ行ける場合、その辺の並びを歩道といいます。
路:辺が重複しない歩道を路といいます。
パス:頂点が重複しない路をパス(
path
)や道といいます。
閉路:始点と終点が同じ路を閉路といいます。
サイクル:始点と終点が同じパスをサイクルといいます。
参考
木(
tree
):サイクルのないグラフで、連結しているもの。森(
forest
):サイクルのないグラフで、連結しているとは限らないもの。
グラフ描画¶
Jupyter Notebookでは、nx.draw_networkx(グラフオブジェクト)
で、簡単にグラフを描画できます。
無向グラフ(
Graph
)の辺は、線で描画されます。有向グラフ(
Graph
)の辺は、矢印で描画されます。
GraphとMultiGraphの違い¶
GraphとMultiGraphの違いは、グラフの辺(u, v)
があったときに、以下のようになります。
辺が一意に決まるグラフ:
Graph
またはDiGraph
で作成できます。辺が一意に決まらないグラフ:
MultiGraph
またはMultiDiGraph
で作成できます。
グラフオブジェクトの変換¶
グラフオブジェクトの作成では、他の種類のグラフオブジェクトを引数に取って、種類を変更できます。
g1 = nx.Graph() # 無向グラフ
g2 = nx.DiGraph(g1) # 有向グラフに変換
上記のコードは、無向グラフg1
を有向グラフに変換しています(g2
)。
「
無向グラフ → 有向グラフ
」は、to_directed
メソッドでも変換できます。g2 = g1.to_directed()
「
有向グラフ → 無向グラフ
」は、to_undirected
メソッドでも変換できます。g1 = g2.to_undirected()
連結グラフとは¶
2つの頂点の間にパスが存在するとき連結しているといいます。
全ての頂点が連結しているグラフを連結グラフ(
connected graph
)といいます。NetworkXでは、
nx.is_connected
でチェックできます。
有向グラフの任意の2点間にパスが存在する場合、強連結といいます。
NetworkXでは、
nx.is_strongly_connected
でチェックできます。
有向グラフが「無向グラフに変換したときに連結である」ならば、弱連結といいます。
NetworkXでは、
nx.is_weakly_connected
でチェックできます。
参考:連結グラフ
グラフの編集¶
add_node(頂点オブジェクト)
:頂点の追加add_edge(頂点オブジェクト1, 頂点オブジェクト2)
:辺の追加頂点オブジェクトは、辞書のキーに使えるものでないといけません。たとえば、数字や文字列が使えます。リストは使えません。
add_nodes_from(頂点リスト)
:頂点リストを一括で作成します。add_edges_from(辺リスト)
:辺リストを一括で作成します。
実は、頂点を追加していなくても、いきなり辺の追加ができます。 辺を追加するときに、指定された頂点が存在しない場合、自動的に頂点の追加も行われます。
add_node
で頂点の追加が必要な場合¶
指定した順番に頂点のリストを作成したいとき:辺を追加する前に、順番通りに頂点を追加します。
頂点に属性を設定したいとき:追加時に属性を指定できます。
属性の指定¶
頂点や辺に、任意の属性を指定できます。属性は、頂点や辺の辞書に設定されます。
頂点の追加:
add_node(頂点オブジェクト, 頂点の属性1, 頂点の属性2, ...)
辺の追加:
add_edge(頂点オブジェクト1, 頂点オブジェクト2, 辺の属性1, 辺の属性2, ...)
補足
属性は、キーワード引数として指定します。いくつでも指定できます。任意のキーワードが使えます。
NetworkXのいくつかの関数では、
weight
などの属性を利用しているものがあります。
属性の参照¶
g.nodes[0]
とすると、頂点0の辞書を取得できます。属性は、
g.nodes[0]['name']
のようにアクセスできます。
g[0][1]
とすると、辺(0, 1)
の辞書を取得できます。属性は、
g.edges[0][1]['capacity']
のようにアクセスできます。g[0][1]
の代わりに、g.edges[0, 1]
あるいはg.get_edge_data(0, 1)
とも書けます。
nx.get_node_attributes(g, 'name')
とすると、全頂点のnameの値を辞書で取得できます。nx.get_edge_attributes(g, 'capacity')
とすると、全辺のcapacityの値を辞書で取得できます。g.nodes.data('name')
とすると、全頂点のnameの値をビュー(辞書のようなもの)で取得できます。g.edges.data('capacity')
とすると、全辺のcapacityの値をビュー(タプルのリストのようなもの)で取得できます。
補足
無向グラフに辺
(i, j)
を追加すると、辺(i, j)
としても、辺(j, i)
としても、同じものとしてアクセスできます。辺の追加は、
g.add_edge(1, 0, capacity=10)
で行いましたが、g.edges[0][1]
で参照できます。
有向グラフでは、辺
(i, j)
と辺(j, i)
は、別になります。
属性と共に一括作成¶
方法その1
add_edges_from
では、辞書を指定することもできます。
g = nx.Graph()
g.add_edges_from([(0, 3, {'weight': 10}),
(1, 2, {'weight': 15}),
(1, 3, {'weight': 20})])
方法その2
属性が1種類のときは、以下のようにadd_weighted_edges_from
を使えます。
g = nx.Graph()
g.add_weighted_edges_from(
[(0, 3, 10), (1, 2, 15), (1, 3, 20)],
weight='weight')
このように、NetworkXでは、柔軟にグラフを作成できます。
頂点の削除¶
remove_node(頂点)
:対象の頂点と、その頂点に接続する辺を削除します。remove_nodes_from(頂点のリスト)
:複数の頂点を一括で削除します。
辺の削除¶
remove_edge(辺)
:対象の辺を削除します。remove_edges_from(辺のリスト)
:複数の辺を一括で削除します。
ある頂点に接続する全ての辺を削除したとしても、その頂点は削除されません。
色々なグラフの作成¶
nx.path_graph(頂点数)
:パスからなるグラフ
nx.cycle_graph(頂点数)
:サイクルからなるグラフ
nx.ladder_graph(段数)
:はしご状のグラフ
nx.circular_ladder_graph(頂点数)
:端がつながったはしご状のグラフnx.grid_2d_graph(頂点数1, 頂点数2)
:2次元の格子グラフ
ランダムなグラフの作成¶
fast_gnp_random_graph(n, p, seed, directed)
:ランダムなグラフの作成n
:頂点の数p
:任意の2頂点の間に辺を作成する確率seed
:乱数シード(指定すると、同じ結果を返します)directed
:有向グラフかどうか
ランダムな連結グラフの作成
ランダムに作成すると、グラフが連結していない可能性があります。 以下のようにすれば、確実に連結グラフを作成できます。
while True:
g = nx.fast_gnp_random_graph(6, 0.5)
if nx.is_connected(g):
break
完全グラフの作成¶
完全グラフとは
全ての頂点間に辺が存在するグラフを完全グラフ(
complete graph
)といいます。NetworkXでは、
nx.complete_graph(頂点数)
で作成できます。頂点数を
n
とすると、辺の数はn * (n - 1) // 2
で計算できます。
参考:完全グラフ
空グラフの作成¶
空グラフとは
辺のないグラフを空グラフといいます。
nx.empty(頂点数)
で作成できます。
参考:空グラフ
補グラフの作成¶
補グラフとは
元のグラフに対して、以下のグラフを補グラフ(
complement graph
)といいます。元のグラフに辺がある → 補グラフの辺を作らない
元のグラフに辺がない → 補グラフの辺を作る
NetworkXでは、
nx.complement(元のグラフ)
で作成できます。
補グラフの補グラフは、元のグラフです。
完全グラフの補グラフは、空グラフです。
参考:補グラフ
2部グラフの作成¶
2部グラフとは
頂点集合を2つの集合
V1
とV2
に分けます。それぞれの集合内について、頂点間に辺がないグラフを2部グラフ(
bipartite graph
)といいます。NetworkXでは、
nx.bipartite
モジュールに多くの関数が定義されています。
参考:2部グラフ
完全2部グラフの作成¶
完全2部グラフとは
2部グラフで、
V1
の任意の頂点とV2
の任意の頂点の間に辺が存在するグラフを完全2部グラフ(complete bipartite graph
)といいます。NetworkXでは、
nx.complete_bipartite_graph(頂点数1, 頂点数2)
で作成できます。
参考:完全2部グラフ
完全2部グラフは、割当問題のモデルを作成するときに利用したりします。
格子グラフ¶
grid_2d_graph(m, n)
は、m x n
の格子グラフを作成します。頂点は、(i, j)というタプルになります。座標を表します。
編集不可のグラフ¶
関数 | 説明 |
---|---|
nx.freeze(g) | 編集不可のグラフ |
「凍らせる(freeze
)→変更できない」ということです。
逆向きのグラフ¶
有向グラフの向きを反転させます。
関数 | 説明 |
---|---|
nx.reverse(g) | 有向グラフの向きを反転したグラフ |
reverse
は、DiGraphかMultiDiGraphで使えます。
線グラフ¶
線グラフとは
辺を頂点とみなした新たなグラフ。
元のグラフの2辺が頂点を共有していれば、線グラフ(line graph
)の対応する頂点間に辺を作成します。
関数 | 説明 |
---|---|
nx.line_graph(g) | 線グラフ |
line_graph
は、GraphかDiGraphで使えます。
線グラフと似ているグラフに双対グラフがあります。
双対グラフとは
平面グラフに対して、「領域を頂点にして、隣接する頂点を辺で結んだグラフ」を双対グラフ(dual graph
)といいます。
参考:グラフの双対
平面グラフとは
平面グラフ(plane graph
)は、辺が交差しないグラフです。
参考:平面グラフ
線グラフの変換¶
関数 | 説明 |
---|---|
nx.inverse_line_graph(g) | 線グラフが元のグラフになるグラフ |
line_graph
は、Graphのみで使えます。
色々なグラフの作成¶
NetworkXで作成できるグラフの一部を紹介します。
関数 | 説明 |
---|---|
nx.circular_ladder_graph(頂点数) | 端がつながったはしご状のグラフ |
nx.complete_bipartite_graph(頂点数1, 頂点数2) | 完全2部グラフ |
nx.complete_graph(頂点数) | 完全グラフ |
nx.cycle_graph(頂点数) | サイクル グラフ |
nx.empty_graph(頂点数) | 空グラフ |
nx.fast_gnp_random_graph(頂点数, 辺の作成率) | ランダムグラフ |
nx.grid_graph(各次元のサイズのリスト) | 多次元の格子グラフ |
nx.grid_2d_graph(頂点数1, 頂点数2) | 2次元の格子グラフ |
nx.ladder_graph(頂点数) | はしご状のグラフ |
nx.path_graph(頂点数) | 1本のパスからなるグラフ |
nx.star_graph(頂点数) | スターグラフ |
グラフの情報や性質¶
number_of_nodes
:頂点数を返します。number_of_edges
:辺数を返します。
頂点ビューと辺ビュー¶
頂点ビュー:頂点のイテレーター。
nodes()
で取得できます。グラフオブジェクトも、頂点のイテレーターです。
辺ビュー:辺のイテレーター。
edges()
で取得できます。
一般に、ビューとはアクセス用の仮想オブジェクトです。 頂点ビューと辺ビューは、イテレーターになっています。 頂点や辺で繰り返すときに使えます。
属性つきの頂点ビューと辺ビュー¶
属性つきの頂点ビュー:
nodes(data=True)
で取得できます。属性つきの辺ビュー:
edges(data=True)
で取得できます。特定の属性つきの頂点ビュー:
nodes(data=属性名)
で取得できます。特定の属性つきの辺ビュー:
edges(data=属性名)
で取得できます。
NetworkXでdata
という単語は、頂点や辺の属性を示すときに使われます。
頂点ビューと辺ビューで、引数が不要のときは、プロパティも使えます。
nodes
:nodes()
と同じです。edges
:edges()
と同じです。
無向グラフの接続情報¶
g.neighbors(n)
:頂点nの隣接頂点(nと辺で結ばれている頂点)g.adj[n].items()
:頂点nに接続する辺と属性
特定の辺の属性は、get_edge_data
で取得できます。
たとえば、辺(1, 2)
の属性は、g.get_edge_data(1, 2)
で{'weight': 20}
になります。
有向グラフの接続情報¶
g.successors(n)
:頂点nから出ていく向きの隣接頂点g.succ[n].items()
:頂点nから出ていく辺と属性g.predecessors(n)
:頂点nに入る向きの隣接頂点g.pred[n].items()
:頂点nに入る辺と属性neighbors
は、successors
と同じです。adj
は、succ
と同じです。successor
は、「後のモノ」という意味です。predecessor
は、「前のモノ」という意味です。
次数とは¶
ある頂点に接続する辺の数を次数(degree)といいます。
全頂点の次数は、
g.degree()
で辞書のように取得できます。頂点
nd
の次数は、g.degree(nd)
で取得できます。
無向グラフ、有向グラフの確認¶
関数 | 性質 |
---|---|
nx.is_directed(g) | 有向グラフかどうか |
g.is_directed() | 有向グラフかどうか |
not nx.is_directed(g) | 無向グラフかどうか |
not g.is_directed() | 無向グラフかどうか |
単純グラフ、多重グラフの確認¶
関数 | 性質 |
---|---|
g.is_multigraph() | `g`の型が多重グラフ用のクラスかどうか |
not g.is_multigraph() | `g`の型が単純グラフ用のクラスかどうか |
補足
MultiGraph()
とMultiDiGraph()
は、空のグラフなので単純グラフです。しかし、型がMultiGraphとMultiDiGraphなので、is_multigraph()
がTrueになります。
単純グラフは、自己ループや多重辺がないグラフです。 しかし、GraphクラスとDiGraphクラスは、自己ループを作成できます。
not g.is_multigraph()
は、厳密には、「単純グラフ、または、多重辺のない多重グラフ」となります。
連結しているかどうか¶
関数 | 関数 | 性質 |
---|---|---|
無向グラフ | g.is_connected() | 連結しているか |
有向グラフ | g.is_weakly_connected() | 弱連結しているか |
有向グラフ | g.is_strongly_connected() | 強連結しているか |
2部グラフ、空グラフの確認¶
関数 | 性質 |
---|---|
nx.is_bipartite(g) | 2部グラフかどうか |
nx.is_empty(g) | 空グラフかどうか |
木、森の確認¶
関数 | 性質 |
---|---|
nx.is_tree(g) | 木かどうか |
nx.is_forest(g) | 森かどうか |
パスの確認¶
関数 | 性質 |
---|---|
nx.is_simple_path(g, 頂点リスト) | 指定されたリストの隣り合うペアが全て辺に含まれているか |
補足
is_simple_path
でチェックするのは、パスです。辺が重複する歩道や、頂点が重複する路は、たとえ全て含まれていてもFalseになります。
オイラー閉路の確認¶
オイラー路、オイラー閉路とは
オイラー路:グラフの全ての辺をちょうど1度だけ通る路
オイラー閉路:グラフの全ての辺をちょうど1度だけ通る閉路
オイラー路であれば、一筆書きで書けます。
関数 | 性質 |
---|---|
nx.is_forest(g) | オイラー閉路かどうか |
無向グラフがオイラー閉路かどうかは、下記の定理を使って簡単に調べられます。
オイラーの定理¶
無向グラフがオイラー閉路 ⇔ 連結、かつ、全頂点の次数が偶数
マッチングの確認¶
マッチングとは
互いに端点を共有しない辺の集合をマッチングといいます。
2部グラフのマッチングは、割当問題を解くのに利用したりします。
関数 | 性質 |
---|---|
nx.is_forest(g) | オイラー閉路かどうか |
たとえば、2部グラフの左側が男性、右側が女性だとします。 複数の相手と付き合っている人がいないとき、マッチングが成立します。
部分グラフとは
グラフ
G(V, E)
に対して、V1 ⊆ V
、E1 ⊆ f(E, V1)
となるG1(V1, E1)
を部分グラフ(subgraph
)といいます。f(E, V1)
は、E
の中で両端がV1
に含まれる辺の集合とします。NetworkXでは、
nx.edge_subgraph
で作成できます。
E1 = f(E, V1)
の場合、誘導部分グラフ(induced subgraph)といいます。NetworkXでは、
nx.subgraph
で作成できます。
マッチングのチェック方法
マッチングであれば、部分グラフの全頂点の次数が1になります。
is_matching(g, elst1)
は、下記のように計算できます。
all(v == 1 for k, v in g.edge_subgraph(elst1).degree())
クリークとは
完全グラフになる誘導部分グラフをクリークといいます。
有向非巡回グラフの確認¶
有向非巡回グラフとは
閉路のない有向グラフを有向非巡回グラフ(
directed acyclic graph: DAG
)といいます。DAGは、色々なアルゴリズムのデータ構造として使われます。
参考:有向非巡回グラフ
関数 | 性質 |
---|---|
nx.is_directed_acyclic_graph(g) | 有向非巡回グラフかどうか |
属性を持っているかの確認¶
全ての辺が特定の属性を持っているかどうかは、下記のように確認できます。
関数 | 性質 |
---|---|
nx.is_weighted(g) | 全辺が属性`weight`を持っているか |
edge
:一部の辺で確認したいときweight
:属性名を'weight'
以外にしたいとき
編集不可のグラフかどうか¶
nx.is_frozen(g)
で確認できます。
オイラーグラフとサイクル¶
オイラーグラフと準オイラーグラフとは
準オイラーグラフ:オイラー閉路を持つグラフ
オイラーグラフ:オイラー路を持つグラフ
関数 | 説明 |
---|---|
nx.eulerian_circuit(g) | オイラー閉路を取得 |
オイラー閉路がない場合、
nx.NetworkXError
になります。オイラー路が欲しい場合は、奇数次数の頂点間にダミーの辺を追加して、オイラー閉路を求めます。
部分的なサイクルの探索¶
部分的なサイクルを探索する関数は、以下のようなものがあります。
関数 | 対象 | 説明 |
---|---|---|
nx.find_cycle | 無向グラフ、有向グラフ | 1つのサイクル(辺リスト) |
nx.simple_cycles | 有向グラフ | 全てのサイクル(頂点リスト) |
無向グラフの連結成分¶
関数 | 説明 |
---|---|
nx.connected_components(g) | 連結成分(頂点集合)の列挙 |
connected_components
は、GraphかMultiGraphで使えます。
connected_components
では、頂点集合を列挙します。
部分グラフが欲しい場合は、以下のようにしてできます。
for c in nx.connected_components(g):
sg = g.subgraph(c) # 部分グラフ
print(sg.nodes)
有向グラフの連結成分¶
関数 | 説明 |
---|---|
nx.weakly_connected_components(g) | 弱連結成分(頂点集合)の列挙 |
nx.strongly_connected_components(g) | 強連結成分(頂点集合)の列挙 |
上記の関数は、DiGraphかMultiDiGraphで使えます。
有向グラフでは、connected_components
は使えません。