example_tdzdd.cpp

example_tdzdd.cpp

#include <fstream>
#include <iostream>
#include <tdzdd/DdSpec.hpp>
#include <tdzdd/DdStructure.hpp>

using namespace std;
    
const bool DEBUG_ENUM = false;

class Combination : public tdzdd::DdSpec<Combination, int, 2> {
    const int n;
    const int k;
public:
    Combination(int __n, int __k) : n(__n), k(__k) {}
    
    int getRoot(int& cnt) {
        cnt = 0;
        return n;
    }
    
    int getChild(int& cnt, int level, int take) const {
        cnt += take;
        if (cnt > k)
            return 0;
        if (cnt + level - 1 < k)
            return 0;
        --level;
        return (level == 0) ? -1 : level;
    }
};

class MaxNumItems: public tdzdd::DdEval<MaxNumItems, int> {
public:
    void evalTerminal(int& n, bool one) const {
        n = one ? 0 : INT_MIN;
    }
    void evalNode(int& n, int, tdzdd::DdValues<int,2> const& values) const {
        n = std::max(values.get(0), values.get(1) + 1);
    }
};
    
int main() {
    const int n = 10;
    const int k = 4;
    // ofstream output("comb.dot");
    // ofstream output_reduced("comb_reduced.dot");
    Combination comb(n, k);
    // comb.dumpDot(output);
    tdzdd::DdStructure<2> dd(comb);
    dd.zddReduce();
    // dd.dumpDot(output_reduced);
    cout << n << "C" << k << "=" << dd.zddCardinality() << endl;

    // test iterator
    if (DEBUG_ENUM) {
        int count = 1;
        for (auto itemset : dd) {
            cout << (count++) << " [";
            for (auto v : itemset) { cout << v << " "; }
            cout << "]" << endl;
        }
    }

    // traverse on ZDD
    // root's level
    auto root_node = dd.root();
    auto top_level = dd.topLevel();
    cout << "root node id = " << root_node << ", top leve = " << top_level << endl;
    
    // topを1とする評価
    int max = dd.evaluate(MaxNumItems());
    cout << max << endl;

    // get child
    auto c0 = dd.child(root_node, 0);
    auto c1 = dd.child(root_node, 1);
    cout << c0 << " " << c1 << endl;

    // get 1-th sub zdd できない
    // ofstream oz1("comb_c1.dot");
    // c1.dumpDot(oz1);
}