dd_package

本パッケージは圧縮データ構造 BDD/ZDD（Binary Decision Diagram、二分決定グラフ）のライブラリである

• SAPPOROBDD（湊 真一先生）
• SAPPOROBDD helper（川原）
• TdZdd（岩下 洋哲氏）

を一度にダウンロードするためのスクリプトです。 SAPPOROBDD は BDD/ZDD の演算ライブラリ、 SAPPOROBDD helper は SAPPOROBDD を使いやすくするための補助ライブラリ、 TdZdd はトップダウン BDD/ZDD 構築ライブラリです。

対応環境

以下の環境で動作を確認しています。

• Windows 10 + Cygwin + gcc 11.4.0
• Windows 10 + WSL 2 + Ubuntu 22.04 + gcc 11.4.0
• Mac 12.5.1 + clang 13.1.6
• Mac 14.0 + clang 15.0.0
• Linux Ubuntu 22.04 + gcc 11.4.0
• Linux Ubuntu 20.04 + clang 10.0.0

パッケージの導入

コマンドラインから行います。 curl, git, make コマンドが実行できる必要があります。 以下のコマンドを実行します。または downloader.sh を手動でダウンロードして実行してください。

# your_program は好きな名前
mkdir your_program
cd your_program
curl -OL https://github.com/junkawahara/dd_package/raw/main/downloader.sh
sh downloader.sh

downloader.sh スクリプトを実行すると、your_program ディレクトリの中に、 SAPPOROBDD、sbdd_helper、TdZdd がダウンロードされます。 また、サンプル用の Makefile と main.cpp もダウンロードされます。 SAPPOROBDD が自動でビルドされます。

make でコンパイルして実行できる状態になっています。

make
./main

./main を実行して、"program works correctly" が出力されると、 正しくコンパイルできています。

本パッケージでは、main.cpp を編集して、 サンプルプログラムを上書き（消去）して自分のプログラムを書くという 使い方を想定しています。Makefile に詳しい人は、Makefile を 編集して、ソースファイルを自分の好きなファイル名にできます。

パッケージのアップデート

パッケージをアップデートするには以下のコマンドを実行します （最新版の downloader.sh が必要です）。

sh downloader.sh --update

SAPPOROBDD のビルド

SAPPOROBDD は downloader.sh によって自動でビルドされますが、 ビルドに失敗する場合は以下の通りにビルドできます。

cd SAPPOROBDD/src/
sh INSTALL
cd ../../
ls SAPPOROBDD/lib
# BDD64.a が表示されれば成功

ビルドに成功すると、SAPPOROBDD/lib ディレクトリの中に、BDD64.a が作成されます。

技術的な詳細と注意

本パッケージでは、SAPPOROBDD の X11 機能を無効にするため、SAPPOROBDD/src/BDDc/makefile と SAPPOROBDD/src/BDD+/Makefile 、 SAPPOROBDD/src/INSTALL を書き換えています。 書き換え前のファイルは .bak 拡張子を付けてバックアップをとっています。

マニュアル、リンク

• ZDD の実装に関する情報
• SAPPOROBDD マニュアル ダウンロードしたパッケージの SAPPOROBDD/man/BDD+.pdf に入っています。
• SAPPOROBDD helper マニュアル
• TdZdd の解説論文 / ユーザガイド（英語）

ライセンス

本パッケージは MIT ライセンスです。downloader.sh を用いてダウンロードされるソフトウェアはそれぞれのライセンスに従います。