RLFAP.h

// RLFAP.h: The Radio Link Frequency Assignment Problem as a CSP.

/*
 * Copyright (C) 2004-2005 Tudor Hulubei <tudor@hulubei.net>.
 *
 * This library 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 library 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 library; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA,
 * 02111-1307, USA.
 */

 /*
  * Radio Link Frequency Assignment Benchmarks as provided by the
  * Centre d'Electronique de l'Armement (France).  See B. Cabon,
  * S. de Givry, L. Lobjois, T. Schiex and J.P. Warners, CONSTRAINTS
  * journal. 1998.
  */

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

#ifndef _CSP_EXAMPLES_RLFAP_H
#define _CSP_EXAMPLES_RLFAP_H


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


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


CSP_NAMESPACE_BEGIN(RLFAP)


using namespace std;


#ifdef __GNUG__
using namespace __gnu_cxx;
#endif

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


typedef csp::values::Int Value;
typedef csp::Domain Domain;
class Variable;


class DistanceConstraint :
    public csp::Constraint
{
  public:
    DistanceConstraint(int distance) :
        csp::Constraint(),
        m_distance(distance) {}

    virtual bool check() const;
    virtual wstring name() const { return L">"; }
    virtual wstring color() const { return L"red"; }
    virtual wstring textColor() const { return L"red"; }

  private:
    int m_distance;
};


class EqualityConstraint :
    public csp::Constraint
{
  public:
    EqualityConstraint(int distance) :
        csp::Constraint(),
        m_distance(distance) {}

    virtual bool check() const;
    virtual wstring name() const { return L"="; }
    virtual wstring color() const { return L"blue"; }
    virtual wstring textColor() const { return L"blue"; }

  private:
    int m_distance;
};


class Problem :
    public csp::Problem
{
  public:
    Problem(
        csp::RandomSequence& randomSequence,
        const wstring& domainsFileName,
        const wstring& variablesFileName,
        const wstring& constraintsFileName);
    Problem(const Problem& problem);
    virtual ~Problem();

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

    void addDistanceConstraint(int index0, int index1, int distance);
    void addEqualityConstraint(int index0, int index1, int distance);

    virtual wostream& printSolution(wostream& wos) const;

    virtual wostream& print(wostream& wos) const;

  private:
    void constructor(
        const wstring& domainsFileName,
        const wstring& variablesFileName,
        const wstring& constraintsFileName);

    void assignBackdoorVariable(csp::id_t variableId, csp::id_t valueId);
    void assignBackdoor();
    void unassignBackdoor();

    wstring m_domainsFileName;
    wstring m_variablesFileName;
    wstring m_constraintsFileName;

    // We keep the nodes in this vector just to be able to find them
    // quickly based on their index.
    vector<Variable*> m_nodes;

    // Convert a variable index into its position in m_nodes.
    hash_map<int, int> m_position;
};


class Variable :
    public csp::variables::Int
{
  public:
    Variable(
        const Problem& problem,
        const vector<csp::values::Int>& array,
        const wstring& name);

    virtual wstring name() const { return m_name; }
    int index() const { return m_index; }
    void setColor(const wstring& color) { m_color = color; }

    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 m_color;
    }
    virtual wstring textColor() const { return L"black"; }

    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:
    wstring m_name;
    int m_index;
    wstring m_color;
    bool m_isBackdoor;
    bool m_isBackdoorKey;
    bool m_isBranching;
};


CSP_NAMESPACE_END(RLFAP)


#endif // _CSP_EXAMPLES_RLFAP_H

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

---