グラフ構造は、アルゴリズムで最も強力なフレームワークの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()メソッドは、以下のパラメータを設定できます。
return_predecessors
:ブール値であり、Trueを設定し、すべてのパスをトラバースします。すべてのパスをトラバースしたくない場合は、Falseに設定します。indices
:要素のインデックス。要素のすべてのパスを返します。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))
コメントを残す