Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.