/SapporoTdZddApps

Bridging SAPPOROBDD and TdZdd with some applications.

Primary LanguageC++MIT LicenseMIT

SapporoTdZddApps

TdZdd と SAPPOROBDD の橋渡しライブラリ

実装予定の機能は下記の通り

  • 各種制約下での DD 構築
    • グラフ制約（FrontierBasedSearchWithVetexIndices の焼き直し）
      • s-t パス
      • サイクル
      • 連結成分系（木、森を含む）
        • 単一成分、木
        • 複数成分、森
      • 次数制約
      • シュタイナー制約
    • その他の制約
      • 線形不等式（整数のみ）
    • 関連する機能
      • DdStructure <--> ZBDD の変換
      • DDの変数順序に合わせたグラフデータの取得
      • 辺の順序付けを行う Beam Search（優先度：低）
  • SAPPOROBDD の拡張としての新規演算など
    • Power set の作成
    • 特定の部分集合を表すZDDの作成
    • 特定のアイテム集合に着目したZDDへの変換（グラフ制約のZDDから頂点変数だけ抜き出すときなどに便利）
    • 特定のアイテムを含む/含まない（OnSet などの別名）
    • 特定のアイテム間の xor を適用
    • DisjointJoin（優先度：低）
    • JointJoin（優先度：低）
  • 最適化
    • 線形最適化のDP
  • その他の機能
    • DdStructure の解凍
    • ZBDD の解凍