決定グラフ（DD）の処理系に関する情報

Zero-suppressed binary decision diagram (ZDD) を始めとする決定グラフ（DD）の処理系に関する情報を提供するページです。

目的別ナビゲーション

• DD のアルゴリズムや実装の中身を知らずに、集合族の圧縮や、部分グラフ列挙を行いたい。

  • graphillion を用いるのがお勧めです。以下の「graphillion 情報」の節を参考にしてください。

• DD を用いたアルゴリズムの実装を行いたい。

  • SAPPOROBDD & TdZdd によって可能です。以下の「SAPPOROBDD & TdZdd 情報」の節を参考にしてください。

• DD を用いたアルゴリズムについて知りたい。

  • 資料 部分グラフ集合を扱うDDアルゴリズム や、書籍「超高速グラフ列挙アルゴリズム－〈フカシギの数え方〉が拓く，組合せ問題への新アプローチ－」をご覧ください。 英語論文 (pdf) もあります。

graphillion 情報

graphillion は集合族や部分グラフ集合を圧縮して活用するための Python ライブラリです。

公式サイトに詳しいドキュメントがあります（英語版、日本語版）。

graphillion のチュートリアル を読むのもお勧めです。

SAPPOROBDD & TdZdd 情報

入門ドキュメント

• DDライブラリ入門 : SAPPOROBDD、SAPPOROBDD helper の入門ドキュメント
• TdZdd の解説論文 : TdZdd の入門ドキュメント

DD を用いたアルゴリズムの実装を始めるには

• dd_package : このパッケージでは、SAPPOROBDD や TdZdd、いくつか便利なライブラリをまとめてインストールできます。

公式マニュアル

• SAPPOROBDD マニュアル パッケージの SAPPOROBDD/man/BDD+.pdf に入っています。
• SAPPOROBDD helper マニュアル
• TdZdd ユーザガイド（英語）

サンプルコード

フロンティア法の実装のサンプルコードはいくつかあります。

• frontier-basic: 学習用サンプルコードです。効率は悪いため、本番で使用しないようにしてください。
• frontier_basic_tdzdd: TdZdd を用いたフロンティア法の実装例です。こちらを用いてください。
• frontier: TdZdd を用いないフロンティア法の実装例です。こちらよりは frontier_basic_tdzdd をおすすめします。

FAQ

• DD ライブラリに関する FAQ

その他ドキュメント

• DDの再帰演算のカタログ : 各種再帰演算の SAPPOROBDD でのコード例が掲載されています。
• BDD バイナリ形式
• graphillion 形式
• TdZdd の Graph クラスについて
• Graph class in the TdZdd library

その他リンク集

• TdZdd を用いたネットワーク信頼性計算
• dd_converter (TdZdd と graphillion 形式の相互変換)
• SapporoTdZddApps: TdZdd と SAPPOROBDD の橋渡しライブラリ
• binary decision diagram (BDD) software libraries（DDライブラリの網羅的リスト）