SciPy グラフ構造

グラフ構造はアルゴリズム学において最も強力なフレームワークの一つです。

グラフは様々な関係のノードとエッジの集合であり、ノードはオブジェクトに対応する頂点、エッジはオブジェクト間の接続です。

SciPy はグラフ構造を処理するための scipy.sparse.csgraph モジュールを提供しています。

隣接行列

隣接行列（Adjacency Matrix）は、頂点間の隣接関係を表す行列です。

隣接行列の論理構造は、V と E の2つの集合に分けられます。ここで、V は頂点、E は辺であり、辺にはノード間の接続の強さを表す重みがある場合があります。

1次元配列でグラフ内のすべての頂点データを格納し、2次元配列で頂点間の関係（辺または弧）のデータを格納します。この2次元配列を隣接行列と呼びます。

次の図の例を見てみましょう：

頂点は A、B、C で、辺の重みは 1 と 2 です。

A と B は接続されており、重みは 1 です。

A と C は接続されており、重みは 2 です。

C と B は接続されていません。

この隣接行列は、次の2次元配列で表すことができます：
     A B C
   A:[0 1 2]  
   B:[1 0 0]
   C:[2 0 0]

隣接行列は、有向グラフの隣接行列と無向グラフの隣接行列に分けられます。

無向グラフは双方向の関係であり、辺に方向はありません：

有向グラフの辺には方向があり、単方向の関係です：

注：上記2つの図の D ノードは自己ループです。自己ループとは、1つの辺の両端が同じノードであることを指します。

連結成分

すべての連結成分を確認するには、connected_components() メソッドを使用します。

例

import numpy as np
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix

arr = np.array([
  [0, 1, 2],
  [1, 0, 0],
  [2, 0, 0]
])

newarr = csr_matrix(arr)

print(connected_components(newarr))

上記のコードの出力結果は次のとおりです：

(1, array([0, 0, 0], dtype=int32))

Dijkstra -- 最短経路アルゴリズム

Dijkstra（ダイクストラ）最短経路アルゴリズムは、あるノードから他のすべてのノードへの最短経路を計算するために使用されます。

Scipy は dijkstra() メソッドを使用して、ある要素から他の要素への最短経路を計算します。

dijkstra() メソッドでは、以下のパラメータを設定できます：
  1. return_predecessors:ブール値。True に設定するとすべての経路を走査します。すべての経路を走査したくない場合は False に設定できます。
  2. indices:要素のインデックス。その要素のすべての経路を返します。
  3. limit:経路の最大重み。

例

要素 1 から 2 への最短経路を検索します：

import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

arr = np.array([
  [0, 1, 2],
  [1, 0, 0],
  [2, 0, 0]
])

newarr = csr_matrix(arr)

print(dijkstra(newarr, return_predecessors=True, indices=0))

上記のコードの出力結果は次のとおりです：

(array([ 0.,  1.,  2.]), array([-9999,     0,     0], dtype=int32))

Floyd Warshall -- フロイド-ワーシャル法

フロイド-ワーシャル法は、任意の2点間の最短経路を求めるアルゴリズムです。

Scipy は floyd_warshall() メソッドを使用して、すべての要素ペア間の最短経路を検索します。

例

すべての要素ペア間の最短経路を検索します：

import numpy as np
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

arr = np.array([
  [0, 1, 2],
  [1, 0, 0],
  [2, 0, 0]
])

newarr = csr_matrix(arr)

print(floyd_warshall(newarr, return_predecessors=True))

上記のコードの出力結果は次のとおりです：

(array([[ 0.,  1.,  2.],
       [ 1.,  0.,  3.],
       [ 2.,  3.,  0.]]), array([[-9999,     0,     0],
       [    1, -9999,     0],
       [    2,     0, -9999]], dtype=int32))

Bellman Ford -- ベルマン-フォード法

ベルマン-フォード法は、任意の2点間の最短経路を求めるアルゴリズムです。

Scipy は bellman_ford() メソッドを使用して、すべての要素ペア間の最短経路を検索します。これは通常、有向グラフや負の重みの辺を持つグラフを含む、あらゆるグラフで使用できます。

例

負の重みを持つ辺を使用したグラフで、要素 1 から要素 2 への最短経路を検索します：

import numpy as np
from scipy.sparse.csgraph import bellman_ford
from scipy.sparse import csr_matrix

arr = np.array([
  [0, -1, 2],
  [1, 0, 0],
  [2, 0, 0]
])

newarr = csr_matrix(arr)

print(bellman_ford(newarr, return_predecessors=True, indices=0))

上記のコードの出力結果は次のとおりです：

(array([ 0., -1.,  2.]), array([-9999,     0,     0], dtype=int32))

深さ優先順序

depth_first_order() メソッドは、あるノードから深さ優先探索の順序を返します。

以下のパラメータを受け取ることができます：

  • 图
  • グラフの走査を開始する要素

例

隣接行列が与えられた場合、深さ優先探索の順序を返します：

import numpy as np
from scipy.sparse.csgraph import depth_first_order
from scipy.sparse import csr_matrix

arr = np.array([
  [0, 1, 0, 1],
  [1, 1, 1, 1],
  [2, 1, 1, 0],
  [0, 1, 0, 1]
])

newarr = csr_matrix(arr)

print(depth_first_order(newarr, 1))

上記のコードの出力結果は次のとおりです：

(array([1, 0, 3, 2], dtype=int32), array([    1, -9999,     1,     0], dtype=int32))

幅優先順序

breadth_first_order() メソッドは、あるノードから幅優先探索の順序を返します。

以下のパラメータを受け取ることができます：

  • 图
  • グラフの走査を開始する要素

例

隣接行列が与えられた場合、幅優先探索の順序を返します：

import numpy as np
from scipy.sparse.csgraph import breadth_first_order
from scipy.sparse import csr_matrix

arr = np.array([
  [0, 1, 0, 1],
  [1, 1, 1, 1],
  [2, 1, 1, 0],
  [0, 1, 0, 1]
])

newarr = csr_matrix(arr)

print(breadth_first_order(newarr, 1))

上記のコードの出力結果は次のとおりです：

(array([1, 0, 2, 3], dtype=int32), array([    1, -9999,     1,     1], dtype=int32))
その他の拡張