feature_network.hpp

#ifndef INFRARED_FEATURE_NETWORK_HPP
#define INFRARED_FEATURE_NETWORK_HPP
 
/*
 * InfraRed ---  A generic engine for Boltzmann sampling over constraint networks
 * (C) Sebastian Will, 2018
 *
 * This file is part of the InfraRed source code.
 *
 * InfraRed provides a generic framework for tree decomposition-based
 * Boltzmann sampling over constraint networks
 */
 
#include <vector>
#include <memory>
#include <limits>
#include <iterator>
#include <cstdlib>
 
#include "cluster.hpp"
#include "finite_domain.hpp"
 
namespace ired {
 
    template<class FunValue>
    class PFEvaluationPolicy {
    public:
        using fun_value_t = FunValue;
        using constraint_t = Function<bool>;
        using function_t = Function<fun_value_t>;
 
        // selector for stochastic backtracking
        class selector {
        public:
            selector(const fun_value_t &value): 
                value_(value),
                r_( rand()/(RAND_MAX+1.0) * value) {
            }
 
            auto
            select(const fun_value_t &x) {
                return x > r_;
            }
        private:
            fun_value_t value_;
            fun_value_t r_;
        };
 
        static
        fun_value_t
        plus(const fun_value_t &x, const fun_value_t &y) {
            return x+y;
        }
 
        static
        fun_value_t
        mul(const fun_value_t &x, const fun_value_t &y) {
            return x*y;
        }
 
        static
        fun_value_t
        one() {
            return fun_value_t(1);
        }
 
        static
        fun_value_t
        zero() {
            return fun_value_t();
        }
    };
 
    template<class FunValue>
    class StdEvaluationPolicy: public PFEvaluationPolicy<FunValue> {
    };
 
    template<class FunValue>
    class ArcticEvaluationPolicy {
    public:
        using fun_value_t = FunValue;
        using constraint_t = Function<bool>;
        using function_t = Function<fun_value_t>;
 
        // selector for 'classic' backtracking
        class selector {
        public:
            selector(const fun_value_t &value): value_(value) {}
            auto
            select(const fun_value_t &x) {
                return x==value_;
            }
        private:
            fun_value_t value_;
        };
 
        static
        fun_value_t
        plus(const fun_value_t &x, const fun_value_t &y) {
            return std::max(x,y);
        }
 
        static
        fun_value_t
        mul(const fun_value_t &x, const fun_value_t &y) {
            return x + y;
        }
 
        static
        fun_value_t
        one() {
            return fun_value_t();
        }
 
        static
        fun_value_t
        zero() {
            return std::numeric_limits<fun_value_t>::min();
        }
    };
 
    template<>
    class StdEvaluationPolicy<bool> {
    public:
        using fun_value_t = bool;
        using constraint_t = Constraint;
        using function_t = Constraint;
 
        static
        fun_value_t
        plus(const fun_value_t &x, const fun_value_t &y) {
            return x || y;
        }
 
        static
        fun_value_t
        mul(const fun_value_t &x, const fun_value_t &y) {
            return x && y;
        }
 
        static
        fun_value_t
        one() {
            return true;
        }
 
        static
        fun_value_t
        zero() {
            return false;
        }
    };
 
    template<class FunValue, class EvaluationPolicy> class FeatureNetwork {
    public: using var_idx_t = int; using var_value_t = int;
 
        using fun_value_t = FunValue;
 
        using assignment_t = Assignment;
        using function_t = Function<FunValue>;
        using constraint_t = Constraint;
 
        using evaluation_policy_t = EvaluationPolicy;
 
        using cluster_t = Cluster<fun_value_t>;
 
        FeatureNetwork() {};
 
        explicit
        FeatureNetwork(const FiniteDomainVector &domains)
            : domains_(domains) {
        };
 
        FeatureNetwork(int num_vars, FiniteDomain domain)
            : domains_(num_vars, domain) {
        };
 
 
        ~FeatureNetwork() {};
 
 
        var_idx_t
        add_variable(FiniteDomain domain) {
            domains_.push_back(domain);
            return domains_.size()-1;
        }
 
        auto
        add_constraint(const std::shared_ptr<constraint_t> &x) {
            if ( x->auto_materialize() ) {
                //materialize it
 
                // for evaluating the constraints, construct a
                // constraint network with the same variables
                // and domains as this one, which evaluates constraints
                auto cn = FeatureNetwork<bool, StdEvaluationPolicy<bool>>(domains_);
                auto mx = std::make_shared<MaterializedFunction<bool, vecS>>(x.get(),cn);
 
                constraints_.push_back( mx );
            } else {
                constraints_.push_back( x );
            }
            return constraints_.back().get();
        }
 
        auto
        add_function(const std::shared_ptr<function_t> &x) {
            if ( x->auto_materialize() ) {
                //materialize it
                auto mx = std::make_shared<MaterializedFunction<typename function_t::fun_value_t, vecS>>(x.get(),*this);
                functions_.push_back( mx );
            } else {
                functions_.push_back( x );
            }
            return functions_.back().get();
        }
 
        int
        num_vars() const {return domains_.size();}
 
        const
        auto & domains() const {
            return domains_;
        }
 
    private:
        FiniteDomainVector domains_;
 
        std::vector<std::shared_ptr<function_t>> functions_;
        std::vector<std::shared_ptr<constraint_t>> constraints_;
    };
 
}
#endif