examples/Random.h

// Random.h -- A random generator of CSPs.

/*
 * Copyright (C) 1997-1999,2003-2005 Tudor Hulubei <tudor@hulubei.net>.
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public License as
 * published by the Free Software Foundation; either version 2, or (at
 * your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA,
 * 02111-1307, USA.
 */

// $Id: examples_2Random_8h-source.html,v 1.1 2005/05/25 12:37:18 tudor Exp $

#ifndef _CSP_EXAMPLES_Random_H
#define _CSP_EXAMPLES_Random_H


#ifndef __cplusplus
#error Must use C++ for the type Random.
#endif


#include <string>
#include <stdexcept>


#include "values/Int.h"
#include "variables/Int.h"


CSP_NAMESPACE_BEGIN(Random)


using namespace std;

#ifdef __GNUG__
using namespace __gnu_cxx;
#endif

#if defined(_MSC_VER) && (_MSC_VER == 1310)
using namespace stdext;
#endif


class Variable;
class Value;


class Problem :
    public csp::Problem
{
  public:
    Problem(
        csp::RandomSequence& randomSequence,
        const wstring& model,
        bool flawed,
        bool weightSearch,
        size_t nVariables,
        size_t domainSize,
        double density,
        double tightness,
        bool nonStandardDensity = true,
        size_t weakSpots = 0,
        size_t weakSpotConstraints = 5);

    Problem(const Problem& problem);
    Problem(csp::RandomSequence& randomSequence, wifstream& wifs);

    virtual wstring name() const { return L"Random"; }

    bool weightSearch() const { return m_weightSearch; }

    double weight() const;
    double minWeight() const;
    double maxWeight() const;

    double currentWeight() const;

    double minAcceptableWeight() const { return m_minAcceptableWeight; }
    double maxAcceptableWeight() const { return m_maxAcceptableWeight; }

    void setMinAcceptableWeight(double minAcceptableWeight)
    {
        assert(minWeight() <= minAcceptableWeight);
        assert(minAcceptableWeight <= maxWeight());
        m_minAcceptableWeight = minAcceptableWeight;
    }

    void setMaxAcceptableWeight(double maxAcceptableWeight)
    {
        assert(minWeight() <= maxAcceptableWeight);
        assert(maxAcceptableWeight <= maxWeight());
        m_maxAcceptableWeight = maxAcceptableWeight;
    }

    double minFutureWeight() const;

    double maxFutureWeight() const;

    double idealWeight() const { return m_idealWeight; }

    void computeConstraintAcceptableWeightRange();

    virtual void save(wofstream& wofs) const;

    void loadSolutions(wifstream& wifs);

    void saveSolution(wofstream& wofs) const;

    virtual wostream& printSolution(wostream& wos) const;
    virtual wostream& print(wostream& wos) const;

  private:
    class Pair
    {
      public:
        Variable* variable0;
        Variable* variable1;
    };

    void constructor(
        const wstring& model,
        bool flawed,
        bool weightSearch,
        size_t nVariables,
        size_t domainSize,
        double density,
        double tightness,
        bool nonStandardDensity,
        size_t weakSpots,
        size_t weakSpotConstraints);

    void createConnectingConstraints(size_t nPairs);

    void createCompleteConstraintSet(vector<Pair>& all);

    void createConstraints(size_t nConstraints, size_t nPairs);

    void createConstraints(double probability, size_t nPairs);

    wstring m_model;

    bool m_flawed;

    bool m_weightSearch;
    double m_idealWeight;
    double m_minAcceptableWeight;
    double m_maxAcceptableWeight;

    /* These are here mainly because we want to be able to report the
       configuration when we load the problem from a file/stream.  */
    size_t m_nVariables;
    size_t m_domainSize;
    double m_density;
    double m_tightness;

    double m_densityGranularity;

    double m_tightnessGranularity;

    bool m_nonStandardDensity;

    size_t m_weakSpots;
    size_t m_weakSpotConstraints;

    wstring m_checksum;
};


class Value :
    public csp::values::Int
{
  public:
    Value(const int v, const double weight) :
        csp::values::Int(v), m_weight(weight) {}
    Value(const Value& v) :
        csp::values::Int(v) { m_weight = v.m_weight; }

    double weight() const { return m_weight; }

    // Assignment operator.
    Value& operator=(const Value& v)
    {
        Int::operator=(v);
        m_weight = v.m_weight;
        return *this;
    }

  private:
    double m_weight;
};


typedef csp::Domain Domain;


class Variable :
    public csp::variables::Int
{
  public:
    Variable(
        const Problem& problem,
        const int min,
        const int max);

    double weight() const { return value().weight(); }

    double minWeight() const { return m_minWeight; }
    double maxWeight() const { return m_maxWeight; }

    Value& value() const { return static_cast<Value&>(Int::value()); }

    virtual wostream& print(wostream& wos) const
    {
        csp::variables::Int::print(wos);
        //wos << L" w=" << weight();
        return wos;
    }

    virtual wstring color() const
    {
        // It's important that the isBackdoor test comes last, as both
        // branching variables (those involved in branching
        // assignments) and backdoor keys are in the backdoor.
        if (m_isBranching)
            return L"pink";
        if (m_isBackdoorKey)
            return L"orange";
        if (m_isBackdoor)
            return L"red";
        return csp::Variable::color();
    }

    virtual wstring textColor() const { return csp::Variable::textColor(); }

    virtual wstring shape() const
    {
        if (m_isBackdoor || m_isBackdoorKey || m_isBranching)
            return L"rectangle";
        return csp::Variable::shape();
    }

    virtual void setBackdoorStatus(bool status) { m_isBackdoor = status; }
    virtual void setBackdoorKeyStatus(bool status) { m_isBackdoorKey = status; }
    virtual void setBranchingStatus(bool status) { m_isBranching = status; }

  private:
    Variable(const Variable&);

    Variable& operator=(const Variable&);

    double m_minWeight;
    double m_maxWeight;

    bool m_isBackdoor;
    bool m_isBackdoorKey;
    bool m_isBranching;
};


class Constraint :
    public csp::Constraint
{
  public:
    Constraint(Problem& problem);
    Constraint(Problem& problem, const Constraint& constraint);
    virtual ~Constraint() { delete m_weights; }

    double weight() const;
    double weight(const Variable& variable, const Value& value) const;

    double minWeight() const { return m_minWeight; }
    double maxWeight() const { return m_maxWeight; }

    void buildWrapper(
        const wstring& model,
        size_t nPairs,
        double probability,
        bool flawed);

    void buildEmpty();

    void addPair(int value0, int value1);

    virtual bool check() const;

    bool isFlawless() const;

    ulonglong allowedTuples() const;

    virtual wostream& print(wostream& wos) const
    {
        csp::Constraint::print(wos);
        //wos << L" w=" << weight();
        return wos;
    }

  private:
    class Pair
    {
      public:
        Value* value0;
        Value* value1;
    };

    void buildWeights(int value0, int value1, size_t domainSize);

    size_t buildPairsUnconditionally(
        vector<Pair>& source, size_t n, size_t domainSize);

    size_t buildFixedNumberOfPairs(
        vector<Pair>& source, size_t n, size_t domainSize);

    void buildAllPairs(vector<Pair>& all);

    void buildAllPairs(vector<Pair>& goods, vector<Pair>& rest);

    void build(double probability, size_t nPairs, bool flawed);

    void build(size_t nPairs, bool flawed);

    Problem& m_problem;

    double m_minWeight;
    double m_maxWeight;

    csp::BitArray m_pairs;
    hash_map<int, double>* m_weights;
};


class AcceptableWeight :
    public csp::ValueOH
{
  public:
    AcceptableWeight(
        csp::Decomposition& decomposition,
        const vector<pair<double, double> >& intervals,
        double quality = 1) :
        csp::ValueOH(L"Acceptable Weight", decomposition, intervals, quality),
        m_ignored(false)
    {
        if (m_quality < 1)
            LOG(L"Random::AcceptableWeight", Warning,
                L"Quality setting ignored");
    }

    void setIgnoredFlag(bool ignored) { m_ignored = ignored; }

    void select(
        csp::Domain& domain,
        csp::Domain& selected,
        csp::Variable& variable);

    virtual long double score(
        csp::Variable& /*variable*/,
        const csp::Value& /*value*/)
    {
        LOG(L"Random::AcceptableWeight", Debug, L"Not implemented!");
        assert(0);
        abort();
        return -1;
    }

  private:
    // `true' if the heuristic is to be (temporary) ignored.
    bool m_ignored;

    typedef struct
    {
        csp::Value* m_value;
        double m_proximity;
    } proximity_type;

    template<class T>
    struct proximity_less :
        public binary_function<T, T, bool>
    {
      public:
        bool operator()(const T& x, const T& y) const
        {
            return fabs(x.m_proximity) < fabs(y.m_proximity);
        }
    };
};


CSP_NAMESPACE_END(Random)


#endif // _CSP_EXAMPLES_Random_H

// Local Variables:
// mode: C++
// End:

---