SciPy グラフ構造

グラフ構造は、アルゴリズムで最も強力なフレームワークの1つです。

グラフは、さまざまな関係の節(ノード)と枝(エッジ)の集合です。ノードはオブジェクトに対応する頂点であり、エッジはオブジェクト間の結合です。

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ノードは自己ループです。これは、エッジの両端が同じノードであることを意味します。

コンポーネント接続

接続されているすべてのコンポーネントを表示するには、 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(ダイクストラ)最短経路問題は、1つのノードから他のすべてのノードへの最短経路を計算するために使用されます。

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))
Share

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です