A. Lucas, Front. Phys. (2014) 掲載例題の実装と解説 ー グラフ同型性判定問題¶
本サンプルコードでは、論文 A. Lucas, "Ising formulations of many NP problems", Front. Phys. (2014) で紹介されている『グラフ同型性判定問題』に Fixstars Amplify を用いて取り組みます。同論文に紹介されている他の NP 完全・NP 困難な問題も以下で解説しています（カッコ内は論文内で問題に対応する節番号）。
- グラフの分割問題（2.2節）
- 最大クリーク問題（2.3節）
- 厳密被覆問題（4.1節）
- 集合パッキング問題（4.2節）
- 最小頂点被覆問題（4.3節）
- 充足可能性問題（SAT）（4.4節）
- 最小極大マッチング問題（4.5節）
- グラフ彩色問題（6.1節）
- クリーク被覆問題（6.2節）
- 整数長ジョブスケジューリング問題（6.3節）
- ハミルトン閉路問題（7.1節）
- 有向帰還頂点集合問題（8.3節）
- 最小帰還辺集合問題（8.5節）
- グラフ同型性判定問題（9節）
グラフ同型性判定問題¶
2 つの (単純) グラフが 同型 であるとは、それらの頂点同士の 1 対 1 対応 (同型写像) があって、片方のグラフの 2 つの頂点が辺で結ばれているならば、もう片方のグラフにおいてもそれらと対応する 2 つの頂点が辺で結ばれていることをいいます。 別の言い方をすると、2 つのグラフを、それぞれ頂点をうまく並べて描画すると同じ絵になるとき、それらは同型となります。
一般に、グラフのサイズが大きいとき、2 つのグラフが同型であるかどうかを現実的な時間で判定することは困難です。ここでは、Fixstars Amplify を用いて同型写像を探索するプログラムを作成します。本サンプルプログラムの定式化は A. Lucas, Front. Phys. (2014) の 9 節のものに沿って行います。
問題の作成¶
まず、NetworkX を用いて適当なグラフ $G_1$ と $G_2$ を作成します。このとき、 $G_1$ と $G_2$ が同型になるようにしておきます。
import networkx as nx
N = 5 # グラフの頂点の数
G1 = nx.Graph()
G1.add_nodes_from(range(N))
edge_list1 = [(0, 1), (0, 4), (1, 2), (2, 3), (3, 4)]
G1.add_edges_from(edge_list1)
pos1 = nx.circular_layout(G1)
nx.draw_networkx(G1, node_size=600, font_color="w", pos=pos1)
G2 = nx.Graph()
G2.add_nodes_from(range(N))
edge_list2 = [(0, 2), (0, 3), (1, 3), (1, 4), (2, 4)]
G2.add_edges_from(edge_list2)
pos2 = nx.circular_layout(G2)
nx.draw_networkx(G2, node_size=600, font_color="w", pos=pos2)
これらの 2 つのグラフをたとえば以下の図のように対応させると同型写像となります。片方のグラフにおいて、 色 A の頂点と色 B の頂点が辺で結ばれているとき、もう片方のグラフにおいても 色 A の頂点と色 B の頂点が辺で結ばれていることを確認してください（ここでは各頂点に記載の番号は無視してください）。
定式化¶
$G_1$ と $G_2$ の頂点数が異なる場合は明らかに同型ではないので、以下 $G_1$ と $G_2$ の頂点数が同じ場合のみ考えます。$G_1$ の頂点数を $N$ とします。次のように定式化を行います。
決定変数¶
2 つのグラフの対応付けを表すために、$N\times N$ のバイナリ変数テーブル $q$ を用意します。 $G_1$ の $i$ 番目の頂点と $G_2$ の $j$ 番目の頂点が対応しているとき、$q$ の $i$ 行 $j$ 列が $1$ となるようにします。
たとえば、上の図において、辺で結ばれている頂点の番号と色の対応を $G_1$, $G_2$ で比較すると、2 つのグラフは以下のように対応していました。
| G1 の頂点 | G2 の頂点 | 頂点の色 |
|---|---|---|
| 0 | 0 | 青 |
| 1 | 2 | 橙 |
| 2 | 4 | 緑 |
| 3 | 1 | 赤 |
| 4 | 3 | 紫 |
これをバイナリ変数 $q$ のテーブルで表すと、以下のようになります。
| G1 \ G2 | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 0 | 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 0 | 0 |
| 2 | 0 | 0 | 0 | 0 | 1 |
| 3 | 0 | 1 | 0 | 0 | 0 |
| 4 | 0 | 0 | 0 | 1 | 0 |
目的関数¶
グラフ同型性判定問題は条件をみたすものを見つける問題なので、目的関数を考慮する必要はありません。
制約条件¶
$q$ が同型写像を表すためには、以下が必要です。
-
条件 1： $G_1$ のそれぞれの頂点は、$G_2$ の頂点 $1$ つと対応している。つまり、$q$ の各行には $1$ つだけ $1$ がある。
-
条件 2： $G_2$ のそれぞれの頂点は、$G_1$ の頂点 $1$ つと対応している。つまり、$q$ の各列には $1$ つだけ $1$ がある。
-
条件 3： $G_1$ の頂点 $u$ と $v$ が辺で結ばれているならば、$u$, $v$ と対応する $G_2$ の $2$ つの頂点も辺で結ばれている。
-
条件 4： $G_2$ の頂点 $s$ と $t$ が辺で結ばれているならば、$s$, $t$ と対応する $G_1$ の $2$ つの頂点も辺で結ばれている。
条件 1 と条件 2 は、
\begin{align*} \sum_{j = 0}^{N-1} q_{i, j} = 1 \quad & \text{for} \quad i \in \{0, 1, \ldots, N-1\} \\ \sum_{i = 0}^{N-1} q_{i, j} = 1 \quad & \text{for} \quad j \in \{0, 1, \ldots, N-1\} \end{align*}
で表せます。
条件 3 は、「$G_1$ の頂点 $u$ と $v$ が辺で結ばれていて、$G_2$ の頂点 $s$ と $t$ が辺で結ばれていないとき、 $u$ と $s$ 、$v$ と $t$ がそれぞれ対応していることがあってはならない」と言い換えられるので、
$$ q_{u, s} q_{v, t} = 0 \quad \text{for} \quad (u\rightarrow v) \in E_1, (s\rightarrow t) \notin E_2 $$
で表すことができます。ここで、$E_1$, $E_2$ はそれぞれ $G_1$, $G_2$ の辺集合です。
同様に、条件 4 は
$$ q_{u, s} q_{v, t} = 0 \quad \text{for} \quad (u\rightarrow v) \notin E_1, (s\rightarrow t) \in E_2 $$
で表せます。
逆に、条件 1-4 が成り立っていれば、グラフ $G_1$ と $G_2$ は同型となります。
以上で、グラフ同型性判定問題の定式化ができました。
実装¶
上で作成した問題と定式化を使って、実際に問題を解いてみましょう。まず、VariableGenerator によりバイナリ決定変数 $q$ を作成します。
from amplify import VariableGenerator
gen = VariableGenerator()
q = gen.array("Binary", shape=(N, N))
次に、条件 1 と 2 に対応する制約条件を作成します。これらは、$q$ のそれぞれの行と列にひとつだけ $1$ があるという条件でしたので、one_hot
を使って書くことができます。axis パラメータに 1 を指定すると二次元配列の各行に対する one-hot 制約を一度に生成でき、0 を指定すると各列に対する one-hot
制約を一度に生成できます。
from amplify import one_hot
constraint1 = one_hot(q, axis=1)
constraint2 = one_hot(q, axis=0)
条件 3 と 4 に対応する制約条件を作成します。条件 3 は、$q_{u, s} q_{v, t} = 0 \bigl((u\rightarrow v) \in E_1, (s\rightarrow t) \notin E_2 \bigr)$ という制約で、条件 4 は条件 3 の $G_1$ と $G_2$ を入れ替えたものです。
from amplify import equal_to, sum as amplify_sum
constraint3 = amplify_sum(
equal_to(q[u, s] * q[v, t], 0) + equal_to(q[u, v] * q[v, s], 0)
for (u, v) in G1.edges
for (s, t) in nx.non_edges(G2)
)
constraint4 = amplify_sum(
equal_to(q[u, s] * q[v, t], 0) + equal_to(q[u, v] * q[v, s], 0)
for (u, v) in nx.non_edges(G1)
for (s, t) in G2.edges
)
作成した制約条件をまとめて、組合せ最適化モデルを構築します。
model = constraint1 + constraint2 + constraint3 + constraint4
クライアントを設定して、Amplify Annealing Engine (AE) で求解を行います。
from amplify import FixstarsClient, solve
from datetime import timedelta
client = FixstarsClient()
# client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx" # ローカル環境等で使用する場合は、Fixstars Amplify AE のアクセストークンを入力してください。
client.parameters.timeout = timedelta(milliseconds=1000) # タイムアウト 1000 ms
# 求解の実行
result = solve(model, client)
同型写像が見つかったかどうかを確認します。Amplify SDK は制約条件をみたす解を自動でフィルターするので、result が空でなければ同型写像が見つかったと分かります。
if len(result) == 0:
print("同型写像が見つかりませんでした。")
else:
print("同型写像が見つかりました。")
最後に、同型写像である 2 つのグラフの対応する頂点同士を同じ色で表示します。
import matplotlib.pyplot as plt
import numpy as np
values = q.evaluate(result.best.values)
# G1 の頂点 i と G2 の頂点 vertex_map[i] が対応する
vertex_map = np.where(values == 1)[1]
colors = np.array([f"C{i}" for i in range(N)])
# G2 の i 番目の頂点を i 番目の色で塗ることにする
colors2 = colors
# G1 の i 番目の頂点は G2 の vertex_map[i] 番目の頂点と同じ色で塗る
colors1 = colors[vertex_map]
# 描画
fig, ax = plt.subplots(nrows=1, ncols=2, figsize=(12, 4))
nx.draw_networkx(
G1, node_size=600, node_color=colors1, font_color="w", pos=pos1, ax=ax[0]
)
nx.draw_networkx(
G2, node_size=600, node_color=colors2, font_color="w", pos=pos2, ax=ax[1]
)
