グラフ描画ライブラリと最大独立集合 (MIS) 問題の求解¶

Hi-QUBO 簡易グラフ描画ライブラリ

Hi-QUBO には,グラフ理論的問題から得られた結果を可視化するための簡易グラフ描画ライブラリが付属しています. これは Graphviz のラッパーであり,Ubuntu では以下のようにインストールできます：

このライブラリを使用するには,qbpp/graph.hpp をインクルードします：

graph-visualization-library-program1.cpp¶

#include <qbpp/graph.hpp>

このライブラリは DOT 入力を生成し,neato を呼び出してグラフを描画します.

警告: このヘッダオンリーライブラリは,Hi-QUBO サンプルプログラムで得られた結果の可視化を目的としています. API や動作は予告なく変更される可能性があり,ミッションクリティカルなアプリケーションでの使用は推奨しません.

最大独立集合 (MIS) 問題

無向グラフ \(G=(V,E)\) の独立集合とは,\(S\) 内のどの2頂点も \(E\) の辺で結ばれていないような頂点部分集合 \(S\subseteq V\) のことです. 最大独立集合 (MIS) 問題は,最大の要素数を持つ独立集合を求める問題です.

MIS 問題は以下のように QUBO として定式化できます. \(G\) が \(0\) から \(n-1\) までの番号が付けられた \(n\) 個の頂点を持つとします. \(n\) 個のバイナリ変数 \(x_i\) \((0\le i\le n-1)\) を導入し,\(x_i=1\) は頂点 \(i\) が \(S\) に含まれることを表します. \(|S|=\sum_{i=0}^{n-1}x_i\) を最大化したいので,以下の目的関数を最小化します：

\[ \begin{aligned} \text{objective} = -\sum_{i=0}^{n-1} x_i . \end{aligned} \]

独立性を保証するために,すべての辺 \((i,j)\in E\) について両端点を同時に選択してはなりません. これは以下のペナルティで表現できます：

\[ \begin{aligned} \text{constraint} = \sum_{(i,j)\in E} x_i x_j . \end{aligned} \]

目的関数とペナルティを組み合わせると,以下の QUBO 関数が得られます：

\[ \begin{aligned} f = \text{objective} + 2\times\text{constraint}. \end{aligned} \]

ペナルティ係数 \(2\) は,集合サイズの増加よりも実行可能性を優先するのに十分な値です.

MIS 問題の Hi-QUBO プログラム

上記の MIS 問題の QUBO 定式化に基づき,以下の Hi-QUBO プログラムは 16 ノードのインスタンスを解きます.辺は edges に格納され,得られた解は Hi-QUBO グラフ描画ライブラリを用いて可視化されます：

graph-visualization-library-program2.cpp¶

#include <qbpp/qbpp.hpp>
#include <qbpp/exhaustive_solver.hpp>
#include <qbpp/graph.hpp>

int main() {
  const size_t N = 16;
  std::vector<std::pair<size_t, size_t>> edges = {
      {0, 1},   {0, 2},   {1, 3},   {1, 4},   {2, 5},  {2, 6},
      {3, 7},   {3, 13},  {4, 6},   {4, 7},   {5, 8},  {6, 8},
      {6, 14},  {7, 14},  {8, 9},   {9, 10},  {9, 12}, {10, 11},
      {10, 12}, {11, 13}, {12, 14}, {13, 15}, {14, 15}};

  auto x = qbpp::var("x", N);

  auto objective = -qbpp::sum(x);
  auto constraint = qbpp::toExpr(0);
  for (const auto& e : edges) {
    constraint += x[e.first] * x[e.second];
  }
  auto f = objective + constraint * 2;
  f.simplify_as_binary();

  auto solver = qbpp::ExhaustiveSolver(f);
  auto sol = solver.search();

  std::cout << "objective = " << objective(sol) << std::endl;
  std::cout << "constraint = " << constraint(sol) << std::endl;

  qbpp::graph::GraphDrawer graph;
  for (size_t i = 0; i < N; ++i) {
    graph.add_node(qbpp::graph::Node(i).color(sol(x[i])));
  }
  for (const auto& e : edges) {
    graph.add_edge(qbpp::graph::Edge(e.first, e.second));
  }
  graph.write("mis.svg");
}

N = 16 個のバイナリ変数のベクトル x に対して,上記の QUBO 定式化に従って式 objective,constraint,f を構築します. Exhaustive Solver を用いて f の最適解を求め,sol に格納します.sol における objective と constraint の値が出力されます.

次に,qbpp::graph::GraphDrawer オブジェクト graph を作成します.i のループでは,ラベル i を持つ qbpp::graph::Node オブジェクトが作成され,color() メンバ関数により sol における x[i] の値に応じて色が 0 または 1 に設定されます.各ノードは add_node() を使って graph に追加されます.

同様に,辺のループでは,各辺に対して qbpp::graph::Edge(e.first, e.second) オブジェクトが作成され,add_edge() を使って graph に追加されます.最後に,graph.write("mis.svg") がグラフを描画し,結果の画像を mis.svg に書き出します.

このプログラムの出力は以下の通りです：

objective = -7
constraint = 0

これは,得られた解が 7 個のノードを選択し,すべての制約を満たしていることを意味します.描画された画像は mis.svg として保存されます：

MIS問題の解

Hi-QUBO 簡易グラフ描画ライブラリの API

Hi-QUBO 簡易グラフ描画ライブラリは以下のクラスを提供します：

qbpp::graph::Node: ラベル,色,線幅,位置などのノード情報を格納します.
qbpp::graph::Edge: 2つの端点ノード,有向・無向の区別,色,線幅などの辺情報を格納します.
qbpp::graph::GraphDrawer: グラフを構成する qbpp::graph::Node と qbpp::graph::Edge のベクトルを格納します.

qbpp::graph::Node

Node(std::string s): ラベルが s であるノードを構築します.
Node(size_t i) ラベルが std::to_string(i) であるノードを構築します.
color(std::string s) ノードの色を s に設定します.#RRGGBB の形式である必要があります.
color(int i): ノードの色をカラーパレットの i 番目のエントリに設定します.デフォルトの色 0 は白です.
penwidth(float f): ノードの輪郭を描画する線幅を f に設定します.
position(float x, float y): ノードの位置を (x, y) に設定します.

qbpp::graph::Edge

以下のコンストラクタとメンバ関数がサポートされています：

Edge(std::string from, std::string to): ラベルが from と to であるノードを結ぶ辺を構築します.
Edge(size_t from, size_t to); ラベルが std::to_string(from) であるノードとラベルが std::to_string(to) であるノードを結ぶ辺を構築します.
directed(): 辺を有向辺として設定します.
color(std::string s): 辺の色を s に設定します.#RRGGBB の形式である必要があります.
color(int i): 辺の色をカラーパレットの i 番目のエントリに設定します.デフォルトの色 0 は黒です.
penwidth(float f): 辺を描画する線幅を f に設定します.

qbpp::graph::GraphDrawer

以下のメンバ関数がサポートされています：

add_node(const Node& node): ノードをグラフに追加します.
add_edge(const Edge& edge): 辺をグラフに追加します.
write(std::string file_name): グラフを描画し,file_name に書き出します. 対応フォーマットは svg,png,jpg,pdf（Graphviz 経由）です. 出力フォーマットはファイルの拡張子によって決定されます.

PyQBPP でのグラフ可視化

Hi-QUBO のC++版には,Graphviz をラップした簡易グラフ描画ライブラリ（qbpp::graph::GraphDrawer）が付属しており,グラフを svg / png / jpg / pdf に直接出力できます.詳細は C++ 版のグラフライブラリのページを参照してください.

PyQBPP には専用のグラフクラスはありません.その代わりに,Python エコシステムで広く使われている以下のライブラリを使ってグラフを可視化できます:

networkx — グラフデータ構造とレイアウトアルゴリズム
matplotlib — 作図と画像出力

インストールは以下のコマンドで行えます:

pip install networkx matplotlib

このページの以降では,最大独立集合（MIS）問題を QUBO として定式化し,PyQBPP で解き,得られた結果を networkx + matplotlib で可視化する方法を説明します.

注意: 以下に示す可視化コードは,PyQBPP のサンプルプログラムで得られた結果を例示する目的のものです. API が変更され得るサードパーティライブラリに依存しているため,ミッションクリティカルなアプリケーションでの使用は推奨しません.

最大独立集合（MIS）問題

無向グラフ \(G=(V,E)\) の独立集合とは,\(S\) 内のどの2頂点も \(E\) の辺で接続されていないような頂点の部分集合 \(S\subseteq V\) のことです. 最大独立集合（MIS）問題は,要素数が最大の独立集合を求める問題です.

MIS問題は以下のようにQUBOとして定式化できます. \(G\) が \(0\) から \(n-1\) までインデックス付けされた \(n\) 個の頂点を持つとします. \(n\) 個のバイナリ変数 \(x_i\) \((0\le i\le n-1)\) を導入し,\(x_i=1\) であることと頂点 \(i\) が \(S\) に含まれることを同値とします. \(\|S\|=\sum_{i=0}^{n-1}x_i\) を最大化したいので,以下の目的関数を最小化します:

\[ \begin{aligned} \text{objective} = -\sum_{i=0}^{n-1} x_i . \end{aligned} \]

独立性を保証するために,すべての辺 \((i,j)\in E\) に対して,両端点を同時に選択してはなりません. これは以下のペナルティで表現できます:

\[ \begin{aligned} \text{constraint} = \sum_{(i,j)\in E} x_i x_j . \end{aligned} \]

目的関数とペナルティを組み合わせると,以下のQUBO関数が得られます:

\[ \begin{aligned} f = \text{objective} + 2\times\text{constraint}. \end{aligned} \]

ペナルティ係数 \(2\) は,集合サイズの増加よりも実行可能性を優先するのに十分です.

MIS問題のPyQBPPプログラム

上記のMIS問題のQUBO定式化に基づき,以下のPyQBPPプログラムは16ノードのインスタンスを解きます.辺は edges に格納されています:

graph-visualization-library-program1.py¶

import pyqbpp as qbpp

N = 16
edges = [
    (0, 1),  (0, 2),  (1, 3),  (1, 4),  (2, 5),  (2, 6),
    (3, 7),  (3, 13), (4, 6),  (4, 7),  (5, 8),  (6, 8),
    (6, 14), (7, 14), (8, 9),  (9, 10), (9, 12), (10, 11),
    (10, 12),(11, 13),(12, 14),(13, 15),(14, 15)]

x = qbpp.var("x", shape=N)

objective = -qbpp.sum(x)
constraint = qbpp.expr()
for u, v in edges:
    constraint += x[u] * x[v]
f = objective + constraint * 2
f.simplify_as_binary()

solver = qbpp.ExhaustiveSolver(f)
sol = solver.search()

print(f"objective = {sol(objective)}")
print(f"constraint = {sol(constraint)}")

print("Selected nodes:", end="")
for i in range(N):
    if sol(x[i]) == 1:
        print(f" {i}", end="")
print()

qbpp.var("x", shape=N) によって生成された N = 16 個のバイナリ変数のベクトル x に対して,上記のQUBO定式化に従って式 objective,constraint,f が構築されます.ここで qbpp.expr() はゼロ式を生成し,辺に関するペナルティ和のアキュムレータとして機能し,qbpp.sum(x) は x のすべての要素の和を計算します.続いて f.simplify_as_binary() により,バイナリ(0/1)ルールに基づく同類項のマージなどの簡約が in-place に適用されます.

次にExhaustive Solverを使用して f の最適解を求め,sol に格納します.sol(objective) と sol(constraint) によって sol における objective と constraint の評価値が得られ,表示されます.最後に,インデックス i をループし,sol(x[i]) == 1 を判定することで解におけるバイナリ変数 x[i] の値を評価し,選択されたノードの一覧を出力します.

このプログラムは以下の出力を生成します:

objective = -7
constraint = 0
Selected nodes: 0 3 4 5 9 11 15

これは,得られた解が7個のノードを選択し,すべての制約を満たしていることを意味します.

matplotlib と networkx による可視化

以下のコードは,matplotlib と networkx を使用して MIS の解を可視化します.上記のプログラムの末尾に追加し,edges,N,x,sol が有効な状態で実行してください:

graph-visualization-library-program2.py¶

import matplotlib.pyplot as plt
import networkx as nx

G = nx.Graph()
G.add_nodes_from(range(N))
G.add_edges_from(edges)
pos = nx.spring_layout(G, seed=42)

colors = ["#e74c3c" if sol(x[i]) == 1 else "#d5dbdb" for i in range(N)]
nx.draw(G, pos, with_labels=True, node_color=colors, node_size=400,
        font_size=9, edge_color="#888888", width=1.2)
plt.title("Maximum Independent Set")
plt.savefig("mis.png", dpi=150, bbox_inches="tight")
plt.show()

networkx.Graph オブジェクト G を作成し,add_nodes_from() と add_edges_from() でノードと辺を追加します.レイアウト位置 pos は spring-layout アルゴリズム（再現性のために固定シードを指定）で計算します.

ソルバの解に基づき,色リスト colors を構築します.選択されたノード（sol(x[i]) == 1）は赤色（#e74c3c）で,選択されていないノードは薄灰色（#d5dbdb）で描画されます.nx.draw() がノードラベル付きでグラフを描画し,plt.savefig() で結果の画像を mis.png に書き出します.出力フォーマットはファイル拡張子によって決まるため,"mis.png" の代わりに "mis.svg" や "mis.pdf" を渡せば対応するフォーマットで出力できます.

描画される画像は以下と同等です（以下の画像はC++版の qbpp::graph::GraphDrawer で生成されたものです）.なお,networkx.spring_layout は力学的配置アルゴリズムを使用するのに対し,C++ 版は Graphviz の neato を使うため,ノードの正確な配置は異なる場合があります:

MIS問題の解

C++ グラフライブラリとの対応

下表は,C++ のグラフ描画 API と Python エコシステムとの対応関係をまとめたものです:

C++（`qbpp/graph.hpp`）	Python での対応
`qbpp::graph::Node(i)`	`networkx.Graph` の `G.add_node(i)`
`Node::color(int)` / `color(str)`	`nx.draw()` の `node_color=[...]` 引数
`Node::position(x, y)`	`nx.draw()` に渡す `pos` 辞書のエントリ
`Node::penwidth(f)`	`nx.draw()` の `linewidths=...` 引数
`qbpp::graph::Edge(u, v)`	`networkx.Graph` の `G.add_edge(u, v)`
`Edge::directed()`	`Graph` の代わりに `networkx.DiGraph` を使用
`Edge::color(...)`	`nx.draw()` の `edge_color=[...]` 引数
`Edge::penwidth(f)`	`nx.draw()` の `width=...` 引数
`GraphDrawer::add_node/edge`	`G.add_node` / `G.add_edge`
`GraphDrawer::write("f.svg")`	`plt.savefig("f.svg")`（`.png` / `.pdf` / `.jpg` も可）

注釈: PyQBPP では,C++ のグラフ描画ヘルパーを意図的に再実装していません. networkx + matplotlib は豊富で十分メンテナンスされた Python のエコシステムであり,QUBO 定式化のソルバ出力を可視化するという目的では C++ 版と同等の結果が得られます.