グラフ理論と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:グラフ
    • VEからなることを明示的に表す場合、G(V, E)と表記します

NetworkXのグラフの種類

NetworkXのグラフには4種類あります。

 無向グラフ有向グラフ
単純グラフなど※GraphDiGraph
多重グラフMultiGraphMultiDiGraph

※ 上表の「単純グラフなど」は、単純グラフ、または 自己ループのみ含む多重グラフを指しています。

グラフの用語

  • 単純グラフ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つの集合V1V2に分けます。
  • それぞれの集合内について、頂点間に辺がないグラフを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部グラフは、割当問題のモデルを作成するときに利用したりします。

参考:割当問題 - ORWiki

格子グラフ

  • 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という単語は、頂点や辺の属性を示すときに使われます。

頂点ビューと辺ビューで、引数が不要のときは、プロパティも使えます。

  • nodesnodes()と同じです。
  • edgesedges()と同じです。

無向グラフの接続情報

  • g.neighbors(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()多重グラフかどうか
not g.is_multigraph()単純グラフかどうか

補足

単純グラフは、自己ループや多重辺がないグラフです。 しかし、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 VE1 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は使えません。