Hi Peter,
I solved that problem for Gecode 1.3.0 (still running for 3.*) by a
dedicated implementation of a Gecode RangeIterator for a std::set
(source attached). The source code can be easily adapted for your
purpose either by sorting the std::vector after filling or by ensuring
that you fill it with values of increasing order.
Dont know if there is a "native" Gecode support in 3.*, havent checked
since I wrote it. :)
the application is than quite simple:
////////////////////////////////////////////////////
std::set<int> data; // fill data
GC_StlSetRangeIterator dataIt(&data);
x.inter_r(*home, dataIt);
////////////////////////////////////////////////////
Hope it helps,
Martin
Peter Vanhee schrieb:
Hey all,
I have more or less the same problem as mentioned here:
http://thread.gmane.org/gmane.comp.lib.gecode.user/919,
however the solution seems to be outdated for gecode 3.x: e.g. GECODE_AUTOARRAY
is not existing anymore etc.
Within the binary propagator, and when one variable is assigned (x0), I need to filter values in the other variable (x1).
What I do right now is:
// loop over all values of x1 and push to remove if necessary
vector<int> remove;
for (IntVarValues i(*x1); i(); ++i) {
if (!predicate(home, x0->val(), i.val())) remove.push_back(i.val());
}
// remove values from domain
for(vector<int>::iterator i=remove.begin(); i!=remove.end(); ++i) {
GECODE_ME_CHECK(x1->nq(_home, r));
}
This is not at all efficient: 90% of the time is spent in
Int::IntVarImp::nq_full, and 38% in Int::IntVarImp::RangeList::min().
How can I change this?
I have variables with big domains (into the millions of values) that have few
continuous ranges.
Thanks,
Peter
--
Martin Mann, Dipl. Bioinf.
Bioinformatics - Inst. of Computer Science
Albert-Ludwigs-University Freiburg
Tel: ++49-761-203-8259
Fax: ++49-761-203-7462
http://www.bioinf.uni-freiburg.de/~mmann/
/*
* Main authors:
* Martin Mann http://www.bioinf.uni-freiburg.de/~mmann/
*
* Contributing authors:
* Sebastian Will http://www.bioinf.uni-freiburg.de/~will/
*
* Copyright:
* Martin Mann, 2007
*
* This file is part of the CPSP-tools package:
* http://www.bioinf.uni-freiburg.de/sw/cpsp/
*
* See the file "LICENSE" for information on usage and
* redistribution of this file, and for a
* DISCLAIMER OF ALL WARRANTIES.
*
*/
#ifndef GC_STLSETRANGEITERATOR_HH_
#define GC_STLSETRANGEITERATOR_HH_
#include <set>
#include <iostream>
/**
* Provides a constant Gecode RangeIterator of a std::set<int>
that
* calculates the ranges on demand.
*/
class GC_StlSetRangeIterator
{
private:
const std::set<int>* data;
std::set<int>::const_iterator actElem;
bool noFurtherRange;
int nextMin, nextMax;
//! searchs for the next range and sets the inner
members
void getNextRange();
public:
GC_StlSetRangeIterator();
GC_StlSetRangeIterator(const std::set<int>* data_);
virtual ~GC_StlSetRangeIterator();
void init(const std::set<int>* const data_) {
data = data_;
noFurtherRange = false;
if (data != NULL)
actElem = data->begin();
getNextRange();
}
bool operator()(void) const { return !noFurtherRange; }
void operator++(void) { getNextRange(); }
int min(void) const { return nextMin; }
int max(void) const { return nextMax; }
unsigned int width(void) { return nextMax-nextMin+1; }
};
#endif /*GC_STLSETRANGEITERATOR_HH_*/
/*
* Main authors:
* Martin Mann http://www.bioinf.uni-freiburg.de/~mmann/
*
* Contributing authors:
* Sebastian Will http://www.bioinf.uni-freiburg.de/~will/
*
* Copyright:
* Martin Mann, 2007
*
* This file is part of the CPSP-tools package:
* http://www.bioinf.uni-freiburg.de/sw/cpsp/
*
* See the file "LICENSE" for information on usage and
* redistribution of this file, and for a
* DISCLAIMER OF ALL WARRANTIES.
*
*/
#include "cpsp/GC_StlSetRangeIterator.hh"
GC_StlSetRangeIterator::GC_StlSetRangeIterator() :
data(NULL), noFurtherRange(true)
{
getNextRange();
}
GC_StlSetRangeIterator::GC_StlSetRangeIterator(const std::set<int>*
data_) :
data(data_), noFurtherRange(false)
{
if (data != NULL)
actElem = data->begin();
getNextRange();
}
GC_StlSetRangeIterator::~GC_StlSetRangeIterator()
{
}
void
GC_StlSetRangeIterator::getNextRange() {
if (data==NULL || actElem == data->end()) {
noFurtherRange = true;
return;
}
// find next range
nextMin = *actElem;
nextMax = nextMin;
// build up new upper bound until end of set reached or
gap in
// sequence
while ( (++actElem != data->end()) && (*actElem ==
(nextMax+1))) {
nextMax++;
}
}
_______________________________________________
Gecode users mailing list
[email protected]
https://www.gecode.org/mailman/listinfo/gecode-users
