QUBO++ 簡易グラフ描画ライブラリと最大独立集合 (MIS) 問題の解決

QUBO++ 簡易グラフ描画ライブラリ

QUBO++ は、グラフ理論的問題から得られた結果を可視化するための簡易グラフ描画ライブラリをバンドルしています。これは Graphviz のラッパーであり、Ubuntu では以下のようにインストールできます:

$ sudo apt install graphviz

このライブラリを使用するには、 qbpp_graph.hpp:

#include "qbpp_graph.hpp"

ライブラリはDOT入力を生成し、 neato を呼び出してグラフを描画します。

警告: このヘッダーのみのライブラリは、QUBO++ サンプルプログラムが生成する結果を可視化することを目的としています。その API と動作は予告なく変更される可能性があり、ミッションクリティカルなアプリケーションでは使用しないでください。

最大独立集合 (MIS) 問題

無向グラフ $G=(V,E)$ の独立集合とは、頂点集合 $S\subseteq V$ の部分集合で、$S$ 内の任意の 2 つの頂点が辺 $E$ で接続されていないものを指します。最大独立集合 (MIS) 問題は、最大要素数を持つ独立集合を求める問題です。

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

\[\begin{aligned} \text{目的関数} = -\sum_{i=0}^{n-1} x_i . \end{aligned}\]

独立性を強制するため、辺 $(i,j)\in E$ について、両端点を同時に選択してはならない。これは以下の制約でペナルティを課すことができる：

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

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

\[\begin{aligned} f = \text{目的関数} + 2\times\text{制約関数}. \end{aligned}\]

ペナルティ係数 $2$ は、集合サイズ増加よりも実現可能性を優先させるのに十分である。

MIS問題に対するQUBO++プログラム

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

#include "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::exhaustive_solver::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");
}

ベクトル x の N = 16 二値変数のベクトル objective, constraint、および f は上記のQUBO形式に従って構築される。その後、完全探索ソルバーを用いて最適解を求め、 fが求められ、これは solに格納される。 objective および constraint は sol で評価された値が印刷される。

A qbpp::graph::GraphDrawer オブジェクト graphが作成される。 iのループ内で、 qbpp::graph::Node オブジェクトがラベル iでラベル付けされ、その色は x[i] の値に応じて0または1に設定される。 sol 経由で color() 各ノードは add_node().

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

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

objective = -7
constraint = 0

これは、得られた解が7つのノードを選択し、全ての制約を満たしていることを意味します。レンダリングされた画像は mis.svg:

The solution of the MIS problem.

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

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

qbpp::graph::Node: ラベル、色、ペン幅、位置などのノード情報を格納します。
qbpp::graph::Edge: 両端のノード、有向/無向の区別、色、ペン幅などのエッジ情報を保持します。
qbpp::graph::GraphDrawing: ベクトルを格納します 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 に設定する。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::GraphDrawing`

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

add_node(const Node& node): ノードをグラフに追加します。
add_edge(const Edge& edge): エッジをグラフに追加します。
write(std::string file_name): グラフを描画し、 file_nameに書き込みます。サポートされる形式には svg, png, jpg、および pdf （Graphviz経由）が含まれます。出力形式はファイル拡張子によって決定されます。

最終更新日: 2026.01.13