SciPyでグラフの連結判定・連結成分の個数取得: connected_components
SciPyの関数scipy.sparse.csgraph.connected_components()を使うと、グラフ（無向グラフ・有向グラフ）の連結成分の個数を取得して、連結グラフであるかを判定したりできる。
ここでは以下の内容について説明する。
- 連結グラフと
scipy.sparse.csgraph.connected_components() connected_components()の基本的な使い方- 個数のみ取得: 引数
return_labels - 強連結成分の個数取得・判定: 引数
directed,connection - 重み付きグラフの場合
以下の説明内容およびサンプルコードはSciPy1.3.1のもの。バージョンが違うと挙動が異なる場合があるので注意。
なお、scipy.sparse.csgraph.connected_components()はSciPy0.11.0で追加された。AtCoderでも使える。
連結グラフとscipy.sparse.csgraph.connected_components()
連結グラフおよび連結成分の説明は以下の通り。
連結グラフ（れんけつグラフ、connected graph）は、グラフ上の任意の2頂点間に道が存在するグラフのことである。連結でないグラフを非連結グラフ (disconnected graph) と呼ぶ。極大で連結な部分グラフは、連結成分 (connected component) という。
連結グラフ - Wikipedia
極大で連結な部分グラフというのが分かりにくいかもしれないが、言葉からのイメージ通りに考えて恐らく間違いない。
┌---(0)---┐ ┌---(0)---┐
| | | |
| | | |
(1)-------(2) (1)-------(2)
|
(3)-------(4) (3)-------(4)
上の図の左側は任意の2頂点間に経路（道）が存在するので連結グラフ。0, 1, 2, 3, 4が1つの連結成分となっている。連結成分が1つであればそのグラフは連結グラフであるといえる。
右側は0, 1, 2と3, 4を結ぶ経路がないので非連結グラフであり、0, 1, 2と3, 4の2つの連結成分を持つ。
上の図は無向グラフだが、有向グラフの場合は強連結という考え方がある。後述。
ソースコードによると、scipy.sparse.csgraph.connected_components()ではTarjan's algorithmによって連結成分を求めており、計算量はO(E + V)（Eは辺の数、Vは頂点の数）とのこと。
Uses an iterative version of Tarjan's algorithm to find the
strongly connected components of a directed graph represented as a
sparse matrix (scipy.sparse.csc_matrix or scipy.sparse.csr_matrix).
The algorithmic complexity is for a graph with E edges and V
vertices is O(E + V).
The storage requirement is 2*V integer arrays.
scipy/_traversal.pyx at v1.3.0 · scipy/scipy
connected_components()の基本的な使い方
以下の隣接行列のグラフを例とする。
import numpy as np
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix
l = [[0, 1, 1, 0, 0],
[0, 0, 1, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 1],
[0, 0, 0, 0, 0]]
┌---(0)---┐
1 1
↓ ↓
(1)---1-->(2)
(3)---1-->(4)
connected_components()の第一引数にリストを指定するとエラーとなる。NumPy配列ndarrayだとOK。
# n, labels = connected_components(l)
# AttributeError: 'list' object has no attribute 'dtype'
a = np.array(l)
print(type(a))
# <class 'numpy.ndarray'>
n, labels = connected_components(a)
print(n)
# 2
print(labels)
# [0 0 0 1 1]
返り値は、連結成分の個数と、各頂点が属する連結成分のラベル。例の場合、0, 1, 2が同じ連結成分、3, 4が同じ連結成分であることを示している。
デフォルト（後述の引数directed=True, connection='weak'）では有向グラフでも向きは考慮されない。例の場合、2から0, 1に至る経路や4から3に至る経路は存在しないが、向きを問わず頂点間に経路が存在していればつながっているとみなされる。
第一引数にはscipy.sparse行列（疎行列）も指定可能。
csr = csr_matrix(l)
print(csr)
# (0, 1) 1
# (0, 2) 1
# (1, 2) 1
# (3, 4) 1
print(type(csr))
# <class 'scipy.sparse.csr.csr_matrix'>
n, labels = connected_components(csr)
print(n)
# 2
print(labels)
# [0 0 0 1 1]
csr_matrixは重みと頂点のリストから生成することも可能。
n = 5
d = [1, 1, 1, 1]
i = [0, 0, 1, 3]
j = [1, 2, 2, 4]
csr = csr_matrix((d, (i, j)), (n, n))
print(csr)
# (0, 1) 1
# (0, 2) 1
# (1, 2) 1
# (3, 4) 1
connected_components()の内部ではnumpy.ndarrayであってもcsc_matrixなど他の形式のscipy.sparse行列であっても、すべてcsr_matrixに変換される。最初からcsr_matrixを生成できるのであればそちらのほうが効率的。
scipy.sparse行列（疎行列）の生成などについての詳細は以下の記事を参照。
個数のみ取得: 引数return_labels
connected_components()の引数return_labelsをFalse（デフォルトはTrue）とすると、ラベルを示す配列は返されず、連結成分の個数のみが返される。
print(connected_components(csr, return_labels=False))
# 2
強連結成分の個数取得・判定: 引数directed, connection
引数directedとconnectionによって、どのような状態を連結とみなすかを設定できる。
上述のように、デフォルト（directed=True, connection='weak'）では、向きを問わず頂点間に経路が存在していればその頂点間はつながっているとみなされる。
directed=True（デフォルト）, connection='strong'とすると、有向グラフにおいて、頂点iと頂点jに対してiからjへの経路とjからiの経路が両方とも存在しているときのみ、その頂点間はつながっているとみなされる。
グラフ上の任意の2頂点間に双方向の経路が存在しているグラフを強連結グラフ、そのような連結成分を強連結成分という。
以下のグラフを例とする。両端に矢がある矢印は両方の向きの経路が存在していることを意味している。
ld = [[0, 1, 1, 0, 0],
[1, 0, 1, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 1],
[0, 0, 0, 1, 0]]
┌-->(0)---┐
1 1
↓ ↓
(1)---1-->(2)
(3)<--1-->(4)
デフォルトでは最初の例と同じ結果。
n, labels = connected_components(csr_matrix(ld))
print(n)
# 2
print(labels)
# [0 0 0 1 1]
connection='strong'とすると以下のような結果となる。
n, labels = connected_components(csr_matrix(ld), connection='strong')
print(n)
# 3
print(labels)
# [1 1 0 2 2]
0, 1から2に至る経路はあるが2から0, 1へ至る経路はないため、0, 1と2は同じ連結成分とはみなされない。
次の例は以下のグラフ。
ld2 = [[0, 1, 0, 0, 0],
[0, 0, 1, 0, 0],
[1, 0, 0, 0, 0],
[0, 0, 0, 0, 1],
[0, 0, 0, 1, 0]]
┌---(0)<--┐
1 1
↓ |
(1)---1-->(2)
(3)<--1-->(4)
この場合の0, 1, 2はそれぞれ行き来できる経路が存在するため、connection='strong'としても一つの連結成分とみなされる。
n, labels = connected_components(csr_matrix(ld2), connection='strong')
print(n)
# 2
print(labels)
# [0 0 0 1 1]
directed=Falseとすると向きが考慮されなくなり、頂点間に経路が存在していればその頂点間はつながっているとみなされる。directed=Falseの場合はconnectionの値は無視される。
n, labels = connected_components(csr_matrix(ld), directed=False, connection='strong')
print(n)
# 2
print(labels)
# [0 0 0 1 1]
結局、directed=Falseとdirected=True, connection='weak'（デフォルト）は同じ状態。directed=True, connection='strong'のときのみ強連結成分の個数取得・判定となる。
重み付きグラフの場合
connected_components()では辺の重みは考慮されない。0でなければ負の値でもなんでも経路が存在するとみなされる。
これまでの例ではすべての辺の重み（コスト）を1としていたが、その値を変えても同じ結果となる。
lw = [[0, 8, 5.2, 0, 0],
[0, 0, 3, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, -2],
[0, 0, 0, 0, 0]]
n, labels = connected_components(csr_matrix(lw))
print(n)
# 2
print(labels)
# [0 0 0 1 1]