/* Global constraint clique (decomposition) in Gecode. From Global Constraint Catalog: http://www.emn.fr/x-info/sdemasse/gccat/Cclique.html """ clique​(SIZE_CLIQUE,​NODES) """ Consider a digraph G described by the NODES collection: to the ith item of the NODES collection corresponds the ith vertex of G; To each value j of the ith succ variable corresponds an arc from the ith vertex to the jth vertex. Select a subset S of the vertices of G that forms a clique of size SIZE_CLIQUE (i.e., there is an arc between each pair of distinct vertices of S). Example [The graph is 1 -> 2,4 2 -> 1,3,5 3 -> 2,5 4 -> 1,5 5 -> 2,3,4 ] (3, < index-1 succ-{}, index-2 succ-{3,5} index-3 succ-{2,‹5} index-4 succ-{}, index-5 succ-{2,3} > ) The clique constraint holds since the NODES collection depicts a clique involving 3 vertices (namely vertices 2, 3 and 5) and since its first argument SIZE_CLIQUE is set to the number of vertices of this clique. """ Compare with the MiniZinc model: http://www.hakank.org/minizinc/clique.mzn This Gecode model was created by Hakan Kjellerstrand (hakank@bonetmail.com) Also, see my Gecode page: http://www.hakank.org/gecode/ . */ #include #include #include #include using namespace Gecode; class Clique : public MaximizeScript { protected: const static int n = 100; // number of nodes in the graph SetVar x; // set of clique IntVar c; // cardinality of clique (to maximize) int c_args; // cardinality of clique from command line public: // search engines enum { SEARCH_DFS, SEARCH_BAB, SEARCH_RESTART }; Clique(const SizeOptions& opt) : x(*this, IntSet::empty, IntSet(0, n-1), 0, n), c(*this, 0, n-1), c_args(opt.size()) { /** * The graph from the Global Constraint catalogue cited above. * Note: In this model we start at 0 * * 0 -> 1,3 * 1 -> 0,2,4 * 2 -> 1,4 * 3 -> 0,4 * 4 -> 1,2,3 * * The found clique (N=3) is {1,2,4}. * */ // num_nodes = 5; /* int g[] = { // 0 1 2 3 4 5 1,1,0,1,0, // 0 1,1,1,0,1, // 1 0,1,1,0,1, // 2 1,0,0,1,1, // 3 0,1,1,1,1, // 4 }; */ /* * A larger graph * The cliques are * 0,1,2 * 3,4,5 * 5,6,7,8,9 * (and their "sub cliques") * num_nodes = 10; */ /* int g[] = { // 0 1 2 3 4 5 6 7 8 9 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, // 0 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, // 1 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, // 2 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, // 3 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, // 4 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, // 5 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, // 6 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, // 7 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, // 8 0, 1, 0, 0, 0, 1, 1, 1, 1, 1 // 9 }; */ /** * This is a random graph of size 100. * * There are 4 cliques of size 6. */ int g[] = { 0,0,1,0,1,0,1,0,0,1,0,1,0,1,1,1,1,0,1,0,0,1,0,1,1,0,1,0,0,0,1,0,1,1,0,1,1,1,0,0,0,1,0,1,1,0,1,0,1,1,0,1,1,0,0,1,0,1,1,1,1,1,1,0,1,0,0,1,1,0,1,1,1,1,1,0,0,1,0,0,0,1,1,1,1,1,1,0,0,1,1,1,0,0,0,1,1,1,1,1, 1,0,0,1,1,0,0,1,0,0,0,0,0,0,1,1,0,1,0,0,0,0,1,1,1,0,1,1,1,0,0,0,1,1,0,1,0,0,1,1,0,0,0,0,0,1,0,0,1,1,0,1,0,0,0,0,0,1,0,0,0,0,1,1,1,1,1,0,1,0,0,0,0,0,1,1,0,0,1,1,0,1,1,0,1,0,1,0,0,1,0,0,0,0,0,1,0,1,0,1, 1,0,0,0,0,0,1,0,0,1,1,0,0,1,1,0,0,0,1,0,1,0,0,1,1,0,1,0,1,1,1,1,1,1,1,0,1,1,0,0,0,1,1,0,0,0,1,0,1,1,0,0,0,1,1,0,0,0,0,1,1,1,0,0,1,1,0,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,1,0,1,1,1,0,0,0,0,0,1,1,0,0,0,1,1, 0,0,0,1,1,1,0,1,1,1,0,0,1,1,0,1,1,0,1,0,1,1,0,0,0,0,0,1,1,0,1,1,1,1,1,1,1,0,0,1,0,1,0,0,1,0,0,0,0,1,0,0,1,0,1,0,1,0,0,1,1,1,1,1,1,1,0,1,1,0,0,1,0,1,0,0,1,1,1,1,1,0,1,1,1,0,0,0,1,1,1,0,1,1,1,0,1,0,1,1, 1,0,0,0,0,1,0,0,1,1,0,0,0,0,1,1,0,0,1,1,0,0,0,1,1,1,0,0,1,1,1,0,0,1,1,0,1,1,0,0,0,1,1,0,1,1,1,0,1,1,0,1,0,1,0,0,0,1,0,1,0,1,1,0,1,0,0,1,0,1,0,0,0,0,0,1,0,1,1,1,1,1,0,0,1,0,0,0,0,1,0,0,1,1,1,1,1,1,1,0, 1,0,1,1,0,0,1,1,1,1,1,0,0,0,1,1,0,0,1,0,1,1,1,0,0,0,0,0,1,1,0,0,0,0,1,1,1,0,0,1,0,1,0,1,0,0,0,0,1,1,0,0,1,1,1,0,1,1,0,1,0,1,0,0,1,0,1,1,1,1,0,0,1,1,0,1,1,0,1,0,0,1,1,0,0,1,1,0,1,0,1,1,1,0,1,1,0,0,1,1, 1,0,0,1,1,0,1,1,0,1,1,0,0,0,0,0,0,1,1,0,1,0,0,0,0,1,1,0,1,0,0,0,1,0,1,1,0,0,0,0,0,0,1,0,1,0,1,0,1,0,1,0,0,1,1,1,0,1,1,0,1,1,1,0,0,1,1,1,0,0,1,1,1,0,1,1,0,1,1,0,0,0,0,1,1,1,0,1,1,0,1,0,0,1,0,0,1,1,0,0, 1,0,1,0,0,1,0,1,1,1,0,1,1,0,1,0,0,1,1,1,0,1,0,1,1,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,1,1,1,0,1,0,0,1,1,0,0,1,1,1,0,1,1,1,0,0,0,1,1,1,0,1,0,1,0,0,0,0,0,1,1,1,0,1,0,1,0,1,1,1,0,0,1,0,1,1,0,1,0,1, 1,0,0,1,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,0,0,0,1,0,1,1,0,0,0,0,0,1,1,1,0,1,0,0,0,0,0,1,1,0,1,0,0,1,0,1,0,0,1,0,1,0,0,1,1,0,0,0,1,0,1,1,1,0,0,1,0,1,0,1,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,0,1,0,0,1,1, 0,1,0,1,0,1,1,1,1,0,0,1,0,1,0,1,1,0,0,1,1,1,0,1,0,0,1,0,0,1,1,1,1,0,0,0,1,1,1,0,1,1,1,1,1,1,0,1,0,1,1,1,0,1,1,0,1,1,1,1,1,1,1,0,1,0,1,0,0,1,1,0,1,0,1,0,0,1,0,0,0,1,0,1,0,0,0,1,0,1,1,1,1,0,1,1,1,1,0,0, 1,0,0,0,0,1,0,1,0,1,1,1,0,1,1,1,1,0,1,0,0,0,0,0,0,1,1,0,0,0,1,1,0,1,1,0,0,0,1,0,0,0,0,0,0,1,1,1,1,0,0,1,0,0,1,1,0,1,0,0,1,1,0,1,0,0,0,0,0,1,0,0,0,1,0,1,1,0,1,1,1,1,0,0,0,0,1,1,0,0,0,0,0,1,0,1,1,0,0,0, 0,0,1,1,1,0,1,0,0,0,1,0,0,1,0,1,0,0,1,1,0,0,0,1,0,0,0,1,1,0,1,0,1,0,0,0,1,1,1,1,0,1,0,1,1,0,0,1,0,0,1,1,1,1,0,0,1,1,0,1,0,1,1,0,1,1,0,1,1,1,0,0,0,1,1,0,1,1,0,1,0,1,0,1,1,0,0,1,1,1,1,1,0,1,1,0,1,1,0,0, 1,1,0,0,0,0,1,0,1,0,1,1,0,1,0,1,1,1,1,1,0,0,0,1,0,1,1,1,0,1,0,0,0,0,1,0,0,1,0,1,0,0,1,0,1,1,1,0,0,0,0,1,0,1,0,0,0,0,1,1,0,1,0,0,0,0,0,0,1,1,0,0,1,1,1,1,0,0,1,0,1,0,0,1,0,0,0,1,1,1,1,1,0,1,1,1,1,0,0,1, 1,1,1,0,0,0,0,0,0,1,0,1,1,1,0,1,1,0,0,0,0,1,0,0,0,0,1,1,1,1,0,0,1,1,0,0,1,0,1,0,1,1,1,0,0,0,1,0,1,1,1,1,1,0,0,1,1,1,0,1,0,1,1,1,1,1,1,1,0,1,0,0,0,0,0,0,0,1,0,1,0,1,0,1,1,1,0,0,1,0,1,1,1,0,0,0,1,0,0,0, 0,0,1,1,1,1,0,1,0,1,0,0,0,0,0,1,0,0,1,1,1,0,0,0,1,0,1,1,0,0,0,0,1,0,0,0,0,0,0,1,1,1,1,1,0,1,0,0,1,0,1,1,1,1,1,0,0,0,1,1,0,1,1,0,0,1,0,0,0,1,0,1,1,1,0,0,0,0,0,1,1,0,1,0,0,1,1,0,0,0,1,1,1,0,0,1,0,1,1,0, 1,0,0,1,1,0,1,1,1,1,0,1,1,1,1,0,0,0,0,1,1,1,0,0,1,0,1,0,1,1,1,0,1,1,0,1,1,1,0,1,1,0,1,1,0,0,0,1,0,0,0,0,0,1,1,0,0,0,0,1,0,1,0,1,0,0,1,1,0,1,1,1,1,0,0,1,0,1,0,1,0,1,1,0,1,1,0,1,0,1,0,1,1,1,0,0,0,1,0,0, 1,0,0,1,1,1,0,0,1,1,0,1,1,0,0,1,0,0,1,1,1,1,0,0,1,1,0,0,1,0,0,1,1,0,0,0,0,0,1,0,0,0,0,1,0,1,1,1,1,0,0,1,0,0,1,1,1,1,0,0,0,0,0,1,1,1,0,1,0,1,0,0,1,1,0,0,0,1,1,0,0,1,1,1,1,1,1,1,0,1,1,0,0,1,1,1,0,1,1,0, 0,0,1,0,1,1,1,1,1,0,1,1,1,0,0,1,1,0,0,0,1,0,1,1,0,1,0,0,0,0,1,1,0,1,1,0,1,0,0,1,1,1,0,0,1,1,1,0,1,1,1,0,1,0,1,1,1,0,1,1,0,1,1,1,1,1,0,0,0,0,1,1,0,0,1,0,0,0,1,0,1,0,1,1,0,0,0,1,1,1,0,1,0,0,1,0,1,1,1,0, 1,1,1,1,0,0,0,1,1,0,0,1,1,0,0,0,0,1,1,1,1,1,1,1,1,1,0,1,1,1,0,0,0,0,1,1,1,1,0,1,0,0,1,0,0,0,0,0,1,1,0,1,0,0,0,1,0,0,0,1,1,0,1,0,1,1,0,1,0,0,1,0,0,0,0,1,1,1,0,0,0,1,1,0,0,1,0,0,0,1,1,1,1,1,0,0,0,1,0,1, 1,0,0,1,1,0,0,1,0,0,0,0,0,0,0,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,1,0,0,1,0,1,1,1,1,0,1,0,1,0,0,0,0,1,1,0,1,0,1,1,1,0,1,0,0,1,1,0,0,0,1,0,1,1,1,0,0,1,1,1,1,1,1,0,1,0,1,0,1,0,1,1,0,1,0,1,1,1, 1,1,0,1,0,0,1,1,1,0,0,1,1,0,1,0,0,0,1,1,0,0,0,0,0,1,0,0,0,1,1,0,0,0,1,1,1,0,1,1,1,1,1,1,0,1,1,0,1,0,1,0,0,1,0,1,1,0,1,1,1,1,1,0,0,1,1,1,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,1,0,1,0,1,1,1,1,1,1,0,1,1, 1,1,1,1,0,0,1,0,1,1,0,0,0,0,1,0,1,0,0,0,0,0,1,1,0,1,0,1,0,0,0,1,1,1,1,1,0,0,1,1,1,0,0,0,1,1,1,1,1,0,0,0,1,0,0,1,0,1,1,0,1,0,1,0,1,0,0,1,0,0,1,1,0,0,1,0,0,0,0,0,0,0,1,1,1,1,0,0,1,1,1,0,0,1,0,0,0,1,0,0, 1,0,0,0,0,1,0,0,0,1,0,0,1,1,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,1,1,0,0,1,1,0,1,1,1,0,1,0,0,0,0,1,1,1,1,0,1,1,0,1,1,1,0,1,1,1,1,0,0,1,0,0,0,0,0,1,1,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,1,1,0,0,1,1,1,1,0,0,0,1, 1,0,1,1,1,0,1,0,0,0,1,1,0,0,1,1,1,1,1,0,0,0,1,0,1,0,0,1,1,0,1,0,1,1,0,0,1,1,1,0,1,0,1,0,1,0,0,1,1,0,0,1,1,0,0,0,0,1,1,0,0,1,1,1,0,0,0,0,1,1,0,1,1,1,0,0,1,1,1,0,0,0,0,1,0,0,1,1,1,0,1,1,0,1,0,0,1,1,1,0, 1,0,1,0,0,1,0,0,1,0,1,1,0,0,1,1,0,0,1,0,1,1,0,0,1,0,1,0,1,1,1,1,1,0,1,1,0,0,0,1,1,0,0,0,1,0,1,0,1,1,1,1,0,1,0,1,1,0,1,0,0,1,0,0,0,0,0,0,1,0,1,1,1,0,1,0,0,0,0,0,1,1,1,1,0,1,0,0,0,1,1,0,0,1,0,0,1,0,1,1, 0,0,1,1,1,0,1,1,1,0,1,1,0,0,0,1,0,1,1,1,0,0,0,0,1,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,1,0,1,0,1,0,1,1,1,0,1,1,0,0,1,1,0,0,0,1,1,1,0,0,1,1,0,1,1,0,1,1,0,1,1,0,1,0,0,0,0,1,0,1,1,1,0,0,1,0,1,1,1,1,0,0,1,1,0, 1,0,0,0,0,1,1,0,0,0,0,1,1,0,0,0,1,1,1,1,1,0,1,0,1,1,0,0,0,0,1,0,1,1,0,1,0,1,0,0,0,1,0,0,1,1,1,1,0,0,1,0,1,1,1,1,1,0,0,0,0,0,0,1,0,0,1,1,0,0,0,1,0,1,1,0,0,0,1,1,0,1,0,1,1,0,1,1,1,1,1,1,1,0,1,1,0,0,0,1, 1,1,0,1,0,1,1,0,1,0,1,0,1,0,0,1,0,1,1,0,0,1,0,0,1,1,1,0,1,1,0,1,1,1,1,0,0,1,0,1,0,0,1,0,1,1,1,0,0,0,1,1,0,1,1,0,1,0,1,0,0,0,0,0,1,1,0,1,0,0,1,1,1,0,1,0,0,0,0,1,1,1,1,1,0,0,1,0,0,0,0,0,1,0,0,0,1,0,0,1, 1,1,1,1,0,1,0,0,0,1,0,1,0,1,1,0,0,1,1,0,0,0,1,1,1,0,1,1,0,1,1,1,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,1,0,0,0,0,0,0,0,1,0,1,1,1,1,1,1,0,1,0,1,1,0,1,1,0,1,0,1,0,0,1,1,1,1,0,1,1,0,0,0,0,0,0,1,0,1, 1,0,0,1,1,0,0,1,1,1,0,0,0,1,1,1,0,0,1,1,0,0,0,0,0,1,0,1,1,0,0,0,0,1,1,1,1,0,0,0,0,0,0,0,1,1,1,1,0,1,0,1,0,1,0,1,0,1,0,0,1,0,0,1,0,1,1,0,1,1,1,0,1,1,1,1,0,0,1,1,1,1,1,0,0,0,1,1,0,0,0,0,0,0,0,0,0,1,0,1, 0,0,1,1,1,0,0,1,1,0,1,0,0,0,1,0,0,1,0,1,0,1,1,0,1,0,0,1,1,1,0,0,0,1,0,0,1,1,1,0,0,1,1,0,0,1,1,1,1,0,0,0,0,0,0,1,0,0,0,1,0,1,1,1,0,1,0,1,1,1,0,1,0,0,0,1,1,0,1,0,1,1,1,0,0,1,1,1,0,1,1,0,1,1,1,1,1,1,0,0, 0,0,1,1,0,0,0,1,1,1,0,1,0,0,1,1,1,0,0,0,0,1,1,0,1,1,1,0,0,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,0,1,0,0,1,0,0,1,0,1,1,0,1,0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,1,0,1,0,0,1,0,0,0,0,1,1,1,1,1,1,1,1,0,0,0,0,1,0,1,0,1,0, 0,1,0,1,0,0,0,1,0,1,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,1,0,1,0,0,0,1,0,0,1,0,0,0,1,1,0,0,1,0,1,1,0,0,0,0,0,0,1,0,1,1,1,0,1,1,0,1,0,1,1,0,0,1,0,0,1,1,0,0,0,0,0,1,0,0,1,0,0,0,1,1,1,0,0,0,1,1,0,1,0,0,1,1,1,1, 0,1,1,0,0,1,0,1,0,0,0,0,0,1,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,1,0,1,0,0,1,1,1,1,1,0,1,1,0,0,1,0,1,1,1,1,0,0,0,1,0,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,0,1,0,0,0,1,0,1,0,0,1,0,0,0,1,0,1,1,0,0,1,1,0,1,1,0,1,1,1,1, 0,1,0,1,0,1,0,0,0,1,0,0,1,0,0,1,0,0,1,0,0,0,0,1,0,0,0,1,1,0,0,1,1,1,1,1,1,0,0,0,1,0,1,0,1,1,1,0,0,1,0,0,0,1,1,1,0,1,1,1,0,0,0,1,1,0,0,1,1,1,0,1,0,1,0,1,1,0,1,0,1,1,1,1,1,1,0,1,1,1,0,0,1,1,1,0,0,0,0,0, 1,0,0,0,1,0,0,0,1,0,0,0,0,1,1,1,0,0,0,0,0,0,0,1,0,1,1,0,1,1,1,0,1,1,0,0,0,1,1,0,0,1,0,0,0,1,1,1,0,1,1,1,1,1,1,0,0,1,0,0,0,1,1,0,0,1,1,1,1,0,1,0,1,1,1,1,0,0,0,0,1,1,0,1,0,0,0,0,1,1,1,1,0,0,1,0,1,1,0,0, 0,1,1,1,0,1,1,0,0,0,0,0,1,1,1,1,0,1,0,0,0,1,1,0,1,1,0,1,1,1,0,0,0,1,0,1,0,1,0,0,1,0,0,1,1,1,0,0,1,0,0,0,0,1,0,1,0,1,0,1,0,1,1,0,0,0,0,1,0,0,1,0,1,0,1,0,0,0,1,0,0,0,1,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,1, 0,1,1,0,0,0,0,0,1,1,1,1,1,1,1,0,1,0,0,0,0,1,1,0,0,1,1,1,0,0,0,0,1,0,1,0,1,1,1,0,0,0,0,0,1,1,1,1,1,1,1,1,0,0,1,1,1,1,0,0,1,0,0,1,0,1,0,1,1,0,0,0,0,1,1,1,1,0,0,1,1,1,1,0,1,0,0,0,0,0,1,1,0,0,1,1,0,1,1,1, 1,0,0,1,0,1,0,0,0,0,1,1,0,1,1,0,0,1,1,1,0,1,1,1,0,0,0,1,1,0,1,1,1,1,0,0,1,1,1,0,1,0,1,0,0,0,1,1,1,0,0,1,1,0,0,0,0,1,1,0,1,0,1,1,0,0,1,1,0,1,1,0,1,1,0,1,1,1,0,0,1,0,0,1,1,1,0,0,1,0,0,1,0,1,0,0,0,1,0,1, 0,0,1,0,0,0,1,1,0,1,1,0,1,1,1,0,1,1,1,1,0,0,1,0,0,0,0,1,0,0,0,0,1,0,1,1,1,1,1,0,1,1,0,0,0,0,1,0,0,1,0,0,0,0,1,1,0,1,0,1,0,0,0,1,0,1,0,0,1,0,0,1,0,0,0,1,1,0,0,0,0,0,1,1,1,0,0,1,1,1,1,0,1,0,0,1,1,0,0,0, 1,0,0,1,0,0,0,1,1,0,1,1,0,0,1,1,1,1,1,1,0,1,1,1,0,1,1,0,1,1,0,0,0,0,0,1,0,0,1,0,0,0,1,1,1,0,1,0,1,1,1,0,1,1,0,0,0,0,0,1,1,1,1,0,0,0,1,0,0,0,1,0,0,1,1,1,1,1,0,1,1,1,1,0,0,0,0,1,0,0,1,1,0,0,1,0,1,0,1,0, 1,0,0,0,0,0,1,1,0,1,1,0,1,1,0,1,0,1,1,1,0,0,1,0,1,1,0,1,1,0,0,0,0,0,0,1,0,1,0,0,0,0,1,1,1,0,0,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,0,1,1,1,1,0,1,1,1,0,1,1,1,1,0,0,0,1,1,1,1,1,0,1,0,0,1,1,1,1,0,1,1,0,1,1, 0,0,1,1,1,0,1,0,1,1,1,1,0,1,0,0,1,1,0,0,1,1,0,1,0,1,1,1,0,0,0,0,1,1,0,1,1,0,1,1,1,1,1,0,0,0,0,1,1,1,1,0,0,1,1,0,1,1,1,0,0,0,1,0,0,0,0,1,0,1,1,1,1,0,1,0,1,1,1,1,1,1,1,0,1,1,0,0,1,1,0,0,1,1,0,1,0,1,0,1, 1,1,0,1,1,1,1,1,1,1,1,0,1,0,0,0,0,0,1,1,1,1,0,1,0,1,1,1,0,0,1,0,0,1,0,0,1,0,1,0,1,0,1,1,1,1,1,0,1,0,1,0,1,1,1,1,1,1,1,0,0,0,1,0,0,1,0,0,0,1,1,0,1,1,0,0,0,1,0,1,1,1,0,0,0,0,1,0,1,1,1,1,0,0,0,1,0,0,0,1, 0,0,1,0,1,1,1,1,1,0,1,0,0,0,0,1,1,1,1,0,0,1,0,0,1,1,1,0,1,1,0,1,1,1,0,0,0,1,0,0,1,1,1,1,1,1,1,1,1,0,0,1,0,0,1,1,0,0,1,1,0,1,1,1,1,1,0,1,0,1,1,1,1,1,0,1,1,0,1,0,0,0,1,1,1,0,0,1,1,1,0,1,0,1,0,0,0,1,1,0, 0,0,1,1,0,1,0,1,1,1,0,1,0,0,1,0,0,0,0,1,1,0,0,1,1,0,1,1,0,0,1,0,0,0,1,0,0,1,1,0,0,0,0,0,1,1,0,1,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,0,0,0,1,1,0,1,0,0,1,0,1,0,0,0,1,0,1,1,0,0,1,0,0, 0,1,0,0,1,1,0,1,0,0,1,1,1,1,1,1,1,0,1,1,1,1,0,1,0,1,0,1,1,0,0,1,1,1,1,1,1,1,1,1,1,0,0,1,1,0,1,1,1,0,0,0,1,1,1,1,0,0,1,0,1,1,1,0,1,0,0,1,1,1,0,0,1,0,1,0,0,1,0,0,1,0,1,1,0,0,0,1,0,0,0,0,0,1,0,0,0,1,0,0, 1,0,0,1,0,0,1,0,0,0,0,0,1,0,0,1,1,0,0,0,1,0,1,1,0,0,1,1,1,1,1,1,0,1,0,0,0,0,0,1,1,1,1,1,0,0,1,1,0,0,1,1,0,0,1,0,0,1,0,1,0,1,1,1,0,1,1,0,0,0,0,0,0,1,1,0,0,1,0,0,1,1,1,1,1,0,1,0,1,0,1,1,1,1,0,1,0,1,1,1, 0,1,1,1,0,0,0,1,1,1,1,1,0,1,0,0,1,0,1,1,1,0,1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,0,0,0,0,0,0,0,1,1,0,0,1,0,0,1,0,0,1,0,0,1,1,1,1,1,0,1,0,0,1,0,1,1,1,0,0,1,1,1,0,0,0,1,1,1,1,1,0,1,1,1,0,1,1,1,0,0,1,1,0,1,1,1, 1,0,1,0,0,1,1,1,0,0,0,0,1,1,1,1,0,0,0,0,1,0,1,0,1,1,0,1,0,1,1,0,1,0,0,0,0,1,0,1,1,1,1,1,0,1,0,1,0,0,0,1,1,0,1,1,0,1,0,0,0,0,0,1,0,0,1,1,1,0,1,1,1,1,0,0,1,1,0,0,1,1,0,0,1,1,0,1,0,0,0,0,1,0,0,1,0,0,1,0, 1,1,1,1,1,1,1,0,0,0,1,0,0,1,1,0,1,1,0,1,1,0,1,0,0,1,1,0,1,1,1,0,1,0,0,0,0,0,1,1,0,0,1,1,1,1,1,1,1,0,1,0,1,1,0,1,1,1,0,1,1,0,1,0,0,1,1,1,1,1,1,0,0,1,0,0,1,1,1,1,1,1,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,1,1, 1,1,1,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,1,0,0,1,1,1,1,1,1,1,1,1,1,1,1,0,0,1,1,0,1,0,1,1,1,0,0,0,1,1,0,0,0,0,0,0,0,0,1,0,0,1,0,1,1,0,1,0,0,0,1,0,1,0,0,1,0,1,1,0,1,0,0,1,0,1,0,0,1,0,1,1,0,1, 1,0,1,0,0,1,0,0,0,0,1,0,1,1,1,1,0,0,0,1,1,0,0,0,0,0,0,0,1,1,0,1,0,1,0,0,0,1,1,0,1,0,1,1,1,1,0,0,0,0,0,1,1,1,1,1,1,0,1,0,1,0,0,0,0,0,0,0,1,0,1,1,0,0,1,0,0,1,0,1,0,0,1,1,0,0,1,1,0,0,1,0,1,1,1,0,0,0,1,0, 1,0,0,1,0,0,1,0,1,1,0,0,0,0,0,1,1,0,0,0,1,1,1,1,1,0,1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,1,0,1,0,0,1,1,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,1,1,1,1,0,1,0,0,0,1,0,1,0,1,1,0,0,0,0,1,1,1,1,0,0,0,0,0,0,1,0,0, 1,0,0,0,1,0,1,1,0,0,1,0,0,1,1,1,0,1,0,0,0,1,1,0,0,1,0,1,1,0,0,1,1,0,1,0,1,1,0,0,1,0,1,1,0,1,0,1,0,0,1,0,1,0,1,0,0,1,0,1,1,0,0,1,0,0,0,0,1,0,0,1,1,1,0,1,1,1,1,1,1,0,0,1,1,0,1,1,1,1,1,1,1,1,1,0,0,1,1,1, 1,0,1,0,0,1,1,0,0,0,1,1,1,0,0,1,0,0,0,1,1,1,1,1,0,0,1,0,1,0,0,0,1,1,0,1,1,1,0,0,1,0,0,0,1,0,1,1,1,0,1,1,0,0,0,1,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,0,0,0,0,1,0,1,1,0,1,1,1,0,1,0,1,0,1,1,0,0,0,1,0,0,1,1,1, 1,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,1,0,1,1,1,1,0,1,1,1,1,0,1,1,0,1,1,0,0,0,1,0,1,0,0,0,1,0,1,1,1,1,0,1,0,1,1,1,0,0,1,0,0,0,1,1,1,0,0,1,0,0,0,0,1,1,1,0,1,0,1,1,0,1,0,0,0,0,0,1,0,1,1,1,0,1,0, 1,0,0,0,1,0,0,0,0,1,0,1,1,0,1,0,1,0,0,0,0,1,1,0,0,0,0,1,0,1,0,1,1,1,0,1,0,0,1,0,0,1,0,1,1,1,0,0,0,1,1,1,0,0,1,0,1,0,0,0,0,1,0,0,0,1,1,1,0,0,1,1,0,1,0,1,1,1,0,1,1,1,0,0,1,1,1,0,1,0,0,1,1,1,1,1,0,0,1,1, 1,0,0,1,0,1,0,0,1,1,0,0,0,1,1,0,1,0,1,0,1,1,1,0,0,1,0,0,0,0,0,1,1,0,1,1,0,0,0,0,0,1,1,1,1,0,0,1,0,0,1,1,0,0,0,1,0,0,0,0,0,0,1,0,0,1,0,1,1,1,1,0,0,0,1,0,1,1,1,0,0,1,1,1,1,1,0,1,0,0,0,0,0,1,0,0,1,0,0,0, 1,0,1,1,0,0,0,0,0,1,0,0,0,1,1,0,0,1,0,0,1,0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,1,1,0,1,0,0,1,0,1,1,1,0,1,0,1,0,1,0,1,1,0,1,0,1,1,0,1,1,0,1,0,0,0,0,1,0,1,0,0,0,1,1,0,0,0,0,0,1,1,0,0,0, 0,0,0,0,1,0,0,0,1,1,1,0,1,0,0,0,0,1,0,0,0,1,1,1,0,0,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,1,1,1,1,1,0,0,1,0,0,1,0,0,1,0,0,1,1,1,0,1,1,1,1,1,1,1,1,1,0,0,1,1,0,0,1,1,0,1,0,0,0,1,1,1,1,0,1,0,1,0,1,0,0,0,0,1,0,1, 0,1,1,0,0,1,1,1,1,0,0,0,1,1,1,0,0,1,1,0,1,1,1,0,0,1,0,0,0,1,1,1,0,1,0,1,0,0,1,0,1,1,0,0,1,0,0,0,1,0,0,1,1,1,1,0,0,1,0,0,0,1,1,1,0,0,1,0,0,1,1,0,1,1,1,0,0,1,1,1,1,1,1,1,1,1,0,1,0,1,0,0,1,0,1,1,0,0,0,1, 1,0,0,0,1,0,0,0,0,0,0,0,0,1,1,1,0,0,1,1,1,0,0,0,1,0,1,1,1,0,1,0,1,1,1,0,1,1,1,1,0,1,1,1,0,0,0,1,0,1,1,1,0,0,0,0,1,0,0,1,0,1,1,1,0,1,0,1,0,1,1,0,0,1,0,0,1,1,1,1,0,0,0,0,1,1,0,1,0,1,1,0,1,1,0,0,1,1,1,0, 1,1,0,1,1,1,1,0,0,0,1,0,0,0,0,0,1,1,1,1,0,1,1,0,1,0,1,1,1,0,1,0,0,0,0,0,1,1,0,1,0,0,1,0,0,0,1,1,1,1,0,1,1,1,0,1,1,1,1,1,0,1,1,0,1,0,1,1,1,0,0,0,0,0,1,0,0,1,1,0,0,0,1,1,1,0,1,1,1,0,1,0,1,1,0,0,1,0,1,0, 1,1,0,1,1,0,1,0,0,0,1,0,0,0,0,1,1,1,0,1,1,0,0,1,1,1,0,1,1,1,1,1,0,1,1,0,0,0,1,1,1,1,1,1,1,0,1,1,1,1,0,1,0,1,1,1,1,0,0,1,1,0,1,1,0,1,0,1,0,1,1,0,0,1,1,0,1,0,0,0,1,1,0,1,1,0,1,1,0,1,1,0,0,1,1,1,0,0,0,0, 1,0,1,0,0,0,0,0,0,1,0,1,0,0,0,0,1,1,0,0,0,1,0,1,1,1,0,0,0,0,0,0,1,0,0,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,0,0,0,0,0,1,0,0,1,0,1,0,0,0,0,0,1,1,1,0,0,0,1,0,0,1,0,1,0,0,0,1,1,1,1,1,1,1,0,1,1,0,0,1,1,1,0,0,1,0, 1,0,0,1,1,0,0,1,1,0,0,0,0,1,0,1,0,1,1,0,0,0,1,0,0,0,1,1,1,0,1,1,1,0,0,1,1,0,0,0,0,1,0,1,0,1,0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,1,0,1,1,1,1,1,1,1,0,0,1,0,0,1,0,0,0,0,0, 0,0,0,0,1,0,0,1,0,1,0,0,1,0,1,0,0,1,1,1,0,1,0,0,1,1,0,0,1,0,0,1,0,1,1,0,0,1,1,1,0,0,1,0,1,0,1,0,0,0,0,0,1,1,0,0,0,1,0,0,1,0,1,1,1,0,0,0,1,0,1,0,1,1,0,0,1,1,1,1,1,0,0,0,1,1,1,0,1,1,1,1,0,1,1,0,1,1,1,0, 1,0,1,0,0,1,0,0,0,1,0,1,0,0,1,0,0,0,0,1,0,1,0,1,1,1,1,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,1,0,1,1,1,1,0,1,1,1,0,1,0,1,0,1,0,1,1,0,0,1,1,1,1,0,0,1,0,1,0,0,1,1,0,1,1,0,1,0,0,0,1,0,1,0,0,1,0,0,1,0,0,0,1,1,1,1, 1,1,1,0,1,0,1,0,1,0,0,0,1,0,1,1,0,1,1,1,0,1,1,0,0,0,0,1,0,1,0,1,0,0,0,0,0,0,1,0,0,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,0,0,0,1,1,0,1,0,1,1,0,1,1,0,0,1,0,1,1,1,1,1,0,0,1,1,0,0,0,0,0,1,1,0,1,1,1,0,1,0,0,0,0,1, 0,1,1,1,0,0,0,1,1,0,1,1,1,1,1,1,1,0,1,0,1,0,0,0,0,1,1,0,0,0,1,1,1,0,0,0,0,0,1,0,1,0,0,1,0,1,0,0,1,0,1,1,0,1,1,0,1,0,1,0,1,1,0,1,1,1,1,1,0,0,1,0,0,0,0,1,1,0,1,0,1,1,0,0,0,1,1,0,1,1,0,0,0,1,0,0,0,0,0,1, 1,1,0,0,0,0,0,1,0,0,1,0,0,0,0,0,1,1,0,0,0,0,1,1,0,0,1,1,0,0,1,0,0,1,0,0,0,0,0,1,0,1,1,0,0,0,1,0,1,1,0,1,0,1,1,1,1,1,1,0,0,1,0,1,0,1,1,1,0,1,0,0,0,0,1,0,1,1,1,0,0,1,1,1,0,1,1,1,0,0,0,1,0,0,0,1,1,0,1,0, 0,0,0,1,1,0,1,1,1,0,0,1,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,1,0,1,0,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0,1,1,1,1,1,0,1,0,1,1,1,1,1,0,0,0,1,1,0,0,1,1,1,0,1,0,1,1,0,1,0,0,0,1,1,1,1,1,1,0,1,1,0,1,1,0,0,1,0,1,1,1, 0,1,1,1,0,1,1,0,0,1,1,0,0,1,0,0,0,1,1,1,0,1,1,0,0,0,0,0,0,1,1,1,0,1,1,1,0,1,1,1,1,0,1,0,0,0,0,0,1,1,1,0,1,1,0,1,0,0,1,0,1,0,1,1,0,1,0,0,0,0,1,1,0,1,1,1,0,0,0,0,1,0,0,0,0,1,1,0,0,1,1,1,0,0,1,0,1,1,0,0, 0,0,1,0,1,0,0,1,0,0,0,1,1,0,1,1,1,0,0,0,0,0,1,1,0,0,0,1,1,1,1,0,1,1,1,0,0,0,1,1,0,1,1,0,0,0,1,1,0,1,0,0,1,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,0,0,0,0,0,1,0,0,1,1,1,0,0,1,1,0,1,0,0,0,1,0,0,0,1,1,0,1,1,0,1, 0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,0,1,1,0,0,0,1,1,1,1,1,0,0,1,0,1,0,0,1,1,0,0,1,0,0,0,1,0,0,1,1,0,0,1,1,0,1,0,1,0,1,1,1,1,0,0,0,1,1,0,1,0,0,1,1,1,1,0,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,1,1,1,0,1,1,0,0,1,0,0, 1,1,1,0,0,0,0,0,0,0,1,0,1,1,0,1,1,0,1,0,0,0,1,1,1,1,1,0,0,1,1,1,1,0,0,0,0,1,1,1,0,1,1,1,0,1,1,0,1,1,1,0,0,1,0,1,0,0,0,0,1,1,0,1,1,1,0,1,1,0,1,0,1,1,0,1,1,0,1,0,1,0,0,1,0,0,1,1,1,1,0,1,0,1,0,0,1,1,1,0, 1,1,1,1,0,1,0,0,1,1,1,1,1,1,1,1,0,1,1,1,0,1,1,0,0,1,1,1,1,1,1,1,1,0,1,0,0,0,1,1,0,1,1,1,1,1,0,0,0,0,0,1,0,0,0,1,1,1,1,1,1,0,1,1,0,0,1,1,1,1,0,0,0,1,0,0,0,0,1,0,1,1,0,0,0,1,1,1,0,1,0,1,0,1,1,0,1,0,1,0, 0,0,0,1,1,1,1,0,1,0,1,0,0,0,0,0,1,1,1,0,1,1,0,0,0,0,0,0,0,1,1,1,0,0,0,0,1,0,1,1,0,1,0,1,0,1,0,0,1,1,1,0,1,0,0,0,0,0,1,1,1,0,0,0,0,1,1,0,1,1,0,1,0,1,0,0,0,1,1,0,1,1,0,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0, 0,0,0,1,1,0,1,1,1,0,0,0,0,1,1,0,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,0,0,1,0,0,0,1,0,0,0,0,1,0,1,0,0,1,0,0,0,1,0,0,1,0,0,0,1,1,1,0,0,1,1,0,1,0,1,0,1,1,1,0,1,0,0,0,0,1,0,1,1,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0, 0,1,1,0,0,1,1,1,0,1,0,0,1,1,1,0,1,1,1,0,1,0,1,1,1,1,0,0,1,1,0,1,0,0,0,1,1,0,1,0,1,1,0,1,1,1,1,1,0,1,1,1,1,0,0,1,1,0,0,0,1,1,1,0,1,1,0,1,0,0,0,0,0,0,1,0,0,1,0,0,1,0,0,1,0,1,0,0,0,1,0,1,1,0,1,1,0,0,0,1, 0,0,0,0,1,0,0,1,1,1,0,1,0,0,0,0,1,0,1,1,0,0,0,0,0,1,1,1,1,1,0,1,0,0,1,0,1,0,1,1,0,0,1,1,1,1,0,1,1,1,0,1,1,0,0,0,1,1,1,0,0,1,0,0,1,0,0,1,0,0,0,0,1,0,0,1,1,0,1,0,1,0,1,0,0,1,0,0,0,1,0,1,1,1,0,1,1,1,1,0, 1,0,1,1,1,0,1,1,0,1,1,0,1,0,0,0,1,0,0,0,1,1,1,0,0,0,0,0,0,1,0,1,1,0,1,0,0,0,1,0,0,1,0,0,1,1,0,0,1,1,0,0,0,0,0,1,1,0,1,1,0,0,0,1,1,1,1,1,1,1,0,0,1,1,1,0,0,1,0,1,0,1,0,1,1,0,0,0,1,1,0,0,0,0,1,0,1,0,0,0, 0,1,0,0,1,0,0,1,1,1,1,0,0,0,0,1,1,0,0,1,1,1,1,1,1,1,0,1,1,0,1,1,1,1,1,0,0,1,1,0,1,0,1,1,1,0,0,1,1,0,1,0,1,1,1,0,1,1,0,0,0,0,1,0,0,0,1,1,1,1,1,1,1,0,1,0,1,0,0,1,1,1,1,1,0,0,1,0,0,0,0,0,0,1,0,0,0,1,1,0, 0,0,0,1,0,0,1,0,0,0,1,1,1,0,0,1,1,0,0,1,0,1,0,0,0,1,0,0,0,1,1,0,0,0,1,0,0,0,1,0,0,1,1,0,1,0,1,0,0,1,0,0,0,0,0,0,1,0,1,1,0,0,1,1,0,1,1,0,1,0,0,1,1,0,1,0,1,1,1,1,0,1,1,1,0,1,1,0,0,1,1,0,1,1,0,1,1,0,1,0, 1,1,1,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0,1,0,0,0,1,0,1,0,0,1,1,1,0,0,0,1,1,1,1,0,1,1,1,1,0,1,1,0,1,1,0,0,1,1,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,1,0,1,1,1,1,1,0,0,1,0,1,1,0,1,0,0,0,1, 1,0,1,1,0,0,1,0,1,0,0,0,1,0,1,0,1,0,1,1,1,1,1,1,0,1,0,0,0,0,1,1,0,0,0,0,0,1,0,0,0,1,0,1,0,1,1,1,1,1,1,1,1,0,0,1,1,1,1,0,0,0,1,0,1,0,1,0,1,1,0,1,0,0,1,0,0,0,1,1,1,0,1,1,1,1,1,0,0,0,0,1,0,1,0,0,0,1,1,1, 1,1,0,0,0,1,0,0,1,1,1,0,0,0,1,0,0,0,1,1,0,0,1,0,0,1,0,1,1,1,1,0,1,0,1,0,1,0,0,0,0,1,0,0,1,0,0,0,0,1,0,1,1,0,0,1,0,1,1,1,1,0,0,1,1,1,0,1,1,0,1,0,0,1,0,0,0,1,1,1,0,0,1,0,1,1,1,1,1,0,1,0,0,0,1,0,0,1,1,0, 1,0,1,1,1,0,1,0,0,0,0,1,1,0,0,0,1,0,1,0,0,1,0,1,0,1,0,1,1,0,0,0,0,0,0,1,0,1,0,1,1,1,0,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,1,0,0,1,1,0,1,1,0,0,0,0,1,1,1,1,0,1,0,0,0,1,1,0,0,0,1,1,1,1,0,1,1,0,1,0,1,0,0,1,1,1, 1,0,0,0,1,1,0,1,0,0,1,1,1,0,0,1,0,0,1,0,1,1,1,0,0,1,1,1,1,1,1,0,1,1,0,0,1,1,1,1,1,1,0,0,0,1,0,0,1,1,0,1,0,1,0,1,1,0,0,0,1,1,0,0,0,0,0,1,0,0,1,1,0,0,1,0,0,0,1,1,0,0,1,1,0,1,0,0,0,1,0,1,0,1,0,0,0,0,1,0, 1,0,1,0,1,1,1,0,0,0,0,0,0,1,0,0,0,0,1,0,1,0,0,1,1,0,1,0,1,1,0,1,1,1,0,1,1,0,0,1,0,1,0,0,0,0,1,0,0,0,0,1,1,0,0,1,0,0,1,1,1,0,0,0,1,1,0,0,0,0,0,1,1,1,1,1,0,0,0,0,1,1,0,0,0,0,0,0,1,1,0,1,0,0,0,0,0,0,0,0, 0,1,0,0,1,0,0,1,1,0,1,0,1,1,1,1,1,0,1,0,0,1,1,1,1,0,0,0,0,0,0,1,1,1,1,1,0,1,0,0,1,1,0,0,1,1,1,1,0,0,1,0,0,1,1,1,1,1,0,0,1,0,1,1,0,1,0,1,1,0,1,1,1,1,0,0,0,0,0,1,1,1,1,1,1,1,1,1,0,0,1,0,0,0,0,1,0,1,0,1, 0,1,0,1,0,0,0,1,1,0,1,1,0,0,0,1,1,0,1,1,1,0,1,0,1,1,1,1,0,0,1,1,0,0,1,1,0,1,1,0,0,0,1,0,0,1,0,0,0,1,1,0,0,1,0,0,1,0,0,0,1,1,1,1,1,1,1,0,1,1,1,1,0,1,0,0,1,1,0,0,1,0,0,1,1,0,0,1,1,1,0,0,1,0,0,1,0,1,1,1, 0,0,0,1,0,0,1,0,0,1,1,0,0,0,1,0,0,0,1,1,1,0,1,1,0,0,1,1,0,0,0,0,1,1,0,0,0,1,1,1,0,1,1,0,1,1,1,1,0,0,0,0,0,0,1,1,1,1,1,1,0,1,0,1,0,0,1,1,0,1,1,1,0,1,0,0,0,1,0,1,1,1,1,0,1,1,0,0,1,1,0,0,0,1,0,1,0,0,0,1, 1,0,1,1,0,1,0,1,0,0,0,1,0,0,1,0,1,0,1,0,0,0,0,1,1,0,1,0,0,0,0,1,0,0,0,1,0,1,0,1,0,1,1,1,1,0,1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,1,0,1,1,0,1,0,0,1,0,0,0,1,1,0,1,1,1,0,0,0,0,0,0,0,1,1,0,0,1,0,0,1,1,1,1,1,0,0, 0,0,0,1,0,1,0,1,0,1,1,0,0,1,0,0,1,1,1,0,0,1,1,0,0,0,0,0,0,0,1,1,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,1,0,0,1,1,0,1,0,0,0,0,0,1,0,0,0,1,1,0,1,0,1,1,1,0,0,0,1,0,1,0,0,1,1,1,1,0,0,0,0,1,0,0,1,1,1,1, 0,0,0,1,0,1,1,0,0,0,1,0,1,1,0,0,1,0,1,0,1,1,1,0,1,0,0,1,1,0,1,1,0,1,0,0,0,0,0,1,0,0,1,0,0,0,1,1,1,0,0,0,0,1,1,0,1,1,0,0,0,1,1,0,1,0,0,1,1,1,1,1,1,1,1,1,0,1,1,0,0,0,0,1,1,0,0,1,0,0,0,0,1,0,0,0,1,0,1,1, 0,1,1,1,1,1,1,1,1,0,0,0,0,1,0,1,0,0,0,0,1,0,1,0,0,0,0,0,1,1,1,1,1,1,1,0,1,0,1,1,1,0,0,1,0,0,0,0,1,1,0,1,0,1,1,0,1,1,0,1,0,0,0,1,1,0,0,0,0,0,1,1,1,0,1,0,1,1,1,1,1,1,1,0,0,1,1,1,1,0,1,0,0,1,1,1,0,0,0,0, 1,0,0,1,0,0,1,0,1,1,0,1,0,1,1,0,0,1,1,0,1,0,0,0,0,1,1,1,1,0,0,0,0,0,0,1,1,1,0,1,0,0,1,0,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1,0,1,0,0,0,1,1,1,1,1,1,1,1,1,1,0,1,0,0,1,0,1,1,1,1,1,0,1,1,0,0,0,1,0, 1,0,1,0,0,0,0,0,1,1,0,1,1,0,0,1,0,1,1,0,0,0,1,0,1,0,1,0,1,1,1,1,1,0,1,1,1,0,0,0,0,1,0,1,0,1,0,0,0,0,1,1,1,0,1,0,0,1,0,1,1,1,1,1,0,0,0,1,1,1,0,1,1,0,1,0,1,1,1,1,0,0,1,1,1,0,1,0,0,1,0,0,1,1,1,0,0,1,0,0 }; // generate a random graph of size n /* int g[n*n]; srand((unsigned)time(0)); for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { g[i*n+j] = rand() % 2; // std::cout << g[i*n+j] << " " ; } // std::cout << std::endl; } // std::cout << std::endl; */ // x_bool is a boolean representation of the clique set x BoolVarArray x_bool(*this, n, 0, 1); channel(*this, x_bool, x); for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { if (i != j) { // (x_bool[i] /\ x_bool[j]) -> ( g[i,j] > 0) BoolVar b(*this, 0, 1); if (g[i*n+j] > 0) { post(*this, b == 1, opt.icl()); } else { post(*this, b == 0, opt.icl()); } post(*this, tt(imp( x_bool[i] == 1 && x_bool[j] == 1, // -> b)), opt.icl()); } } } // cardinality of x cardinality(*this, x, c); // show all solutions with this cardinality if (c_args) { post(*this, c == c_args, opt.icl()); } // branching branch(*this, x_bool, INT_VAR_DEGREE_MIN, INT_VAL_SPLIT_MIN); } // Print solution virtual void print(std::ostream& os) const { os << "\t " << x << std::endl; } // Return cost virtual IntVar cost(void) const { return c; } // Constructor for cloning s Clique(bool share, Clique& s) : MaximizeScript(share,s), c_args(s.c_args) { x.update(*this, share, s.x); c.update(*this, share, s.c); } // Copy during cloning virtual Space* copy(bool share) { return new Clique(share,*this); } }; int main(int argc, char* argv[]) { SizeOptions opt("Clique"); opt.solutions(0); opt.icl(ICL_BND); opt.search(Clique::SEARCH_BAB); opt.search(Clique::SEARCH_DFS, "dfs"); opt.search(Clique::SEARCH_BAB, "bab"); opt.search(Clique::SEARCH_RESTART, "restart"); opt.parse(argc,argv); if (opt.size()) { opt.search(Clique::SEARCH_DFS); } if (opt.search() == Clique::SEARCH_DFS) { Script::run(opt); } else if (opt.search() == Clique::SEARCH_RESTART) { MinimizeScript::run(opt); } else { MinimizeScript::run(opt); } return 0; }