mirror of
https://github.com/BlackLight/libCSP--.git
synced 2024-11-23 20:25:12 +01:00
341 lines
6.7 KiB
C++
341 lines
6.7 KiB
C++
/*
|
|
* =====================================================================================
|
|
*
|
|
* Filename: csp++.cpp
|
|
*
|
|
* Description:
|
|
*
|
|
* Version: 0.1.1
|
|
* Created: 17/05/2010 09:17:13
|
|
* Revision: none
|
|
* Compiler: gcc
|
|
*
|
|
* Author: BlackLight (http://0x00.ath.cx), <blacklight@autistici.org>
|
|
* Licence: GNU GPL v.3
|
|
* Company: lulz
|
|
*
|
|
* =====================================================================================
|
|
*/
|
|
|
|
|
|
#include <algorithm>
|
|
|
|
#define __CSPPP_CPP
|
|
#include "csp++-def.h"
|
|
#undef __CSPPP_CPP
|
|
|
|
using std::vector;
|
|
|
|
|
|
template<class T>
|
|
void
|
|
CSP<T>::__init (int n, bool (*c)(vector< CSPvariable<T> >))
|
|
{
|
|
variables = vector< CSPvariable<T> >(n);
|
|
__default_domains = vector< vector<T> >(n);
|
|
|
|
for (size_t i=0; i < variables.size(); i++) {
|
|
variables[i].index = i;
|
|
variables[i].fixed = false;
|
|
}
|
|
|
|
constraints = vector< bool (*)(std::vector< CSPvariable<T> >) >(1);
|
|
constraint = c;
|
|
__has_default_value = false;
|
|
}
|
|
|
|
template<class T>
|
|
CSP<T>::CSP (int n, bool (*c)(vector< CSPvariable<T> >))
|
|
{
|
|
__init (n, c);
|
|
}
|
|
|
|
template<class T>
|
|
CSP<T>::CSP ( int n, T default_value, bool set_value, bool (*c)(std::vector< CSPvariable<T> >) )
|
|
{
|
|
__init (n, c);
|
|
|
|
for ( size_t i=0; i < variables.size(); i++ ) {
|
|
variables[i].value = default_value;
|
|
variables[i].fixed = set_value;
|
|
}
|
|
|
|
__default_value = default_value;
|
|
__has_default_value = true;
|
|
}
|
|
|
|
template<class T>
|
|
void
|
|
CSP<T>::setDomain (size_t index, vector<T> domain)
|
|
{
|
|
if (index >= variables.size())
|
|
throw CSPexception("Index out of range");
|
|
|
|
variables[index].domain = domain;
|
|
__default_domains[index] = domain;
|
|
}
|
|
|
|
template<class T>
|
|
void
|
|
CSP<T>::setDomain (size_t index, T domain[], int size)
|
|
{
|
|
if (index >= variables.size())
|
|
throw CSPexception("Index out of range");
|
|
|
|
if (size < 0)
|
|
throw CSPexception("Invalid domain size");
|
|
|
|
variables[index].domain = vector<T>(size);
|
|
|
|
for (int i=0; i < size; i++) {
|
|
variables[index].domain[i] = domain[i];
|
|
__default_domains[index].push_back(domain[i]);
|
|
}
|
|
}
|
|
|
|
template<class T>
|
|
void
|
|
CSP<T>::setConstraint ( bool (*c)(vector< CSPvariable<T> >))
|
|
{
|
|
constraints = vector< bool(*)(vector< CSPvariable<T > >) >(1);
|
|
constraint = c;
|
|
}
|
|
|
|
template<class T>
|
|
void
|
|
CSP<T>::setConstraint ( std::vector< bool(*)(std::vector< CSPvariable<T> >) > c )
|
|
{
|
|
constraints = c;
|
|
}
|
|
|
|
template<class T>
|
|
void
|
|
CSP<T>::appendConstraint ( bool (*c)(vector< CSPvariable<T> >))
|
|
{
|
|
constraints.push_back(c);
|
|
}
|
|
|
|
template<class T>
|
|
void
|
|
CSP<T>::dropConstraint ( size_t index )
|
|
{
|
|
if (index >= constraints.size())
|
|
throw CSPexception("Index out of range");
|
|
|
|
constraints.erase( constraints.begin() + index );
|
|
}
|
|
|
|
template<class T>
|
|
void
|
|
CSP<T>::restoreDomains ( void )
|
|
{
|
|
for (int i=0; i < variables.size(); i++)
|
|
variables[i].domain = __default_domains[i];
|
|
}
|
|
|
|
template<class T>
|
|
void
|
|
CSP<T>::refreshDomains ( void )
|
|
{
|
|
vector< arc<T> > arcs;
|
|
restoreDomains();
|
|
|
|
for (typename vector< CSPvariable<T> >::iterator x = variables.begin(); x != variables.end(); x++) {
|
|
for (typename vector< CSPvariable<T> >::iterator y = variables.begin(); y != variables.end(); y++) {
|
|
T xOrigValue = x->value;
|
|
T yOrigValue = y->value;
|
|
|
|
for (size_t i=0; i < x->domain.size(); i++) {
|
|
if ( x->fixed ) {
|
|
if ( x->domain[i] != x->value )
|
|
continue;
|
|
}
|
|
|
|
x->value = x->domain[i];
|
|
|
|
for (size_t j=0; j < y->domain.size(); j++) {
|
|
if ( y->fixed ) {
|
|
if ( y->domain[j] != y->value )
|
|
continue;
|
|
}
|
|
|
|
y->value = y->domain[j];
|
|
bool isConfigurationValid = true;
|
|
|
|
for ( typename std::vector< bool (*)(std::vector< CSPvariable<T> >) >::iterator c = constraints.begin();
|
|
c != constraints.end() && isConfigurationValid;
|
|
c++ ) {
|
|
if (!(*c)(variables))
|
|
isConfigurationValid = false;
|
|
}
|
|
|
|
if (isConfigurationValid) {
|
|
arc<T> a;
|
|
a.var[0] = *x; a.var[1] = *y;
|
|
a.value[0] = x->value; a.value[1] = y->value;
|
|
arcs.push_back(a);
|
|
}
|
|
}
|
|
|
|
y->value = yOrigValue;
|
|
}
|
|
|
|
x->value = xOrigValue;
|
|
}
|
|
|
|
vector<T> domain = vector<T>();
|
|
|
|
for (size_t i=0; i < arcs.size(); i++) {
|
|
if (arcs[i].var[0].index == x->index ||
|
|
arcs[i].var[1].index == x->index) {
|
|
T value = (arcs[i].var[0].index == x->index) ? arcs[i].value[0] : arcs[i].value[1];
|
|
bool found = false;
|
|
|
|
for (size_t j=0; j < domain.size() && !found; j++) {
|
|
if (domain[j] == value)
|
|
found = true;
|
|
}
|
|
|
|
if (!found) {
|
|
domain.push_back(value);
|
|
}
|
|
}
|
|
}
|
|
|
|
sort(domain.begin(), domain.end());
|
|
x->domain = domain;
|
|
}
|
|
}
|
|
|
|
template<class T>
|
|
std::vector<T>
|
|
CSP<T>::domain ( size_t index )
|
|
{
|
|
if (index >= variables.size())
|
|
throw CSPexception("Index out of range");
|
|
|
|
return variables[index].domain;
|
|
}
|
|
|
|
template<class T>
|
|
size_t
|
|
CSP<T>::size( void )
|
|
{
|
|
return variables.size();
|
|
}
|
|
|
|
template<class T>
|
|
void
|
|
CSP<T>::setValue ( size_t index, T value )
|
|
{
|
|
if (index >= variables.size())
|
|
throw CSPexception("Index out of range");
|
|
|
|
variables[index].value = value;
|
|
variables[index].fixed = true;
|
|
}
|
|
|
|
template<class T>
|
|
void
|
|
CSP<T>::unsetValue ( size_t index )
|
|
{
|
|
if (index >= variables.size())
|
|
throw CSPexception("Index out of range");
|
|
|
|
if (__has_default_value)
|
|
variables[index].value = __default_value;
|
|
variables[index].fixed = false;
|
|
}
|
|
|
|
template<class T>
|
|
bool
|
|
CSP<T>::isSatisfiable ( void )
|
|
{
|
|
for ( size_t i=0; i < variables.size(); i++ ) {
|
|
if ( variables[i].domain.empty() )
|
|
return false;
|
|
}
|
|
|
|
return true;
|
|
}
|
|
|
|
template<class T>
|
|
bool
|
|
CSP<T>::hasUniqueSolution ( void )
|
|
{
|
|
for ( size_t i=0; i < variables.size(); i++ ) {
|
|
if (variables[i].domain.size() != 1)
|
|
return false;
|
|
}
|
|
|
|
return true;
|
|
}
|
|
|
|
template<class T>
|
|
void
|
|
CSP<T>::assignUniqueDomains ( void )
|
|
{
|
|
for ( int i=0; i < size(); i++ ) {
|
|
if (domain(i).size() == 1)
|
|
setValue( i, domain(i)[0] );
|
|
}
|
|
}
|
|
|
|
template<class T>
|
|
bool
|
|
CSP<T>::isSet ( size_t index )
|
|
{
|
|
if (index >= variables.size())
|
|
throw CSPexception("Index out of range");
|
|
|
|
return variables[index].fixed;
|
|
}
|
|
|
|
template<class T>
|
|
T
|
|
CSP<T>::value ( size_t index )
|
|
{
|
|
if (index >= variables.size())
|
|
throw CSPexception("Index out of range");
|
|
|
|
return variables[index].value;
|
|
}
|
|
|
|
template<class T>
|
|
void
|
|
CSP<T>::solve ( size_t max_iterations )
|
|
{
|
|
bool changed = false;
|
|
size_t steps = 1;
|
|
vector< vector<T> > oldDomains(size());
|
|
|
|
do {
|
|
if (max_iterations != 0) {
|
|
if (steps++ > max_iterations)
|
|
break;
|
|
}
|
|
|
|
for ( size_t i=0; i < size(); i++ ) {
|
|
oldDomains[i] = variables[i].domain;
|
|
}
|
|
|
|
refreshDomains();
|
|
assignUniqueDomains();
|
|
|
|
if (hasUniqueSolution())
|
|
break;
|
|
|
|
changed = false;
|
|
|
|
for ( size_t i=0; i < size(); i++ ) {
|
|
if (domain(i).size() != oldDomains[i].size())
|
|
changed = true;
|
|
|
|
for ( size_t j=0; j < domain(i).size() && !changed; j++ ) {
|
|
if ( domain(i)[j] != oldDomains[i][j] )
|
|
changed = true;
|
|
}
|
|
}
|
|
} while (changed);
|
|
}
|
|
|