Zero-suppressed binary decision diagram (ZDD) を始めとする決定グラフ（DD）の処理系に関する情報を提供するページです。
-
DD のアルゴリズムや実装の中身を知らずに、集合族の圧縮や、部分グラフ列挙を行いたい。
- graphillion を用いるのがお勧めです。以下の「graphillion 情報」の節を参考にしてください。
-
DD を用いたアルゴリズムの実装を行いたい。
- SAPPOROBDD & TdZdd によって可能です。以下の「SAPPOROBDD & TdZdd 情報」の節を参考にしてください。
-
DD を用いたアルゴリズムについて知りたい。
- 資料 部分グラフ集合を扱うDDアルゴリズム や、書籍「超高速グラフ列挙アルゴリズム－〈フカシギの数え方〉が拓く，組合せ問題への新アプローチ－」をご覧ください。 英語論文 (pdf) もあります。
graphillion は集合族や部分グラフ集合を圧縮して活用するための Python ライブラリです。
公式サイトに詳しいドキュメントがあります（英語版、日本語版）。
graphillion のチュートリアル を読むのもお勧めです。
- DDライブラリ入門 : SAPPOROBDD、SAPPOROBDD helper の入門ドキュメント
- TdZdd の解説論文 : TdZdd の入門ドキュメント
- dd_package : このパッケージでは、SAPPOROBDD や TdZdd、いくつか便利なライブラリをまとめてインストールできます。
- SAPPOROBDD マニュアル パッケージの SAPPOROBDD/man/BDD+.pdf に入っています。
- SAPPOROBDD helper マニュアル
- TdZdd ユーザガイド（英語）
フロンティア法の実装のサンプルコードはいくつかあります。
- frontier-basic: 学習用サンプルコードです。効率は悪いため、本番で使用しないようにしてください。
- frontier_basic_tdzdd: TdZdd を用いたフロンティア法の実装例です。こちらを用いてください。
- frontier: TdZdd を用いないフロンティア法の実装例です。こちらよりは frontier_basic_tdzdd をおすすめします。
- DDの再帰演算のカタログ : 各種再帰演算の SAPPOROBDD でのコード例が掲載されています。
- BDD バイナリ形式
- graphillion 形式
- TdZdd の Graph クラスについて
- Graph class in the TdZdd library