# グラフ描画ライブラリと最大独立集合 (MIS) 問題の求解
:::{container} prog-cpp
## Hi-QUBO 簡易グラフ描画ライブラリ
Hi-QUBO には,グラフ理論的問題から得られた結果を可視化するための簡易グラフ描画ライブラリが付属しています.
これは Graphviz のラッパーであり,Ubuntu では以下のようにインストールできます：
```{include} /../programFiles/markDown/example/graph/graph-visualization-library.md
:start-after:
:end-before:
```
このライブラリを使用するには,`qbpp/graph.hpp` をインクルードします：
```{literalinclude} /../programFiles/cppPrograms/example/graph/graph-visualization-library-program1.cpp
:language: cpp
:caption: graph-visualization-library-program1.cpp
```
このライブラリは 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 グラフ描画ライブラリを用いて可視化されます：
```{literalinclude} /../programFiles/cppPrograms/example/graph/graph-visualization-library-program2.cpp
:language: cpp
:caption: graph-visualization-library-program2.cpp
```
`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` に書き出します.
このプログラムの出力は以下の通りです：
```{include} /../programFiles/markDown/example/graph/graph-visualization-library.md
:start-after:
:end-before:
```
これは,得られた解が 7 個のノードを選択し,すべての制約を満たしていることを意味します.描画された画像は `mis.svg` として保存されます：
## 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 経由）です.
出力フォーマットはファイルの拡張子によって決定されます.
:::
:::{container} prog-python
## PyQBPP でのグラフ可視化
Hi-QUBO のC++版には,Graphviz をラップした簡易グラフ描画ライブラリ（`qbpp::graph::GraphDrawer`）が付属しており,グラフを `svg` / `png` / `jpg` / `pdf` に直接出力できます.詳細は [C++ 版のグラフライブラリのページ](graph-visualization-library.md) を参照してください.
PyQBPP には専用のグラフクラスは**ありません**.その代わりに,Python エコシステムで広く使われている以下のライブラリを使ってグラフを可視化できます:
- [`networkx`](https://networkx.org/) — グラフデータ構造とレイアウトアルゴリズム
- [`matplotlib`](https://matplotlib.org/) — 作図と画像出力
インストールは以下のコマンドで行えます:
```{include} /../programFiles/markDown/example/graph/graph-visualization-library.md
:start-after:
:end-before:
```
このページの以降では,最大独立集合（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` に格納されています:
```{literalinclude} /../programFiles/pythonPrograms/example/graph/graph-visualization-library-program1.py
:language: python
:caption: graph-visualization-library-program1.py
```
`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]` の値を評価し,選択されたノードの一覧を出力します.
このプログラムは以下の出力を生成します:
```{include} /../programFiles/markDown/example/graph/graph-visualization-library.md
:start-after:
:end-before:
```
これは,得られた解が7個のノードを選択し,すべての制約を満たしていることを意味します.
## matplotlib と networkx による可視化
以下のコードは,`matplotlib` と `networkx` を使用して MIS の解を可視化します.上記のプログラムの末尾に追加し,`edges`,`N`,`x`,`sol` が有効な状態で実行してください:
```{literalinclude} /../programFiles/pythonPrograms/example/graph/graph-visualization-library-program2.py
:language: python
:caption: graph-visualization-library-program2.py
```
`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` を使うため,ノードの正確な配置は異なる場合があります:
## 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++ 版と同等の結果が得られます.
:::