Graphillion：巨大なグラフ集合を扱うソフトウェアライブラリ

摘要

これまでに多くのグラフライブラリが開発されてきたが，それらはひとつのグラフを処理するために設計されている．あるグラフからは指数的な数のサブグラフを取り出せるが，それらを効率的に扱うことはできない．本稿では，Graphillionという巨大なグラフ集合を扱うためのソフトウェアライブラリを提案する．Graphillionは，グラフ集合を「辺の集合の集合」として簡易化してみなすことにより，強力な「集合族演算」を適用可能にし，巨大なグラフ集合を効率的に扱う．また，グラフ列挙アルゴリズムを用いて，単なる集合しか扱えない演算体系にグラフの構造を理解させる．Graphillionは生産性に優れるPython言語のモジュールとして実装されるため，Graphillionを用いたアプリケーションを開発は容易である．パズルソルバと電力網最適化というグラフ集合演算を伴うケーススタディを通し，わずかなコード量で天文学的な数のグラフ（この例では複雑な制約を満たすサイクルや森）－を扱い，複雑な問題を解決できることを示す．Graphillionはhttp：//graphillion.org／で公開されている．