Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #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);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement