diff options
Diffstat (limited to 'casa')
55 files changed, 4680 insertions, 0 deletions
diff --git a/casa/Main.C b/casa/Main.C new file mode 100644 index 0000000..63e7859 --- /dev/null +++ b/casa/Main.C @@ -0,0 +1,80 @@ +// Copyright 2008, 2009 Brady J. Garvin + +// This file is part of Covering Arrays by Simulated Annealing (CASA). + +// CASA is free software: you can redistribute it and/or modify it +// under the terms of the GNU General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. + +// CASA 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 General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with CASA. If not, see <http://www.gnu.org/licenses/>. + + +#include <cstdlib> +#include <ctime> +#include <iostream> +#include <sstream> + +#include "io/Usage.H" +#include "io/SpecificationFile.H" +#include "io/ConstraintFile.H" +#include "io/OutputFile.H" + +#include "covering/state/CoveringArray.H" + +#include "annealing/Anneal.H" + +using namespace std; + +int main(int argc, char**argv) { + // Absorb the command line arguments into shared variables. + parseOptions(argc, argv); + // Process the random seed. + if (!seeded) { + seed = time(NULL); + cout << "Choosing random seed " << seed << endl; + } + srand(seed); + // Process the specification file. + SpecificationFile specification(modelFile); + // Process the constraints file. + ConstraintFile constraints(constraintFile ? constraintFile : ""); + // ready the output file + ostringstream defaultOutputFile("anneal", ios::out | ios::app); + if (!outputFile) { + defaultOutputFile << '.' << seed; + defaultOutputFile << ".out"; + cout << "Using output filename " << defaultOutputFile.str() << endl; + } + OutputFile output(outputFile ? outputFile : defaultOutputFile.str()); + + // Start the core algorithm. + if (verbose) { + cout << "Passing control to primary algorithm" << endl; + } + CoveringArray solution = + anneal + (specification, + constraints, + iterations, + startingTemperature, + decrement); + if (verbose) { + cout << "Control returned from primary algorithm" << endl; + } + + // Store the results in the output file. + output.setCoveringArray(solution); + output.write(); + + if (verbose) { + cout << "Done" << endl; + } + return 0; +} diff --git a/casa/algorithms/BinarySearch.C b/casa/algorithms/BinarySearch.C new file mode 100644 index 0000000..4ee02bc --- /dev/null +++ b/casa/algorithms/BinarySearch.C @@ -0,0 +1,37 @@ +// Copyright 2008, 2009 Brady J. Garvin + +// This file is part of Covering Arrays by Simulated Annealing (CASA). + +// CASA is free software: you can redistribute it and/or modify it +// under the terms of the GNU General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. + +// CASA 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 General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with CASA. If not, see <http://www.gnu.org/licenses/>. + + +#include <cassert> +#include "algorithms/BinarySearch.H" + +unsigned BinarySearch::operator ()(unsigned offset, unsigned size) { + unsigned result = offset + size; + while (size) { + unsigned division = partitioner(offset, size); + assert(division - offset < size); + if (predicate(division)) { + size = division - offset; + result = division; + } else { + ++division; + size += offset - division; + offset = division; + } + } + return result; +} diff --git a/casa/algorithms/BinarySearch.H b/casa/algorithms/BinarySearch.H new file mode 100644 index 0000000..43d2e2d --- /dev/null +++ b/casa/algorithms/BinarySearch.H @@ -0,0 +1,49 @@ +// Copyright 2008, 2009 Brady J. Garvin + +// This file is part of Covering Arrays by Simulated Annealing (CASA). + +// CASA is free software: you can redistribute it and/or modify it +// under the terms of the GNU General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. + +// CASA 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 General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with CASA. If not, see <http://www.gnu.org/licenses/>. + + +#ifndef BINARY_SEARCH_H +#define BINARY_SEARCH_H + +class Partitioner { +public: + virtual ~Partitioner() {} + virtual unsigned operator ()(unsigned offset, unsigned size) = 0; +}; + +class ExpensiveUnaryPredicate { +public: + virtual ~ExpensiveUnaryPredicate() {} + virtual bool operator ()(unsigned index) const = 0; +}; + +class BinarySearch { +protected: + const ExpensiveUnaryPredicate& predicate; + Partitioner& partitioner; +public: + BinarySearch + (const ExpensiveUnaryPredicate&predicate, Partitioner&partitioner) : + predicate(predicate), + partitioner(partitioner) {} + virtual ~BinarySearch() {} + // Returns the smallest index for which the predicate returns true, using the + // partitioner to reduce the comparison cost. + unsigned operator ()(unsigned offset, unsigned size); +}; + +#endif diff --git a/casa/annealing/Anneal.C b/casa/annealing/Anneal.C new file mode 100644 index 0000000..b77e344 --- /dev/null +++ b/casa/annealing/Anneal.C @@ -0,0 +1,152 @@ +// Copyright 2008, 2009 Brady J. Garvin + +// This file is part of Covering Arrays by Simulated Annealing (CASA). + +// CASA is free software: you can redistribute it and/or modify it +// under the terms of the GNU General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. + +// CASA 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 General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with CASA. If not, see <http://www.gnu.org/licenses/>. + + +#include "io/Usage.H" + +#include "annealing/Anneal.H" +#include "annealing/Bounds.H" +#include "annealing/AnnealingSuccess.H" +#include "annealing/AnnealingPartitioner.H" + +#include "search/Search.H" +#include "search/StateGuide.H" + +#include "covering/space/SingleChangeSpace.H" +#include "covering/space/GraftSpace.H" +#include "covering/heuristic/CoveringArrayHeuristic.H" +#include "covering/goal/CoverageGoal.H" +#include "covering/filter/CoveringArrayAnnealingFilter.H" +#include "covering/report/IterationReport.H" + +#include "algorithms/BinarySearch.H" + +CoveringArray anneal + (const SpecificationFile&specification, + const ConstraintFile&constraints, + unsigned iterations, + double startingTemperature, + double decrement) { + std::cout << "Setting up annealing framework" << std::endl; + // Build and connect all of the pieces of the search. + // For simulated annealing: + SearchConfiguration configuration(false,true,1U,0U); +#ifdef WITHOUT_INNER + SingleChangeSpace space +#else + GraftSpace space +#endif + (specification.getStrength(), specification.getOptions()); + // Add the constraints. + { + SATSolver&solver = space.getSolver(); + const Array<InputClause>&clauses = constraints.getClauses(); + for (unsigned i = clauses.getSize(); i--;) { + solver.addClause(const_cast<InputClause&>(clauses[i])); + } + } + CoveringArrayHeuristic heuristic; + StateGuide<CoveringArray, CoverageCost>guide; + CoverageGoal goal(space.computeTargetCoverage()); + CoveringArrayAnnealingFilter filter(startingTemperature,decrement); + IterationReport iterationReport; + Search<CoveringArray, CoverageCost>search + (configuration, &space, &heuristic, &guide, &goal, &filter, true); + AnnealingPartitioner partitioner; + // Add the listeners. + { + // For cooling: + ((EventSource<SearchIteration>&)search).addListener(filter); + typedef EventSource<SearchFinish<CoveringArray, CoverageCost> > + FinishEventSourceT; + // Structure start states: + ((FinishEventSourceT&)search).addListener(space); + // Use search feedback to guide the outer search: + ((FinishEventSourceT&)search).addListener(partitioner); + // Give reports on iterations taken: + ((FinishEventSourceT&)search).addListener(iterationReport); + } + CoveringArray initialSolution + (0, + specification.getStrength(), + specification.getOptions(), + space.getSolver()); + + // Here we go... + std::cout << "Annealing" +#ifdef WITHOUT_INNER + << " (without t-set replacement)" +#endif +#ifdef WITHOUT_OUTER + << " (without extra outer search)" +#endif + << std::endl; + unsigned lower = + computeLowerBound(specification.getStrength(), specification.getOptions()); + unsigned upper = + computeUpperBound(specification.getStrength(), specification.getOptions()); + AnnealingSuccess annealingSuccess(search, iterations, initialSolution); + + std::cout << "Suspect that the optimum number of rows is in [" << lower << + ".." << upper << ']' << std::endl; + std::cout << "Starting binary search" << std::endl; + BinarySearch binarySearch(annealingSuccess, partitioner); + unsigned result = binarySearch(lower, upper + 1 - lower); + while (result > upper) { + upper <<= 1; + std::cout << "Trying more conservative upper bound " << upper << std::endl; + result = binarySearch(lower, upper + 1 - lower); + } +#ifndef WITHOUT_OUTER + do { + if (result == lower) { + if (lower > 5) { + lower -= 5; + } else { + --lower; + if (!lower) { + break; + } + } + std::cout << "Trying less conservative lower bound " << lower << + std::endl; + } + unsigned lastResult = result; + unsigned upped = 0; + do { + if (lastResult == result) { + iterations *= 2; + annealingSuccess.setIterations(iterations); + std::cout << "Upping iterations to " << iterations << std::endl; + ++upped; + } else { + upped = 0; + } + lastResult = result; + std::cout << "Restarting binary search with best result at " << + lastResult << " rows" << std::endl; + filter.setTemperature(startingTemperature); + result = binarySearch(lower, lastResult - lower); + } while ((result < lastResult || upped < retries) && result > lower); + } while (result == lower); +#endif + std::cout << "Giving up with best result at " << result << " rows" << + std::endl; + std::cout << "Total cost of computation: " << iterationReport.getTotal() << + " iteration(s)" << std::endl; + return annealingSuccess.getSolution(); +} diff --git a/casa/annealing/Anneal.H b/casa/annealing/Anneal.H new file mode 100644 index 0000000..8eaa6b1 --- /dev/null +++ b/casa/annealing/Anneal.H @@ -0,0 +1,33 @@ +// Copyright 2008, 2009 Brady J. Garvin + +// This file is part of Covering Arrays by Simulated Annealing (CASA). + +// CASA is free software: you can redistribute it and/or modify it +// under the terms of the GNU General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. + +// CASA 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 General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with CASA. If not, see <http://www.gnu.org/licenses/>. + +#ifndef ANNEAL_H +#define ANNEAL_H + +#include "io/SpecificationFile.H" +#include "io/ConstraintFile.H" + +#include "covering/state/CoveringArray.H" + +CoveringArray anneal + (const SpecificationFile&specification, + const ConstraintFile&constraints, + unsigned iterations, + double startingTemperature, + double decrement); + +#endif diff --git a/casa/annealing/AnnealingFilter.H b/casa/annealing/AnnealingFilter.H new file mode 100644 index 0000000..f787ae4 --- /dev/null +++ b/casa/annealing/AnnealingFilter.H @@ -0,0 +1,93 @@ +// Copyright 2008, 2009 Brady J. Garvin + +// This file is part of Covering Arrays by Simulated Annealing (CASA). + +// CASA is free software: you can redistribute it and/or modify it +// under the terms of the GNU General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. + +// CASA 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 General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with CASA. If not, see <http://www.gnu.org/licenses/>. + + +#ifndef ANNEALING_FILTER_H +#define ANNEALING_FILTER_H + +#include <cassert> +#include <iostream> + +#include "search/GreedyFilter.H" +#include "events/Listener.H" + +// Decides, according to the rules of simulated annealing, when to take good +// moves and when to take bad ones. + +// Should be added as a listener to search iterations in order that cooling be +// synchronized with the search. + +template<class STATE, class COST>class AnnealingFilter : + public GreedyFilter<STATE,COST>, + public Listener<SearchIteration> { + + typedef Heuristic<STATE,COST> HeuristicT; + typedef Goal<STATE> GoalT; + + double temperature; + const double decay; + +public: + AnnealingFilter(double temperature, double decay) : + temperature(temperature), + decay(decay) { + assert(0 <= decay); + assert(decay <= 1); + } + virtual ~AnnealingFilter() {} + + void setTemperature(double temperature) { + this->temperature = temperature; + } + + virtual double convertToDelta(COST childEstimate, COST parentEstimate) const + = 0; + + void signal(const SearchIteration&message) { + temperature *= decay; + } + + void operator() + (std::set<STATE>&children, + const STATE&parent, + const HeuristicT&heuristic, + const GoalT&goal) const { + GreedyFilter<STATE,COST>::operator()(children, heuristic, goal); + assert(children.size() <= 1); + if (children.size()) { + typename std::set<STATE>::iterator child = children.begin(); + COST childEstimate = heuristic.estimate(*child, goal); + COST parentEstimate = heuristic.estimate(parent, goal); + if (!(parentEstimate < childEstimate)) { + // Always take good moves. + return; + } + double delta = convertToDelta(childEstimate, parentEstimate); + double probability = exp(delta / temperature); + int boundary = (int)(probability * RAND_MAX); + if (rand() < boundary) { + // Sometimes take bad moves. + return; + } + children.clear(); + } + // When no moves are possible or a bad move is rejected, keep the parent. + children.insert(parent); + } +}; + +#endif diff --git a/casa/annealing/AnnealingPartitioner.C b/casa/annealing/AnnealingPartitioner.C new file mode 100644 index 0000000..396d193 --- /dev/null +++ b/casa/annealing/AnnealingPartitioner.C @@ -0,0 +1,58 @@ +// Copyright 2008, 2009 Brady J. Garvin + +// This file is part of Covering Arrays by Simulated Annealing (CASA). + +// CASA is free software: you can redistribute it and/or modify it +// under the terms of the GNU General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. + +// CASA 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 General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with CASA. If not, see <http://www.gnu.org/licenses/>. + + +#include "annealing/AnnealingPartitioner.H" +#include "io/Usage.H" + +using namespace std; + +unsigned AnnealingPartitioner::operator ()(unsigned offset, unsigned size) { + if (guess && guess - offset < size) { + return guess; + } + return offset + (unsigned)(searchPartition * size); +} + +void AnnealingPartitioner::signal + (const SearchFinish<CoveringArray, CoverageCost>&finish) { + set<const Node<CoveringArray, CoverageCost>*>best = finish.source.getBest(); + if (!best.size()) { + guess = 0; + return; + } + const CoveringArray&state = (*best.begin())->getState(); + assert(state.isTrackingNoncoverage()); + if (finish.results.size()) { + if (finish.iterations < 128) { + lastGuess = guess; + guess = 0; + } else { + unsigned ratio = finish.maxIterations / finish.iterations; + unsigned delta = guess - lastGuess; + lastGuess = guess; + if (delta > 0){ + for (guess = state.getRows(); ratio; --guess, ratio >>= 1); + } else { + for (guess = state.getRows() + delta; ratio; --guess, ratio >>= 2); + } + } + } else { + lastGuess = guess; + guess = state.getRows() + state.getNoncoverage().size() / 2; + } +} diff --git a/casa/annealing/AnnealingPartitioner.H b/casa/annealing/AnnealingPartitioner.H new file mode 100644 index 0000000..34fd564 --- /dev/null +++ b/casa/annealing/AnnealingPartitioner.H @@ -0,0 +1,43 @@ +// Copyright 2008, 2009 Brady J. Garvin + +// This file is part of Covering Arrays by Simulated Annealing (CASA). + +// CASA is free software: you can redistribute it and/or modify it +// under the terms of the GNU General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. + +// CASA 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 General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with CASA. If not, see <http://www.gnu.org/licenses/>. + + +#ifndef ANNEALING_PARTITIONER_H +#define ANNEALING_PARTITIONER_H + +#include "algorithms/BinarySearch.H" +#include "events/Listener.H" +#include "search/SearchFinish.H" + +#include "covering/state/CoveringArray.H" +#include "covering/cost/CoverageCost.H" + +class AnnealingPartitioner : + public Partitioner, + public Listener<SearchFinish<CoveringArray,CoverageCost> > { +protected: + unsigned guess; + unsigned lastGuess; +public: + AnnealingPartitioner() : + guess(0), + lastGuess(0) {} + unsigned operator ()(unsigned offset, unsigned size); + void signal(const SearchFinish<CoveringArray, CoverageCost>&finish); +}; + +#endif diff --git a/casa/annealing/AnnealingSuccess.C b/casa/annealing/AnnealingSuccess.C new file mode 100644 index 0000000..f7199f2 --- /dev/null +++ b/casa/annealing/AnnealingSuccess.C @@ -0,0 +1,47 @@ +// Copyright 2008, 2009 Brady J. Garvin + +// This file is part of Covering Arrays by Simulated Annealing (CASA). + +// CASA is free software: you can redistribute it and/or modify it +// under the terms of the GNU General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. + +// CASA 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 General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with CASA. If not, see <http://www.gnu.org/licenses/>. + + +#include <iostream> + +#include "covering/space/CoveringArraySpace.H" +#include "annealing/AnnealingSuccess.H" + +using namespace std; + +bool AnnealingSuccess::operator ()(unsigned rows) const { + bool result; + cout << "Trying " << rows << " rows" << endl; + const CoveringArraySpace*space = + dynamic_cast<const CoveringArraySpace*>(search.getSpace()); + assert(space); + cout << "Building start state" << endl; + CoveringArray startState = space->createStartState(rows); + search.addStartState(startState); + cout << "Searching" << endl; + set<NodeT*>solutions = search.search(iterations, false); + if (solutions.empty()) { + cout << "Failed to meet coverage with " << rows << " rows" << endl; + result = false; + } else { + cout << "Met coverage with " << rows << " rows" << endl; + result = true; + solution = (*solutions.begin())->getState(); + } + search.clear(); + return result; +} diff --git a/casa/annealing/AnnealingSuccess.H b/casa/annealing/AnnealingSuccess.H new file mode 100644 index 0000000..d108f2d --- /dev/null +++ b/casa/annealing/AnnealingSuccess.H @@ -0,0 +1,57 @@ +// Copyright 2008, 2009 Brady J. Garvin + +// This file is part of Covering Arrays by Simulated Annealing (CASA). + +// CASA is free software: you can redistribute it and/or modify it +// under the terms of the GNU General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. + +// CASA 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 General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with CASA. If not, see <http://www.gnu.org/licenses/>. + + +#ifndef ANNEALING_SUCCESS_H +#define ANNEALING_SUCCESS_H + +#include "algorithms/BinarySearch.H" +#include "search/Search.H" + +#include "covering/state/CoveringArray.H" +#include "covering/cost/CoverageCost.H" + +class AnnealingSuccess : public ExpensiveUnaryPredicate { +protected: + typedef Node<CoveringArray, CoverageCost> + NodeT; + + Search<CoveringArray, CoverageCost>& search; + unsigned iterations; + mutable CoveringArray solution; + +public: + AnnealingSuccess + (Search<CoveringArray, CoverageCost>&search, + unsigned iterations, + const CoveringArray&initialSolution) : + search(search), + iterations(iterations), + solution(initialSolution) {} + + bool operator ()(unsigned rows) const; + + void setIterations(unsigned iterations) { + this->iterations = iterations; + } + + const CoveringArray&getSolution() const { + return solution; + } +}; + +#endif diff --git a/casa/annealing/Bounds.C b/casa/annealing/Bounds.C new file mode 100644 index 0000000..8e087e9 --- /dev/null +++ b/casa/annealing/Bounds.C @@ -0,0 +1,66 @@ +// Copyright 2008, 2009 Brady J. Garvin + +// This file is part of Covering Arrays by Simulated Annealing (CASA). + +// CASA is free software: you can redistribute it and/or modify it +// under the terms of the GNU General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. + +// CASA 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 General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with CASA. If not, see <http://www.gnu.org/licenses/>. + + +#include <cmath> +#include <algorithm> +#include <functional> + +#include "annealing/Bounds.H" + +using namespace std; + +#ifndef UPPER_BOUND_SCALING_FACTOR +#define UPPER_BOUND_SCALING_FACTOR 5 +#endif + +unsigned computeLowerBound(unsigned strength, const Options&options) { + if (lowerBound) { + return lowerBound; + } + static greater<unsigned>backwards; + unsigned result = 1; + Array<unsigned>symbolCounts(options.getSize()); + for (unsigned i = symbolCounts.getSize(); i--;) { + symbolCounts[i] = options.getSymbolCount(i); + } + partial_sort + (symbolCounts + 0, + symbolCounts + strength, + symbolCounts + symbolCounts.getSize(), + backwards); + for (unsigned i = strength; i--;) { + result *= symbolCounts[i]; + } + return result; +} + +unsigned computeUpperBound(unsigned strength, const Options&options) { + if (upperBound) { + return upperBound; + } + unsigned max = 0; + Array<unsigned>symbolCounts(options.getSize()); + for (unsigned i = symbolCounts.getSize(); i--;) { + unsigned candidate = options.getSymbolCount(i); + if (candidate > max) { + max = candidate; + } + } + return (unsigned)(UPPER_BOUND_SCALING_FACTOR * + pow((double)max, (double)strength)); +} diff --git a/casa/annealing/Bounds.H b/casa/annealing/Bounds.H new file mode 100644 index 0000000..2062dfa --- /dev/null +++ b/casa/annealing/Bounds.H @@ -0,0 +1,28 @@ +// Copyright 2008, 2009 Brady J. Garvin + +// This file is part of Covering Arrays by Simulated Annealing (CASA). + +// CASA is free software: you can redistribute it and/or modify it +// under the terms of the GNU General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. + +// CASA 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 General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with CASA. If not, see <http://www.gnu.org/licenses/>. + + +#ifndef BOUNDS_H +#define BOUNDS_H + +#include "io/Usage.H" +#include "covering/bookkeeping/Options.H" + +unsigned computeLowerBound(unsigned strength, const Options&options); +unsigned computeUpperBound(unsigned strength, const Options&options); + +#endif diff --git a/casa/covering/bookkeeping/Coverage.H b/casa/covering/bookkeeping/Coverage.H new file mode 100644 index 0000000..c0ce2b3 --- /dev/null +++ b/casa/covering/bookkeeping/Coverage.H @@ -0,0 +1,313 @@ +// Copyright 2008, 2009 Brady J. Garvin + +// This file is part of Covering Arrays by Simulated Annealing (CASA). + +// CASA is free software: you can redistribute it and/or modify it +// under the terms of the GNU General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. + +// CASA 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 General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with CASA. If not, see <http://www.gnu.org/licenses/>. + + +#ifndef COVERAGE_H +#define COVERAGE_H + +#include "PascalTriangle.H" +#include "Combinadic.H" + +#include "SubstitutionArray.H" + +#include "covering/bookkeeping/Options.H" + +template<class T>class Coverage { +protected: + unsigned strength; + Options options; + // The offsets are indices into the contents array; entry offsets[i], where i + // is the combinadic encoding of a set of columns, is the beginning of the + // contents for that column set's t-sets. + Array<unsigned> offsets; + SubstitutionArray<T> contents; + +public: + Coverage(unsigned strength, Options options) : + strength(strength), + options(options), + offsets(triangle.nCr(options.getSize(), strength)) { + unsigned size = 0; + unsigned offsetIndex = 0; + for (Array<unsigned>columns = combinadic.begin(strength); + columns[strength - 1] < options.getSize(); + combinadic.next(columns)) { + unsigned blockSize = 1; + for (unsigned i = strength; i--;) { + blockSize *= options.getSymbolCount(columns[i]); + } + offsets[offsetIndex++] = size; + size += blockSize; + } + contents = Array<T>(size); + } + + Coverage(const Coverage©) : + strength(copy.strength), + options(copy.options), + offsets(copy.offsets), + contents(copy.contents) {} + +protected: + // The method encode, in its various forms, is responsible for converting a + // sorted t-set to an index into the contents array. + + // These hinted versions of encode are for when some information has already + // been computed. indexHint is the combinadic encoding of the set of columns; + // columnsHint is this set of columns in sorted order; firstsHint is an array + // of corresponding first symbols; and countsHint is an array of symbol counts + // for each column. + unsigned encode + (unsigned indexHint, + Array<unsigned>columnsHint, + Array<unsigned>firstsHint, + Array<unsigned>countsHint, + Array<unsigned>sortedCombination) const { + assert(sortedCombination.getSize() == strength); + assert(indexHint < offsets.getSize()); + unsigned offset = offsets[indexHint]; + unsigned index = 0; + for (unsigned i = strength; i--;) { + unsigned column = columnsHint[i]; + unsigned base = firstsHint[column]; + unsigned count = countsHint[column]; + index *= count; + index += sortedCombination[i] - base; + } + return offset + index; + } + + unsigned encode + (Array<unsigned>columnsHint, + Array<unsigned>firstsHint, + Array<unsigned>countsHint, + Array<unsigned>sortedCombination) const { + return encode + (combinadic.encode(columnsHint), + columnsHint, + firstsHint, + countsHint, + sortedCombination); + } + + unsigned encode(Array<unsigned>sortedCombination) const { + assert(sortedCombination.getSize() == strength); + Array<unsigned>columns(strength); + for (unsigned i = strength; i--;) { + columns[i] = options.getOption(sortedCombination[i]); + } + unsigned offsetIndex = combinadic.encode(columns); + assert(offsetIndex < offsets.getSize()); + unsigned offset = offsets[offsetIndex]; + unsigned index = 0; + for (unsigned i = strength; i--;) { + unsigned column = columns[i]; + unsigned base = options.getFirstSymbol(column); + unsigned count = options.getSymbolCount(column); + index *= count; + index += sortedCombination[i] - base; + } + return offset + index; + } + + // The method decode, of course, does the opposite of encode. + Array<unsigned>decode(unsigned encoding) const { + unsigned offsetIndex = offsets.getSize(); + while (offsets[--offsetIndex] > encoding); + unsigned index = encoding - offsets[offsetIndex]; + Array<unsigned>columns = combinadic.decode(offsetIndex, strength); + Array<unsigned>result(strength); + for (unsigned i = 0; i < strength; ++i) { + unsigned column = columns[i]; + unsigned base = options.getFirstSymbol(column); + unsigned count = options.getSymbolCount(column); + unsigned digit = index % count; + index -= digit; + index /= count; + result[i] = base + digit; + } + assert(encode(result) == encoding); + return result; + } + +public: + unsigned getStrength() const { + return strength; + } + const Options&getOptions() const { + return options; + } + + class Entry{ + protected: + Coverage& owner; + unsigned index; + public: + Entry(const Coverage&owner,unsigned index) : + owner(const_cast<Coverage&>(owner)), + index(index) {} + operator T() const { + return owner.contents[index]; + } + Entry&operator =(const T&value) { + owner.contents[index] = value; + return *this; + } + Entry&operator --() { + --owner.contents[index]; + return *this; + } + Entry&operator ++() { + ++owner.contents[index]; + return *this; + } + }; + + const Entry operator[](Array<unsigned>sortedCombination) const { + return Entry(*this, encode(sortedCombination)); + } + Entry operator [](Array<unsigned>sortedCombination) { + return Entry(*this, encode(sortedCombination)); + } + + // The methods named hintGet work like the [] operator with the aforementioned + // hints. + const Entry hintGet + (unsigned indexHint, + Array<unsigned>columnsHint, + Array<unsigned>firstsHint, + Array<unsigned>countsHint, + Array<unsigned>sortedCombination) const { + return Entry + (*this, + encode + (indexHint, columnsHint, firstsHint, countsHint, sortedCombination)); + } + + Entry hintGet + (unsigned indexHint, + Array<unsigned>columnsHint, + Array<unsigned>firstsHint, + Array<unsigned>countsHint, + Array<unsigned>sortedCombination) { + return Entry + (*this, + encode + (indexHint, columnsHint, firstsHint, countsHint, sortedCombination)); + } + + const Entry hintGet + (Array<unsigned>columnsHint, + Array<unsigned>firstsHint, + Array<unsigned>countsHint, + Array<unsigned>sortedCombination) const { + return Entry + (*this, + encode(columnsHint, firstsHint, countsHint, sortedCombination)); + } + + Entry hintGet + (Array<unsigned>columnsHint, + Array<unsigned>firstsHint, + Array<unsigned>countsHint, + Array<unsigned>sortedCombination) { + return Entry + (*this, + encode(columnsHint, firstsHint, countsHint, sortedCombination)); + } + + class iterator { + protected: + Coverage& owner; + unsigned index; + public: + iterator(Coverage&owner, unsigned index) : + owner(owner), + index(index) {} + const Entry operator *() const { + return Entry(owner, index); + } + Entry operator *() { + return Entry(owner, index); + } + iterator&operator ++() { + ++index; + return *this; + } + bool operator ==(const iterator&other) const { + return &owner == &other.owner && index == other.index; + } + bool operator !=(const iterator&other) const { + return &owner != &other.owner || index != other.index; + } + Array<unsigned>getCombination() const { + return owner.decode(index); + } + }; + + class const_iterator { + protected: + const Coverage& owner; + unsigned index; + public: + const_iterator(const Coverage&owner, unsigned index) : + owner(owner), + index(index) {} + const_iterator(const iterator©) : + owner(copy.owner), + index(copy.index) {} + const Entry operator *() const { + return Entry(owner, index); + } + const_iterator&operator ++() { + ++index; + return *this; + } + bool operator ==(const const_iterator&other) const { + return &owner == &other.owner && index == other.index; + } + bool operator != (const const_iterator&other) const { + return &owner != &other.owner || index != other.index; + } + Array<unsigned>getCombination() const { + return owner.decode(index); + } + }; + + iterator begin() { + return iterator(*this, 0); + } + const_iterator begin() const { + return const_iterator(*this, 0); + } + iterator end() { + return iterator(*this, contents.getSize()); + } + const_iterator end() const { + return const_iterator(*this, contents.getSize()); + } + + unsigned getSize() const { + return contents.getSize(); + } + + void fill(const T&filler) { + contents.fill(filler); + } +}; + +#endif diff --git a/casa/covering/bookkeeping/Options.C b/casa/covering/bookkeeping/Options.C new file mode 100644 index 0000000..cd3c911 --- /dev/null +++ b/casa/covering/bookkeeping/Options.C @@ -0,0 +1,102 @@ +// Copyright 2008, 2009 Brady J. Garvin + +// This file is part of Covering Arrays by Simulated Annealing (CASA). + +// CASA is free software: you can redistribute it and/or modify it +// under the terms of the GNU General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. + +// CASA 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 General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with CASA. If not, see <http://www.gnu.org/licenses/>. + + +#include "covering/bookkeeping/Options.H" + +Options::Options() : + cumulativeValueCounts(0), + owningOptions(0) {} + +Options::Options(Array<unsigned>values) : + cumulativeValueCounts(values.getSize()) { + unsigned cumulativeValueCount = 0; + for (unsigned i = 0; i < values.getSize(); ++i) { + cumulativeValueCount += values[i]; + cumulativeValueCounts[i] = cumulativeValueCount; + } + owningOptions = Array<unsigned>(cumulativeValueCount); + for (unsigned i = 0, j = 0; i < values.getSize(); ++i) { + for (unsigned k = values[i]; k--;) { + owningOptions[j++] = i; + } + } +} + +Options::Options(const Options©) : + cumulativeValueCounts(copy.cumulativeValueCounts), + owningOptions(copy.owningOptions) {} + +unsigned Options::getSize() const { + return cumulativeValueCounts.getSize(); +} + +unsigned Options::getFirstSymbol(unsigned option) const { + return option ? cumulativeValueCounts[option - 1] : 0; +} + +Array<unsigned>Options::getFirstSymbols() const { + unsigned size = cumulativeValueCounts.getSize(); + Array<unsigned>result(size); + for (unsigned i = size; i-- > 1;) { + result[i] = cumulativeValueCounts[i - 1]; + } + if (size) { + result[0] = 0; + } + return result; +} + +unsigned Options::getSymbolCount(unsigned option) const { + return option ? + (cumulativeValueCounts[option] - cumulativeValueCounts[option - 1]) : + cumulativeValueCounts[0]; +} + +Array<unsigned>Options::getSymbolCounts() const { + unsigned size = cumulativeValueCounts.getSize(); + Array<unsigned>result(size); + for (unsigned i = size; i-- > 1;) { + result[i] = cumulativeValueCounts[i] - cumulativeValueCounts[i - 1]; + } + if (size) { + result[0] = cumulativeValueCounts[0]; + } + return result; +} + +unsigned Options::getLastSymbol(unsigned option) const { + return cumulativeValueCounts[option] - 1; +} + +unsigned Options::getRandomSymbol(unsigned option) const { + return rand() % getSymbolCount(option) + getFirstSymbol(option); +} + +unsigned Options::getOtherRandomSymbol(unsigned option, unsigned exclude) + const { + unsigned count = getSymbolCount(option); + if (count == 1) { + return getFirstSymbol(option); + } + unsigned result = rand() % (count - 1) + getFirstSymbol(option); + return (result >= exclude) ? (result + 1) : result; +} + +unsigned Options::getOption(unsigned symbol) const { + return owningOptions[symbol]; +} diff --git a/casa/covering/bookkeeping/Options.H b/casa/covering/bookkeeping/Options.H new file mode 100644 index 0000000..ee047a4 --- /dev/null +++ b/casa/covering/bookkeeping/Options.H @@ -0,0 +1,50 @@ +// Copyright 2008, 2009 Brady J. Garvin + +// This file is part of Covering Arrays by Simulated Annealing (CASA). + +// CASA is free software: you can redistribute it and/or modify it +// under the terms of the GNU General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. + +// CASA 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 General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with CASA. If not, see <http://www.gnu.org/licenses/>. + + +#ifndef OPTIONS_H +#define OPTIONS_H + +#include <cstdlib> +#include <utility> + +#include "Array.H" + +class Options { +protected: + // The entry cumulativeValueCounts[i] is the number of values in options 0 + // through i, inclusive. + Array<unsigned> cumulativeValueCounts; + // The entry owningOptions[i] is the option that the value i belongs to. + Array<unsigned> owningOptions; + +public: + Options(); + Options(Array<unsigned>valueCounts); + Options(const Options©); + unsigned getSize() const; + unsigned getFirstSymbol(unsigned option) const; + Array<unsigned>getFirstSymbols() const; + unsigned getSymbolCount(unsigned option) const; + Array<unsigned>getSymbolCounts() const; + unsigned getLastSymbol(unsigned option) const; + unsigned getRandomSymbol(unsigned option) const; + unsigned getOtherRandomSymbol(unsigned option, unsigned exclude) const; + unsigned getOption(unsigned symbol) const; +}; + +#endif diff --git a/casa/covering/cost/CoverageCost.H b/casa/covering/cost/CoverageCost.H new file mode 100644 index 0000000..524a240 --- /dev/null +++ b/casa/covering/cost/CoverageCost.H @@ -0,0 +1,72 @@ +// Copyright 2008, 2009 Brady J. Garvin + +// This file is part of Covering Arrays by Simulated Annealing (CASA). + +// CASA is free software: you can redistribute it and/or modify it +// under the terms of the GNU General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. + +// CASA 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 General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with CASA. If not, see <http://www.gnu.org/licenses/>. + + +#ifndef COVERAGE_COST_H +#define COVERAGE_COST_H + +#include <cassert> + +class CoverageCost { +protected: + unsigned noncoverage; + unsigned multipleCoverage; + +public: + // So we can initialize an object from a literal zero: + CoverageCost(unsigned zero = 0) : + noncoverage(0), + multipleCoverage(0) { + assert(!zero); + } + CoverageCost(unsigned noncoverage, unsigned multipleCoverage) : + noncoverage(noncoverage), + multipleCoverage(multipleCoverage) {} + + unsigned getNoncoverage() const { + return noncoverage; + } + unsigned getMultipleCoverage() const { + return multipleCoverage; + } + + bool operator <(const CoverageCost&other) const { + if (noncoverage < other.noncoverage) { + return true; + } + if (noncoverage > other.noncoverage) { + return false; + } + return multipleCoverage < other.multipleCoverage; + } + bool operator <=(const CoverageCost&other) const { + if (noncoverage < other.noncoverage) { + return true; + } + if (noncoverage > other.noncoverage) { + return false; + } + return multipleCoverage <= other.multipleCoverage; + } + bool operator ==(const CoverageCost&other) const { + return + noncoverage == other.noncoverage && + multipleCoverage == other.multipleCoverage; + } +}; + +#endif diff --git a/casa/covering/filter/CoveringArrayAnnealingFilter.H b/casa/covering/filter/CoveringArrayAnnealingFilter.H new file mode 100644 index 0000000..f876e8f --- /dev/null +++ b/casa/covering/filter/CoveringArrayAnnealingFilter.H @@ -0,0 +1,49 @@ +// Copyright 2008, 2009 Brady J. Garvin + +// This file is part of Covering Arrays by Simulated Annealing (CASA). + +// CASA is free software: you can redistribute it and/or modify it +// under the terms of the GNU General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. + +// CASA 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 General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with CASA. If not, see <http://www.gnu.org/licenses/>. + + +#ifndef COVERING_ARRAY_ANNEALING_FILTER_H +#define COVERING_ARRAY_ANNEALING_FILTER_H + +#include "annealing/AnnealingFilter.H" + +#include "covering/state/CoveringArray.H" +#include "covering/cost/CoverageCost.H" + +#ifndef MULTIPLE_COVERAGE_WEIGHT +#define MULTIPLE_COVERAGE_WEIGHT 0.1L +#endif + +class CoveringArrayAnnealingFilter : + public AnnealingFilter<CoveringArray, CoverageCost> { +public: + CoveringArrayAnnealingFilter(double temperature, double decay) : + AnnealingFilter<CoveringArray, CoverageCost>(temperature, decay) {} + + double convertToDelta(CoverageCost childEstimate, CoverageCost parentEstimate) + const { + unsigned childNoncoverage = childEstimate.getNoncoverage(); + unsigned parentNoncoverage = parentEstimate.getNoncoverage(); + unsigned childMultipleCoverage = childEstimate.getMultipleCoverage(); + unsigned parentMultipleCoverage = parentEstimate.getMultipleCoverage(); + return -(double)(childNoncoverage - parentNoncoverage) - + MULTIPLE_COVERAGE_WEIGHT * + (childMultipleCoverage - parentMultipleCoverage); + } +}; + +#endif diff --git a/casa/covering/goal/CoverageGoal.H b/casa/covering/goal/CoverageGoal.H new file mode 100644 index 0000000..c4e0693 --- /dev/null +++ b/casa/covering/goal/CoverageGoal.H @@ -0,0 +1,43 @@ +// Copyright 2008, 2009 Brady J. Garvin + +// This file is part of Covering Arrays by Simulated Annealing (CASA). + +// CASA is free software: you can redistribute it and/or modify it +// under the terms of the GNU General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. + +// CASA 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 General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with CASA. If not, see <http://www.gnu.org/licenses/>. + + +#ifndef COVERAGE_GOAL_H +#define COVERAGE_GOAL_H + +#include "search/Goal.H" + +#include "covering/state/CoveringArray.H" + +class CoverageGoal : public Goal<CoveringArray> { +protected: + unsigned targetCoverage; +public: + CoverageGoal(unsigned targetCoverage) : + targetCoverage(targetCoverage) {} + + unsigned getTargetCoverage() { + return targetCoverage; + } + + bool isGoal(const CoveringArray&array) { + assert(array.getCoverageCount() <= targetCoverage); + return array.getCoverageCount() == targetCoverage; + } +}; + +#endif diff --git a/casa/covering/heuristic/CoveringArrayHeuristic.H b/casa/covering/heuristic/CoveringArrayHeuristic.H new file mode 100644 index 0000000..61214b8 --- /dev/null +++ b/casa/covering/heuristic/CoveringArrayHeuristic.H @@ -0,0 +1,37 @@ +// Copyright 2008, 2009 Brady J. Garvin + +// This file is part of Covering Arrays by Simulated Annealing (CASA). + +// CASA is free software: you can redistribute it and/or modify it +// under the terms of the GNU General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. + +// CASA 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 General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with CASA. If not, see <http://www.gnu.org/licenses/>. + + +#ifndef COVERING_ARRAY_HEURISTIC_H +#define COVERING_ARRAY_HEURISTIC_H + +#include "search/Heuristic.H" + +#include "covering/state/CoveringArray.H" +#include "covering/goal/CoverageGoal.H" + +class CoveringArrayHeuristic : public Heuristic<CoveringArray, CoverageCost> { + CoverageCost estimate + (const CoveringArray&state, const Goal<CoveringArray>&goal) const { + unsigned targetCoverage = ((CoverageGoal&)goal).getTargetCoverage(); + return CoverageCost + (targetCoverage - state.getCoverageCount(), + state.getMultipleCoverageCount()); + } +}; + +#endif diff --git a/casa/covering/report/IterationReport.H b/casa/covering/report/IterationReport.H new file mode 100644 index 0000000..7799b88 --- /dev/null +++ b/casa/covering/report/IterationReport.H @@ -0,0 +1,53 @@ +// Copyright 2008, 2009 Brady J. Garvin + +// This file is part of Covering Arrays by Simulated Annealing (CASA). + +// CASA is free software: you can redistribute it and/or modify it +// under the terms of the GNU General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. + +// CASA 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 General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with CASA. If not, see <http://www.gnu.org/licenses/>. + + +#ifndef ITERATION_REPORT_H +#define ITERATION_REPORT_H + +#include <iostream> + +class IterationReport : + public Listener<SearchFinish<CoveringArray, CoverageCost> > { +protected: + unsigned total; +public: + IterationReport() : + total(0) {} + void signal(const SearchFinish<CoveringArray, CoverageCost>&finish) { + std::set<const Node<CoveringArray, CoverageCost>*>best = + finish.source.getBest(); + if (best.size()) { + const CoveringArray&state = (*best.begin())->getState(); + assert(state.isTrackingNoncoverage()); + std::cout << "Search stopped after " << finish.iterations << '/' << + finish.maxIterations << " iteration(s) with " << + state.getNoncoverage().size() << " uncovered t-sets and " << + state.getMultipleCoverageCount() << " multicovered t-sets" << std::endl; + } else { + std::cout << "Search stopped after " << finish.iterations << '/' << + finish.maxIterations << " iteration(s) with no results" << std::endl; + } + total += finish.iterations; + std::cout << "Used " << total << " total iterations thus far" << std::endl; + } + unsigned getTotal() const { + return total; + } +}; + +#endif diff --git a/casa/covering/space/CoveringArraySpace.C b/casa/covering/space/CoveringArraySpace.C new file mode 100644 index 0000000..6287bd3 --- /dev/null +++ b/casa/covering/space/CoveringArraySpace.C @@ -0,0 +1,80 @@ +// Copyright 2008, 2009 Brady J. Garvin + +// This file is part of Covering Arrays by Simulated Annealing (CASA). + +// CASA is free software: you can redistribute it and/or modify it +// under the terms of the GNU General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. + +// CASA 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 General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with CASA. If not, see <http://www.gnu.org/licenses/>. + + +#include "covering/space/CoveringArraySpace.H" + +CoveringArraySpace::CoveringArraySpace(unsigned strength, Options options) : + strength(strength), options(options) { + assert(strength <= options.getSize()); + for (unsigned i = options.getSize(); i--;) { + // The clause atLeast requires that each column be filled. + InputClause atLeast; + for (unsigned + j = options.getFirstSymbol(i), + limit = options.getLastSymbol(i); + j <= limit; + ++j) { + atLeast.append(InputTerm(false, j)); + } + solver.addClause(atLeast); + // The clauses atMost require that each pairing of symbols from an option + // show at least one absence. + for (unsigned + j = options.getFirstSymbol(i), + limit = options.getLastSymbol(i); + j <= limit; ++j) { + for (unsigned k = j + 1; k <= limit; ++k) { + InputClause atMost; + atMost.append(InputTerm(true, j)); + atMost.append(InputTerm(true, k)); + solver.addClause(atMost); + } + } + } +} + +unsigned CoveringArraySpace::computeTargetCoverage() const { + unsigned result = 0; + for (Array<unsigned>columns = combinadic.begin(strength); + columns[strength - 1] < options.getSize(); + combinadic.next(columns)) { + // Initialization: + Array<InputTerm>combination(columns.getSize()); + for (unsigned i = columns.getSize(); i--;) { + combination[i] = InputTerm(false, options.getFirstSymbol(columns[i])); + } + // Body: + loop: + { + InputKnown known(combination); + if (solver(known)) { + ++result; + } + } + // Advance: + for (unsigned i = columns.getSize(); i--;) { + unsigned next = combination[i].getVariable() + 1; + if (next <= options.getLastSymbol(columns[i])) { + combination[i] = InputTerm(false, next); + goto loop; + } + combination[i] = InputTerm(false, options.getFirstSymbol(columns[i])); + } + } + return result; +} diff --git a/casa/covering/space/CoveringArraySpace.H b/casa/covering/space/CoveringArraySpace.H new file mode 100644 index 0000000..e4702a5 --- /dev/null +++ b/casa/covering/space/CoveringArraySpace.H @@ -0,0 +1,52 @@ +// Copyright 2008, 2009 Brady J. Garvin + +// This file is part of Covering Arrays by Simulated Annealing (CASA). + +// CASA is free software: you can redistribute it and/or modify it +// under the terms of the GNU General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. + +// CASA 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 General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with CASA. If not, see <http://www.gnu.org/licenses/>. + + +#ifndef COVERING_ARRAY_SPACE_H +#define COVERING_ARRAY_SPACE_H + +#include <cassert> + +#include "Array.H" + +#include "search/StateSpace.H" + +#include "covering/state/CoveringArray.H" +#include "covering/bookkeeping/Options.H" +#include "covering/cost/CoverageCost.H" + +#include "sat/SAT.H" + +class CoveringArraySpace : public StateSpace<CoveringArray, CoverageCost>{ +protected: + unsigned strength; + Options options; + mutable SATSolver solver; +public: + CoveringArraySpace(unsigned strength, Options options); + virtual ~CoveringArraySpace() {} + virtual CoveringArray createStartState(unsigned rows) const = 0; + SATSolver&getSolver() { + return solver; + } + const SATSolver&getSolver() const { + return solver; + } + unsigned computeTargetCoverage() const; +}; + +#endif diff --git a/casa/covering/space/GraftSpace.C b/casa/covering/space/GraftSpace.C new file mode 100644 index 0000000..daa84e0 --- /dev/null +++ b/casa/covering/space/GraftSpace.C @@ -0,0 +1,187 @@ +// Copyright 2008, 2009 Brady J. Garvin + +// This file is part of Covering Arrays by Simulated Annealing (CASA). + +// CASA is free software: you can redistribute it and/or modify it +// under the terms of the GNU General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. + +// CASA 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 General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with CASA. If not, see <http://www.gnu.org/licenses/>. + + +#include <algorithm> + +#include "utility/igreater.H" + +#include "covering/space/GraftSpace.H" + +using namespace std; + +#ifndef MAXIMUM_SUBROW_CHANGE_FAILED_ATTEMPTS +#define MAXIMUM_SUBROW_CHANGE_FAILED_ATTEMPTS 32 +#endif + +Array<unsigned>GraftSpace::createRandomMatchingRow(InputKnown&known) const { + Array<unsigned>result(options.getSize()); + for (unsigned i = options.getSize(); i--;) { + vector<unsigned>candidates; + for (unsigned + j = options.getSymbolCount(i), + base = options.getFirstSymbol(i); + j--;) { + candidates.push_back(base + j); + } + unsigned index = rand() % candidates.size(); + unsigned symbol = candidates[index]; + known.append(InputTerm(false, symbol)); + while (!solver(known)) { + known.undoAppend(); + candidates[index] = candidates[candidates.size() - 1]; + candidates.pop_back(); + index = rand() % candidates.size(); + symbol = candidates[index]; + known.append(InputTerm(false, symbol)); + } + result[i] = symbol; + } + return result; +} + +CoveringArray GraftSpace::createStartState(unsigned rows) const { + CoveringArray result(rows, strength, options, solver); + unsigned i = rows; + while (i-->resurrectionBuffer.size()) { + InputKnown known; + result.setBackingArrayRow(i, createRandomMatchingRow(known)); + } + if (resurrectionBuffer.size()) { + for (++i;i--;) { + Array<unsigned>row = resurrectionBuffer[i]; + // We must deep copy to preserve the resurrection buffer. + for (unsigned j = options.getSize(); j--;) { + result.setBackingArrayEntry(i, j, row[j]); + } + } + } + result.setTrackingCoverage(true); + result.setTrackingNoncoverage(true); + return result; +} + +CoverageCost GraftSpace::getTraveled(const CoveringArray&start) const { + return 0; +} + +CoverageCost GraftSpace::getTraveled + (const Node<CoveringArray, CoverageCost>&parent,const CoveringArray&state) + const { + return 0; +} + +set<CoveringArray>GraftSpace::getChildren + (const CoveringArray&state, float proportion) const { + assert(false); // Unimplemented. + return getChildren(state, (unsigned)1); +} + +set<CoveringArray>GraftSpace::getChildren + (const CoveringArray&state, unsigned count) const { + set<CoveringArray>result; + unsigned rows = state.getRows(); + assert(options.getSize() == state.getOptions()); + assert(state.isTrackingNoncoverage()); + const set<Array<unsigned>, ArrayComparator<unsigned> >&noncoverage = + state.getNoncoverage(); + if (noncoverage.empty()){ + return result; + } + unsigned attempts = 0; + for (unsigned i = count; i; ++attempts) { + unsigned row = rand() % rows; + set<Array<unsigned>, ArrayComparator<unsigned> >::const_iterator + combinationIterator = noncoverage.begin(); + unsigned combinationIndex = rand() % noncoverage.size(); + while (combinationIndex--) { + ++combinationIterator; + } + Array<unsigned>combination = *combinationIterator; + Array<unsigned>columns(strength); + InputKnown known; + if (attempts < MAXIMUM_SUBROW_CHANGE_FAILED_ATTEMPTS) { + for (unsigned j = strength; j--;) { + columns[j] = options.getOption(combination[j]); + } + for (unsigned j = options.getSize(), k = strength; j--;) { + if (k && columns[k-1] == j) { + unsigned symbol = combination[--k]; + known.append(InputTerm(false, symbol)); + } else { + assert(!k || columns[k - 1] < j); + unsigned symbol = state(row, j); + known.append(InputTerm(false, symbol)); + } + } + if (solver(known)) { + CoveringArray child = state; + child(row, columns) = combination; + result.insert(child); + --i; + attempts = 0; + } + } else { + cout << "Considering a full row change" << endl; + for (unsigned k = strength; k--;) { + known.append(InputTerm(false, combination[k])); + } + CoveringArray child = state; + child(row) = createRandomMatchingRow(known); + result.insert(child); + --i; + attempts = 0; + } + } + return result; +} + +void GraftSpace::signal(const SearchFinish<CoveringArray, CoverageCost>&finish) { + const set<const Node<CoveringArray, CoverageCost>*>&best = + finish.source.getBest(); + if (best.empty()) { + return; + } + const CoveringArray&solution = (*best.begin())->getState(); + unsigned rowCount = solution.getRows(); + unsigned optionCount = solution.getOptions(); + resurrectionBuffer.reserve(rowCount); + while (resurrectionBuffer.size() < rowCount) { + resurrectionBuffer.push_back(Array<unsigned>()); + } + cout << "Sorting rows for distinct coverage" << endl; + Array<unsigned>distinctCoverage = solution.countDistinctCoverage(); + Array<unsigned>permutation(rowCount); + for (unsigned i = rowCount; i--;) { + permutation[i] = i; + } + igreater<unsigned>betterDistinctCoverage(distinctCoverage); + sort(permutation + 0, permutation + rowCount, betterDistinctCoverage); + cout << "Saving rows in resurrection buffer" << endl; + for (unsigned i = rowCount; i--;) { + unsigned p = permutation[i]; + Array<unsigned>row = Array<unsigned>(optionCount); + for (unsigned j = optionCount; j--;) { + row[j] = solution(p, j); + } + resurrectionBuffer[i] = row; + } +} + +void GraftSpace::clearResurrectionBuffer() { + resurrectionBuffer.clear(); +} diff --git a/casa/covering/space/GraftSpace.H b/casa/covering/space/GraftSpace.H new file mode 100644 index 0000000..abd7b84 --- /dev/null +++ b/casa/covering/space/GraftSpace.H @@ -0,0 +1,60 @@ +// Copyright 2008, 2009 Brady J. Garvin + +// This file is part of Covering Arrays by Simulated Annealing (CASA). + +// CASA is free software: you can redistribute it and/or modify it +// under the terms of the GNU General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. + +// CASA 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 General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with CASA. If not, see <http://www.gnu.org/licenses/>. + + +#ifndef GRAFT_SPACE_H +#define GRAFT_SPACE_H + +#include <vector> +#include <iostream> + +#include "Array.H" + +#include "covering/space/CoveringArraySpace.H" +#include "covering/cost/CoverageCost.H" + +#include "events/Listener.H" +#include "search/SearchFinish.H" + +class GraftSpace : + public CoveringArraySpace, + public Listener<SearchFinish<CoveringArray, CoverageCost> > { +protected: + std::vector<Array<unsigned> > resurrectionBuffer; + +public: + GraftSpace(unsigned strength, Options options) : + CoveringArraySpace(strength, options) {} + +protected: + Array<unsigned>createRandomMatchingRow(InputKnown&known) const; + +public: + CoveringArray createStartState(unsigned rows) const; + CoverageCost getTraveled(const CoveringArray&start) const; + CoverageCost getTraveled + (const Node<CoveringArray, CoverageCost>&parent, const CoveringArray&state) + const; + std::set<CoveringArray>getChildren + (const CoveringArray&state, float proportion) const; + std::set<CoveringArray>getChildren + (const CoveringArray&state,unsigned count) const; + void signal(const SearchFinish<CoveringArray, CoverageCost>&finish); + void clearResurrectionBuffer(); +}; + +#endif diff --git a/casa/covering/space/SingleChangeSpace.C b/casa/covering/space/SingleChangeSpace.C new file mode 100644 index 0000000..96c4146 --- /dev/null +++ b/casa/covering/space/SingleChangeSpace.C @@ -0,0 +1,175 @@ +// Copyright 2008, 2009 Brady J. Garvin + +// This file is part of Covering Arrays by Simulated Annealing (CASA). + +// CASA is free software: you can redistribute it and/or modify it +// under the terms of the GNU General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. + +// CASA 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 General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with CASA. If not, see <http://www.gnu.org/licenses/>. + + +#include <iostream> +#include <algorithm> + +#include "utility/igreater.H" + +#include "covering/space/SingleChangeSpace.H" + +using namespace std; + +#ifndef MAXIMUM_SINGLE_CHANGE_FAILED_ATTEMPTS +#define MAXIMUM_SINGLE_CHANGE_FAILED_ATTEMPTS 32 +#endif + +Array<unsigned>SingleChangeSpace::createRandomMatchingRow + (InputKnown&known) const { + Array<unsigned>result(options.getSize()); + for (unsigned i = options.getSize(); i--;) { + vector<unsigned>candidates; + for (unsigned + j = options.getSymbolCount(i), + base = options.getFirstSymbol(i); + j--;) { + candidates.push_back(base + j); + } + unsigned index = rand() % candidates.size(); + unsigned symbol = candidates[index]; + known.append(InputTerm(false, symbol)); + while (!solver(known)) { + known.undoAppend(); + candidates[index] = candidates[candidates.size() - 1]; + candidates.pop_back(); + index = rand() % candidates.size(); + symbol = candidates[index]; + known.append(InputTerm(false, symbol)); + } + result[i] = symbol; + } + return result; +} + +CoveringArray SingleChangeSpace::createStartState(unsigned rows) const { + CoveringArray result(rows, strength, options, solver); + unsigned i = rows; + while (i-->resurrectionBuffer.size()) { + InputKnown known; + result.setBackingArrayRow(i, createRandomMatchingRow(known)); + } + if (resurrectionBuffer.size()) { + for (++i; i--;) { + Array<unsigned>row = resurrectionBuffer[i]; + // We must deep copy to preserve the resurrection buffer. + for (unsigned j = options.getSize(); j--;) { + result.setBackingArrayEntry(i, j, row[j]); + } + } + } + result.setTrackingCoverage(true); + result.setTrackingNoncoverage(true); + return result; +} + +CoverageCost SingleChangeSpace::getTraveled(const CoveringArray&start) const { + return 0; +} + +CoverageCost SingleChangeSpace::getTraveled + (const Node<CoveringArray, CoverageCost>&parent, const CoveringArray&state) + const { + return 0; +} + +set<CoveringArray>SingleChangeSpace::getChildren + (const CoveringArray&state, float proportion) const { + assert(false); // Unimplemented + return getChildren(state, (unsigned)1); +} + +set<CoveringArray>SingleChangeSpace::getChildren + (const CoveringArray&state, unsigned count) const { + set<CoveringArray>result; + unsigned rows = state.getRows(); + assert(options.getSize() == state.getOptions()); + assert(state.isTrackingNoncoverage()); + const set<Array<unsigned>, ArrayComparator<unsigned> >&noncoverage = + state.getNoncoverage(); + if (noncoverage.empty()) { + return result; + } + unsigned attempts = 0; + for (unsigned i = count; i; ++attempts) { + unsigned row = rand() % rows; + unsigned option = rand() % options.getSize(); + unsigned value = options.getOtherRandomSymbol(option, state(row, option)); + InputKnown known; + known.append(InputTerm(false, value)); + if (attempts < MAXIMUM_SINGLE_CHANGE_FAILED_ATTEMPTS) { + for (unsigned j = 0; j < option; ++j) { + known.append(InputTerm(false, state(row, j))); + } + for (unsigned j = option + 1; j < options.getSize(); ++j) { + known.append(InputTerm(false, state(row, j))); + } + if (solver(known)) { + CoveringArray child = state; + child(row, option) = value; + result.insert(child); + --i; + attempts = 0; + } + } else { + cout << "Considering a full row change" << endl; + CoveringArray child = state; + child(row) = createRandomMatchingRow(known); + result.insert(child); + --i; + attempts = 0; + } + } + return result; +} + +void SingleChangeSpace::signal + (const SearchFinish<CoveringArray, CoverageCost>&finish) { + const set<const Node<CoveringArray, CoverageCost>*>&best = + finish.source.getBest(); + if (best.empty()) { + return; + } + const CoveringArray&solution = (*best.begin())->getState(); + unsigned rowCount = solution.getRows(); + unsigned optionCount = solution.getOptions(); + resurrectionBuffer.reserve(rowCount); + while (resurrectionBuffer.size() < rowCount) { + resurrectionBuffer.push_back(Array<unsigned>()); + } + cout << "Sorting rows for distinct coverage" << endl; + Array<unsigned>distinctCoverage = solution.countDistinctCoverage(); + Array<unsigned>permutation(rowCount); + for (unsigned i = rowCount; i--;) { + permutation[i] = i; + } + igreater<unsigned>betterDistinctCoverage(distinctCoverage); + sort(permutation + 0, permutation + rowCount, betterDistinctCoverage); + cout << "Saving rows in resurrection buffer" << endl; + for (unsigned i = rowCount; i--;) { + unsigned p = permutation[i]; + Array<unsigned>row(optionCount); + for (unsigned j = optionCount; j--;) { + row[j] = solution(p,j); + } + resurrectionBuffer[i] = row; + } +} + +void SingleChangeSpace::clearResurrectionBuffer() { + resurrectionBuffer.clear(); +} diff --git a/casa/covering/space/SingleChangeSpace.H b/casa/covering/space/SingleChangeSpace.H new file mode 100644 index 0000000..66efbc3 --- /dev/null +++ b/casa/covering/space/SingleChangeSpace.H @@ -0,0 +1,61 @@ +// Copyright 2008, 2009 Brady J. Garvin + +// This file is part of Covering Arrays by Simulated Annealing (CASA). + +// CASA is free software: you can redistribute it and/or modify it +// under the terms of the GNU General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. + +// CASA 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 General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with CASA. If not, see <http://www.gnu.org/licenses/>. + + +#ifndef SINGLE_CHANGE_SPACE_H +#define SINGLE_CHANGE_SPACE_H + +#include <cstdlib> +#include <cassert> +#include <vector> + +#include "Array.H" + +#include "covering/space/CoveringArraySpace.H" +#include "covering/cost/CoverageCost.H" + +#include "events/Listener.H" +#include "search/SearchFinish.H" + +class SingleChangeSpace : + public CoveringArraySpace, + public Listener<SearchFinish<CoveringArray, CoverageCost> > { +protected: + std::vector<Array<unsigned> > resurrectionBuffer; + +public: + SingleChangeSpace(unsigned strength, Options options) : + CoveringArraySpace(strength, options) {} + +protected: + Array<unsigned>createRandomMatchingRow(InputKnown&known) const; + +public: + CoveringArray createStartState(unsigned rows) const; + CoverageCost getTraveled(const CoveringArray&start) const; + CoverageCost getTraveled + (const Node<CoveringArray, CoverageCost>&parent, + const CoveringArray&state) const; + std::set<CoveringArray>getChildren + (const CoveringArray&state, float proportion) const; + std::set<CoveringArray>getChildren + (const CoveringArray&state, unsigned count) const; + void signal(const SearchFinish<CoveringArray, CoverageCost>&finish); + void clearResurrectionBuffer(); +}; + +#endif diff --git a/casa/covering/state/CoveringArray.C b/casa/covering/state/CoveringArray.C new file mode 100644 index 0000000..e5aca80 --- /dev/null +++ b/casa/covering/state/CoveringArray.C @@ -0,0 +1,274 @@ +// Copyright 2008, 2009 Brady J. Garvin + +// This file is part of Covering Arrays by Simulated Annealing (CASA). + +// CASA is free software: you can redistribute it and/or modify it +// under the terms of the GNU General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. + +// CASA 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 General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with CASA. If not, see <http://www.gnu.org/licenses/>. + + +#include "covering/state/CoveringArray.H" + +using namespace std; + +#ifndef MAXIMUM_COVERING_ARRAY_SUBSTITUTION +#define MAXIMUM_COVERING_ARRAY_SUBSTITUTION 0x40 +#endif + +CoveringArray::CoveringArray + (unsigned rows, unsigned strength, Options options, SATSolver&solver) : + array(rows), + substitutions(new map<pair<unsigned, unsigned>, unsigned>()), + solver(&solver), + trackingCoverage(false), + trackingNoncoverage(false), + coverageCount(0), + multipleCoverageCount(0), + coverage(strength, options), + noncoverage(new set<Array<unsigned>, ArrayComparator<unsigned> >()) { + for (unsigned i = rows; i--;) { + array[i] = Array<unsigned>(options.getSize()); + } + coverage.fill(0); +} + +CoveringArray::CoveringArray(const CoveringArray©) : + array(copy.array), + substitutions(copy.substitutions), + solver(copy.solver), + trackingCoverage(copy.trackingCoverage), + trackingNoncoverage(copy.trackingNoncoverage), + coverageCount(copy.coverageCount), + multipleCoverageCount(copy.multipleCoverageCount), + coverage(copy.coverage), + noncoverage(copy.noncoverage) { + assert(array); +} + +void CoveringArray::setBackingArrayEntry + (unsigned row, unsigned option, unsigned value) { + assert(!substitutions->size()); + array[row][option] = value; +} + +void CoveringArray::setBackingArrayRow(unsigned row, Array<unsigned>value) { + assert(!substitutions->size()); + array[row] = value; +} + +unsigned CoveringArray::getCoverageCount() const { + return coverageCount; +} + +unsigned CoveringArray::getMultipleCoverageCount() const { + return multipleCoverageCount; +} + +Array<unsigned>CoveringArray::countDistinctCoverage() const { + assert(trackingCoverage); + Array<unsigned>result(array.getSize()); + result.fill(0); + unsigned strength = coverage.getStrength(); + unsigned limit = coverage.getOptions().getSize(); + Array<unsigned>firsts = coverage.getOptions().getFirstSymbols(); + Array<unsigned>counts = coverage.getOptions().getSymbolCounts(); + unsigned hint = 0; + for (Array<unsigned> + columns = combinadic.begin(strength), + symbols(strength); + columns[strength - 1]<limit; + combinadic.next(columns), ++hint) { + for (unsigned i = array.getSize(); i--;) { + for (unsigned j = strength; j--;) { + symbols[j] = (*this)(i, columns[j]); + } + if (coverage.hintGet(hint, columns, firsts, counts, symbols) == 1) { + ++result[i]; + } + } + } + return result; +} + +bool CoveringArray::operator <(const CoveringArray&other) const { + return this < &other; +} +bool CoveringArray::operator >(const CoveringArray&other) const { + return this > &other; +} +bool CoveringArray::operator ==(const CoveringArray&other) const { + return this == &other; +} +bool CoveringArray::operator !=(const CoveringArray&other) const { + return this != &other; +} + +void CoveringArray::finalizeSubstitutions() { + unsigned outer = getRows(); + unsigned inner = getOptions(); + Array<Array<unsigned> >replacement(outer); + for (unsigned i = outer; i--;) { + replacement[i] = Array<unsigned>(inner); + for (unsigned j = inner; j--;) { + replacement[i][j] = array[i][j]; + } + } + for (map<pair<unsigned, unsigned>, unsigned>::const_iterator + iterator = substitutions->begin(), + end = substitutions->end(); + iterator != end; + ++iterator) { + const pair<unsigned, unsigned>&location = iterator->first; + replacement[location.first][location.second] = iterator->second; + } + substitutions->clear(); + array = replacement; +} + +void CoveringArray::autoFinalizeSubstitutions() { + if (substitutions->size() > MAXIMUM_COVERING_ARRAY_SUBSTITUTION) { + finalizeSubstitutions(); + } +} + +bool CoveringArray::isTrackingCoverage() const { + return trackingCoverage; +} + +void CoveringArray::setTrackingCoverage(bool trackingCoverage) { + if (this->trackingCoverage) { + this->trackingCoverage = trackingCoverage; + return; + } + this->trackingCoverage = trackingCoverage; + if (trackingCoverage) { + unsigned strength = coverage.getStrength(); + unsigned limit = coverage.getOptions().getSize(); + Array<unsigned>firsts = coverage.getOptions().getFirstSymbols(); + Array<unsigned>counts = coverage.getOptions().getSymbolCounts(); + coverage.fill(0); + coverageCount = 0; + multipleCoverageCount = 0; + if (substitutions->size()) { + unsigned hint = 0; + for (Array<unsigned> + columns = combinadic.begin(strength), + symbols(strength); + columns[strength - 1] < limit; + combinadic.next(columns), ++hint) { + for (unsigned i = array.getSize();i--;) { + for (unsigned j = strength;j--;) { + symbols[j] = (*this)(i, columns[j]); + } + unsigned newCoverage = + ++coverage.hintGet(hint, columns, firsts, counts, symbols); + if (newCoverage == 1) { + ++coverageCount; + } + if (newCoverage>1) { + ++multipleCoverageCount; + } + } + } + } else { + // A special common case where we can bypass the () operator: + unsigned hint = 0; + for (Array<unsigned> + columns = combinadic.begin(strength), + symbols(strength); + columns[strength - 1] < limit; + combinadic.next(columns), ++hint) { + for (unsigned i = array.getSize(); i--;) { + for (unsigned j = strength; j--;) { + symbols[j] = array[i][columns[j]]; + } + unsigned newCoverage = + ++coverage.hintGet(hint, columns, firsts, counts, symbols); + if (newCoverage == 1) { + ++coverageCount; + } + if (newCoverage>1) { + ++multipleCoverageCount; + } + } + } + } + } +} + +bool CoveringArray::isTrackingNoncoverage() const { + return trackingNoncoverage; +} + +void CoveringArray::setTrackingNoncoverage(bool trackingNoncoverage) { + if (this->trackingNoncoverage) { + this->trackingNoncoverage = trackingNoncoverage; + if (!trackingNoncoverage) { + noncoverage->clear(); + } + return; + } + this->trackingNoncoverage = trackingNoncoverage; + if (trackingNoncoverage) { + assert(trackingCoverage); + assert(noncoverage->empty()); +#ifndef NDEBUG + unsigned impossible = 0; +#endif + for (Coverage<unsigned>::iterator + iterator = coverage.begin(), + end = coverage.end(); + iterator != end; + ++iterator) { + if (!*iterator) { + InputKnown known; + Array<unsigned>combination = iterator.getCombination(); + for (unsigned i = combination.getSize(); i--;) { + known.append(InputTerm(false, combination[i])); + } + if ((*solver)(known)) { + noncoverage->insert(combination); + } +#ifndef NDEBUG + else { + ++impossible; + } +#endif + } + } + assert(coverageCount + noncoverage->size() + impossible == + coverage.getSize()); + } +} + +const set<Array<unsigned>, ArrayComparator<unsigned> >& + CoveringArray::getNoncoverage() const { + return *noncoverage; +} + +ostream&operator <<(ostream&out, const CoveringArray&array) { + out << '{'; + for (unsigned i = 0; i < array.getRows(); ++i) { + out << '['; + for (unsigned j = 0; j < array.getOptions(); ++j) { + out << array(i,j) << ','; + } + out << "X],"; + } + out << "X} -> "; + if (array.isTrackingCoverage()) { + out << array.getCoverageCount(); + }else{ + out << '?'; + } + return out; +} diff --git a/casa/covering/state/CoveringArray.H b/casa/covering/state/CoveringArray.H new file mode 100644 index 0000000..6241230 --- /dev/null +++ b/casa/covering/state/CoveringArray.H @@ -0,0 +1,166 @@ +// Copyright 2008, 2009 Brady J. Garvin + +// This file is part of Covering Arrays by Simulated Annealing (CASA). + +// CASA is free software: you can redistribute it and/or modify it +// under the terms of the GNU General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. + +// CASA 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 General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with CASA. If not, see <http://www.gnu.org/licenses/>. + + +#ifndef COVERING_ARRAY_H +#define COVERING_ARRAY_H + +#include <cassert> +#include <iostream> +#include <set> +#include <map> + +#include "Lazy.H" +#include "Array.H" + +#include "covering/bookkeeping/Coverage.H" + +#include "sat/SAT.H" + + +class CoveringArray { +protected: + // The first index is the test configuration (row). + // The second index is the option (column). + Array<Array<unsigned> > array; + Lazy<std::map<std::pair<unsigned, unsigned>, unsigned> > + substitutions; + + SATSolver* solver; + + bool trackingCoverage; + bool trackingNoncoverage; + + unsigned coverageCount; + unsigned multipleCoverageCount; + Coverage<unsigned> coverage; + Lazy<std::set<Array<unsigned>, ArrayComparator<unsigned> > > + noncoverage; + +public: + CoveringArray + (unsigned rows, unsigned strength, Options options, SATSolver&solver); + CoveringArray(const CoveringArray©); + + unsigned getRows() const { + return array.getSize(); + } + unsigned getOptions() const { + return array.getSize() ? array[0].getSize() : 0; + } + + void setBackingArrayEntry(unsigned row, unsigned option, unsigned value); + void setBackingArrayRow(unsigned row, Array<unsigned>value); + + class Entry { + protected: + CoveringArray& owner; + unsigned row; + unsigned option; + public: + Entry(CoveringArray&owner, unsigned row, unsigned option) : + owner(owner), + row(row), + option(option) {} + protected: + void updateTracking(unsigned value); + public: + operator unsigned() const; + Entry&operator =(unsigned value); + }; + + // Warning: CoveringArray::Row assumes that constraints are always satisfied. + class Row { + protected: + CoveringArray& owner; + unsigned row; + public: + Row(CoveringArray&owner, unsigned row) : + owner(owner), + row(row) {} + protected: + void updateTracking(const Array<unsigned>values); + public: + operator Array<unsigned>() const; + Row&operator =(const Array<unsigned>values); + }; + + // Warning: CoveringArray::SubRow assumes that constraints are always + // satisfied. + class SubRow { + protected: + CoveringArray& owner; + unsigned row; + Array<unsigned> columns; + public: + SubRow(CoveringArray&owner, unsigned row, Array<unsigned>columns) : + owner(owner), + row(row), + columns(columns) {} + protected: + void updateTracking(const Array<unsigned>values); + public: + operator Array<unsigned>() const; + SubRow&operator =(const Array<unsigned>values); + }; + + Entry operator ()(unsigned row, unsigned option) { + return Entry(*this, row, option); + } + const Entry operator ()(unsigned row, unsigned option) const { + return Entry(*const_cast<CoveringArray*>(this), row, option); + } + + Row operator ()(unsigned row) { + return Row(*this, row); + } + const Row operator ()(unsigned row) const { + return Row(*const_cast<CoveringArray*>(this), row); + } + + SubRow operator ()(unsigned row, Array<unsigned>columns) { + return SubRow(*this, row, columns); + } + const SubRow operator ()(unsigned row, Array<unsigned>columns) const { + return SubRow(*const_cast<CoveringArray*>(this), row, columns); + } + + unsigned getCoverageCount() const; + unsigned getMultipleCoverageCount() const; + Array<unsigned>countDistinctCoverage() const; + + bool operator <(const CoveringArray&other) const; + bool operator >(const CoveringArray&other) const; + bool operator ==(const CoveringArray&other) const; + bool operator !=(const CoveringArray&other) const; + + void finalizeSubstitutions(); + void autoFinalizeSubstitutions(); + + bool isTrackingCoverage() const; + void setTrackingCoverage(bool trackingCoverage); + + bool isTrackingNoncoverage() const; + void setTrackingNoncoverage(bool trackingNoncoverage); + + const std::set<Array<unsigned>, ArrayComparator<unsigned> >&getNoncoverage() + const; +}; + +std::ostream&operator <<(std::ostream&out,const CoveringArray&array); + +#endif diff --git a/casa/covering/state/CoveringArrayEntry.C b/casa/covering/state/CoveringArrayEntry.C new file mode 100644 index 0000000..73e6e24 --- /dev/null +++ b/casa/covering/state/CoveringArrayEntry.C @@ -0,0 +1,102 @@ +// Copyright 2008, 2009 Brady J. Garvin + +// This file is part of Covering Arrays by Simulated Annealing (CASA). + +// CASA is free software: you can redistribute it and/or modify it +// under the terms of the GNU General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. + +// CASA 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 General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with CASA. If not, see <http://www.gnu.org/licenses/>. + + +#include "covering/state/CoveringArray.H" + +using namespace std; + +void CoveringArray::Entry::updateTracking(unsigned value) { + if (owner(row,option) == value) { + return; + } + unsigned strength = owner.coverage.getStrength(); + unsigned limit = owner.coverage.getOptions().getSize(); + Array<unsigned>firsts = owner.coverage.getOptions().getFirstSymbols(); + Array<unsigned>counts = owner.coverage.getOptions().getSymbolCounts(); + unsigned hint = 0; + for (Array<unsigned> + columns = combinadic.begin(strength), + symbols(strength); + columns[strength - 1] < limit; + combinadic.next(columns), ++hint) { + for (unsigned i = strength; i--;) { + if (columns[i] == option) { + for (unsigned j = strength; j--;) { + symbols[j] = owner(row, columns[j]); + } + InputKnown oldKnown(symbols); + if ((*owner.solver)(oldKnown) && + --owner.coverage.hintGet(hint, columns, firsts, counts, symbols) == + 0) { + --owner.coverageCount; + if (owner.trackingNoncoverage) { + Array<unsigned>separateCopyOfSymbols(symbols.getSize()); + for (unsigned j = symbols.getSize(); j--;) { + separateCopyOfSymbols[j] = symbols[j]; + } + bool successfulInsertion = + owner.noncoverage->insert(separateCopyOfSymbols).second; + assert(successfulInsertion); + (void)successfulInsertion; // This is unused without assertions. + } + } else { + --owner.multipleCoverageCount; + } + symbols[i] = value; + InputKnown newKnown(symbols); + if ((*owner.solver)(newKnown) && + ++owner.coverage.hintGet(hint, columns, firsts, counts, symbols) == + 1) { + ++owner.coverageCount; + if (owner.trackingNoncoverage) { + Array<unsigned>separateCopyOfSymbols(symbols.getSize()); + for (unsigned j = symbols.getSize(); j--;) { + separateCopyOfSymbols[j] = symbols[j]; + } + bool successfulErasure = + (bool)owner.noncoverage->erase(separateCopyOfSymbols); + assert(successfulErasure); + (void)successfulErasure; // This is unused without assertions. + } + } else { + ++owner.multipleCoverageCount; + } + break; + } + } + } + owner.autoFinalizeSubstitutions(); +} + +CoveringArray::Entry::operator unsigned() const { + map<pair<unsigned, unsigned>, unsigned>::const_iterator + substitution = + owner.substitutions->find(pair<unsigned, unsigned>(row,option)), + end = owner.substitutions->end(); + return (substitution == end) ? + owner.array[row][option] : + substitution->second; +} + +CoveringArray::Entry&CoveringArray::Entry::operator =(unsigned value) { + if (owner.trackingCoverage) { + updateTracking(value); + } + (*owner.substitutions)[pair<unsigned, unsigned>(row, option)] = value; + return *this; +} diff --git a/casa/covering/state/CoveringArrayRow.C b/casa/covering/state/CoveringArrayRow.C new file mode 100644 index 0000000..10f0a45 --- /dev/null +++ b/casa/covering/state/CoveringArrayRow.C @@ -0,0 +1,113 @@ +// Copyright 2008, 2009 Brady J. Garvin + +// This file is part of Covering Arrays by Simulated Annealing (CASA). + +// CASA is free software: you can redistribute it and/or modify it +// under the terms of the GNU General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. + +// CASA 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 General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with CASA. If not, see <http://www.gnu.org/licenses/>. + + +#include "covering/state/CoveringArray.H" + +using namespace std; + +void CoveringArray::Row::updateTracking(const Array<unsigned>values) { + unsigned size = values.getSize(); + assert(size == owner.getOptions()); + unsigned strength = owner.coverage.getStrength(); + unsigned limit = owner.coverage.getOptions().getSize(); + Array<unsigned>oldRow(size); + for (unsigned i = size; i--;) { + oldRow[i] = owner(row, i); + } + Array<unsigned>firsts = owner.coverage.getOptions().getFirstSymbols(); + Array<unsigned>counts = owner.coverage.getOptions().getSymbolCounts(); + unsigned hint = 0; + for (Array<unsigned> + columns = combinadic.begin(strength), + oldSymbols(strength), + newSymbols(strength); + columns[strength - 1] < limit; + combinadic.next(columns), ++hint) { + bool unchanged = true; + for (unsigned j = strength; j--;) { + unsigned column = columns[j]; + oldSymbols[j] = oldRow[column]; + newSymbols[j] = values[column]; + if (oldSymbols[j] != newSymbols[j]) { + unchanged = false; + } + } + if (unchanged) { + continue; + } + InputKnown oldKnown(oldSymbols); + InputKnown newKnown(newSymbols); + if (--owner.coverage.hintGet(hint, columns, firsts, counts, oldSymbols) == + 0) { + --owner.coverageCount; + if (owner.trackingNoncoverage) { + Array<unsigned>separateCopyOfSymbols(oldSymbols.getSize()); + for (unsigned j = oldSymbols.getSize(); j--;) { + separateCopyOfSymbols[j] = oldSymbols[j]; + } + bool successfulInsertion = + owner.noncoverage->insert(separateCopyOfSymbols).second; + assert(successfulInsertion); + (void)successfulInsertion; //This is unused without assertions. + } + } else { + --owner.multipleCoverageCount; + } + if (++owner.coverage.hintGet(hint, columns, firsts, counts, newSymbols) == + 1) { + ++owner.coverageCount; + if (owner.trackingNoncoverage) { + Array<unsigned>separateCopyOfSymbols(newSymbols.getSize()); + for (unsigned j = newSymbols.getSize(); j--;) { + separateCopyOfSymbols[j] = newSymbols[j]; + } + bool successfulErasure = + (bool)owner.noncoverage->erase(separateCopyOfSymbols); + assert(successfulErasure); + (void)successfulErasure; // This is unused without assertions. + } + } else { + ++owner.multipleCoverageCount; + } + } + owner.autoFinalizeSubstitutions(); +} + +CoveringArray::Row::operator Array<unsigned>() const { + typedef map<pair<unsigned,unsigned>,unsigned>::const_iterator Substitution; + Substitution end = owner.substitutions->end(); + Array<unsigned>result(owner.getOptions()); + for (pair<unsigned, unsigned>key(row, result.getSize()); key.second--;) { + Substitution substitution = owner.substitutions->find(key); + result[key.second] = + (substitution == end) ? + owner.array[row][key.second] : + substitution->second; + } + return result; +} + +CoveringArray::Row&CoveringArray::Row::operator =(const Array<unsigned>values) { + if (owner.trackingCoverage) { + updateTracking(values); + } + for (pair<unsigned, unsigned>key(row, owner.getOptions()); key.second--;) { + (*owner.substitutions)[key] = values[key.second]; + } + return *this; +} diff --git a/casa/covering/state/CoveringArraySubRow.C b/casa/covering/state/CoveringArraySubRow.C new file mode 100644 index 0000000..b66f546 --- /dev/null +++ b/casa/covering/state/CoveringArraySubRow.C @@ -0,0 +1,129 @@ +// Copyright 2008, 2009 Brady J. Garvin + +// This file is part of Covering Arrays by Simulated Annealing (CASA). + +// CASA is free software: you can redistribute it and/or modify it +// under the terms of the GNU General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. + +// CASA 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 General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with CASA. If not, see <http://www.gnu.org/licenses/>. + + +#include "covering/state/CoveringArray.H" +#include "CombinadicIterator.H" + +using namespace std; + +void CoveringArray::SubRow::updateTracking(const Array<unsigned>values) { + assert(values.getSize() == columns.getSize()); + const Options&options = owner.coverage.getOptions(); + unsigned strength = owner.coverage.getStrength(); + unsigned limit = options.getSize(); + unsigned changes = 0; + Array<unsigned>oldRow(limit); + Array<unsigned>newRow(limit); + Array<unsigned>changedColumns(columns.getSize()); + for (unsigned i = limit; i--;) { + oldRow[i] = owner(row, i); + } + for (unsigned i = limit, j = values.getSize(); i--;) { + if (j && (columns[j - 1] == i)) { + newRow[i] = values[--j]; + } else { + newRow[i] = oldRow[i]; + } + } + for (unsigned i = 0; i < limit; ++i) { + if (newRow[i] != oldRow[i]) { + changedColumns[changes++] = i; + } + } + changedColumns = Array<unsigned>(changedColumns, changes); + Array<unsigned>firsts = options.getFirstSymbols(); + Array<unsigned>counts = options.getSymbolCounts(); + for (CombinadicIterator combo(limit, strength, changedColumns); + combo; + ++combo) { + const Array<unsigned>updateColumns = *combo; + Array<unsigned>oldSymbols(strength); + Array<unsigned>newSymbols(strength); + for (unsigned j = strength; j--;) { + unsigned column = updateColumns[j]; + oldSymbols[j] = oldRow[column]; + newSymbols[j] = newRow[column]; + } + Coverage<unsigned>::Entry lost = + owner.coverage.hintGet(updateColumns, firsts, counts, oldSymbols); + assert(lost); // Assert that what we lost is something we had to lose. + if (--lost == 0) { + --owner.coverageCount; + if (owner.trackingNoncoverage) { + Array<unsigned>separateCopyOfSymbols(oldSymbols.getSize()); + for (unsigned j = oldSymbols.getSize(); j--;) { + separateCopyOfSymbols[j] = oldSymbols[j]; + } + bool successfulInsertion = + owner.noncoverage->insert(separateCopyOfSymbols).second; + assert(successfulInsertion); + (void)successfulInsertion; // This is unused without assertions. + } + } else { + --owner.multipleCoverageCount; + } + Coverage<unsigned>::Entry gained = + owner.coverage.hintGet(updateColumns, firsts, counts, newSymbols); + if (++gained == 1) { + ++owner.coverageCount; + if (owner.trackingNoncoverage) { + Array<unsigned>separateCopyOfSymbols(newSymbols.getSize()); + for (unsigned j = newSymbols.getSize(); j--;) { + separateCopyOfSymbols[j] = newSymbols[j]; + } + bool successfulErasure = + (bool)owner.noncoverage->erase(separateCopyOfSymbols); + assert(successfulErasure); + (void)successfulErasure; // This is unused without assertions. + } + } else { + ++owner.multipleCoverageCount; + } + } + owner.autoFinalizeSubstitutions(); +} + +CoveringArray::SubRow::operator Array<unsigned>() const { + typedef map<pair<unsigned, unsigned>, unsigned>::const_iterator Substitution; + Substitution end = owner.substitutions->end(); + unsigned size = columns.getSize(); + Array<unsigned>result(size); + pair<unsigned, unsigned>key(row,0); + for (unsigned i = size; i--;) { + key.second = columns[i]; + Substitution substitution = owner.substitutions->find(key); + result[i] = + (substitution == end) ? + owner.array[row][key.second] : + substitution->second; + } + return result; +} +CoveringArray::SubRow&CoveringArray::SubRow::operator = + (const Array<unsigned>values) { + assert(values.getSize() == columns.getSize()); + if (owner.trackingCoverage) { + updateTracking(values); + } + pair<unsigned, unsigned>key(row, 0); + for (unsigned i = columns.getSize(); i--;) { + key.second = columns[i]; + (*owner.substitutions)[key] = values[i]; + } + return *this; +} diff --git a/casa/events/EventSource.H b/casa/events/EventSource.H new file mode 100644 index 0000000..38097f4 --- /dev/null +++ b/casa/events/EventSource.H @@ -0,0 +1,59 @@ +// Copyright 2008, 2009 Brady J. Garvin + +// This file is part of Covering Arrays by Simulated Annealing (CASA). + +// CASA is free software: you can redistribute it and/or modify it +// under the terms of the GNU General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. + +// CASA 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 General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with CASA. If not, see <http://www.gnu.org/licenses/>. + + +#ifndef EVENT_SOURCE_H +#define EVENT_SOURCE_H + +#include <set> +#include "events/Listener.H" + +template<class MESSAGE>class EventSource { +public: + typedef Listener<MESSAGE> ListenerT; + +private: + std::set<ListenerT*> listeners; + +public: + virtual ~EventSource() {} + bool isListener(const ListenerT&listener) const { + return listeners.find(&listener) != listeners.end(); + } + void addListener(ListenerT&listener) { + listeners.insert(&listener); + } + void removeListener(ListenerT&listener) { + listeners.erase(&listener); + } + void removeAllListeners() { + listeners.clear(); + } + +protected: + void dispatch(const MESSAGE&message) { + for(typename std::set<ListenerT*>::iterator iterator = + listeners.begin(), + end = listeners.end(); + iterator != end; + ++iterator) { + (*iterator)->signal(message); + } + } +}; + +#endif diff --git a/casa/events/Listener.H b/casa/events/Listener.H new file mode 100644 index 0000000..45831de --- /dev/null +++ b/casa/events/Listener.H @@ -0,0 +1,28 @@ +// Copyright 2008, 2009 Brady J. Garvin + +// This file is part of Covering Arrays by Simulated Annealing (CASA). + +// CASA is free software: you can redistribute it and/or modify it +// under the terms of the GNU General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. + +// CASA 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 General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with CASA. If not, see <http://www.gnu.org/licenses/>. + + +#ifndef LISTENER_H +#define LISTENER_H + +template<class MESSAGE>class Listener { +public: + virtual ~Listener() {} + virtual void signal(const MESSAGE&message) = 0; +}; + +#endif diff --git a/casa/io/ConstraintFile.C b/casa/io/ConstraintFile.C new file mode 100644 index 0000000..6ea05b2 --- /dev/null +++ b/casa/io/ConstraintFile.C @@ -0,0 +1,50 @@ +// Copyright 2008, 2009 Brady J. Garvin + +// This file is part of Covering Arrays by Simulated Annealing (CASA). + +// CASA is free software: you can redistribute it and/or modify it +// under the terms of the GNU General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. + +// CASA 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 General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with CASA. If not, see <http://www.gnu.org/licenses/>. + + +#include "io/ConstraintFile.H" + +using namespace std; + +ConstraintFile::ConstraintFile(const string&filename) { + if (!filename.size()) { + return; + } + ifstream fileInputStream(filename.data()); + unsigned clauseCount; + fileInputStream >> clauseCount; + clauses = Array<InputClause>(clauseCount); + for (unsigned i = 0; i < clauseCount; ++i) { + InputClause&clause = clauses[i]; + unsigned termCount; + fileInputStream >> termCount; + while (termCount--) { + char sign; + unsigned symbol; + do { + fileInputStream >> sign; + } while (sign != '-' && sign != '+'); + fileInputStream >> symbol; + clause.append(InputTerm(sign == '-', symbol)); + } + } + fileInputStream.close(); +} + +const Array<InputClause>&ConstraintFile::getClauses() const { + return clauses; +} diff --git a/casa/io/ConstraintFile.H b/casa/io/ConstraintFile.H new file mode 100644 index 0000000..cfdb685 --- /dev/null +++ b/casa/io/ConstraintFile.H @@ -0,0 +1,35 @@ +// Copyright 2008, 2009 Brady J. Garvin + +// This file is part of Covering Arrays by Simulated Annealing (CASA). + +// CASA is free software: you can redistribute it and/or modify it +// under the terms of the GNU General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. + +// CASA 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 General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with CASA. If not, see <http://www.gnu.org/licenses/>. + + +#ifndef CONSTRAINT_FILE_H +#define CONSTRAINT_FILE_H + +#include <fstream> +#include <string> + +#include "Array.H" +#include "sat/SAT.H" + +class ConstraintFile { + Array<InputClause> clauses; +public: + ConstraintFile(const std::string&filename); + const Array<InputClause>&getClauses() const; +}; + +#endif diff --git a/casa/io/OutputFile.C b/casa/io/OutputFile.C new file mode 100644 index 0000000..43000ff --- /dev/null +++ b/casa/io/OutputFile.C @@ -0,0 +1,50 @@ +// Copyright 2008, 2009 Brady J. Garvin + +// This file is part of Covering Arrays by Simulated Annealing (CASA). + +// CASA is free software: you can redistribute it and/or modify it +// under the terms of the GNU General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. + +// CASA 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 General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with CASA. If not, see <http://www.gnu.org/licenses/>. + + +#include "io/OutputFile.H" + +using namespace std; + +OutputFile::OutputFile(const string&filename) : + filename(filename) {} + +void OutputFile::setCoveringArray(const CoveringArray&array) { + unsigned rows = array.getRows(); + unsigned options = array.getOptions(); + this->array = Array<Array<unsigned> >(rows); + for (unsigned i = rows; i--;) { + Array<unsigned>&row = this->array[i] = Array<unsigned>(options); + for (unsigned j = options; j--;) { + row[j] = array(i, j); + } + } +} + +void OutputFile::write() const { + ofstream fileOutputStream(filename.data()); + fileOutputStream << array.getSize() << '\n'; + for (unsigned i = 0;i < array.getSize(); ++i) { + const Array<unsigned>&row = array[i]; + fileOutputStream << row[0]; + for (unsigned j = 1; j < row.getSize(); ++j) { + fileOutputStream << ' ' << row[j]; + } + fileOutputStream << '\n'; + } + fileOutputStream.close(); +} diff --git a/casa/io/OutputFile.H b/casa/io/OutputFile.H new file mode 100644 index 0000000..b89345b --- /dev/null +++ b/casa/io/OutputFile.H @@ -0,0 +1,38 @@ +// Copyright 2008, 2009 Brady J. Garvin + +// This file is part of Covering Arrays by Simulated Annealing (CASA). + +// CASA is free software: you can redistribute it and/or modify it +// under the terms of the GNU General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. + +// CASA 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 General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with CASA. If not, see <http://www.gnu.org/licenses/>. + + +#ifndef OUTPUT_FILE_H +#define OUTPUT_FILE_H + +#include <fstream> +#include <string> + +#include "Array.H" +#include "covering/state/CoveringArray.H" + +class OutputFile { +protected: + std::string filename; + Array<Array<unsigned> > array; +public: + OutputFile(const std::string&filename); + void setCoveringArray(const CoveringArray&array); + void write() const; +}; + +#endif diff --git a/casa/io/SpecificationFile.C b/casa/io/SpecificationFile.C new file mode 100644 index 0000000..8fba427 --- /dev/null +++ b/casa/io/SpecificationFile.C @@ -0,0 +1,39 @@ +// Copyright 2008, 2009 Brady J. Garvin + +// This file is part of Covering Arrays by Simulated Annealing (CASA). + +// CASA is free software: you can redistribute it and/or modify it +// under the terms of the GNU General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. + +// CASA 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 General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with CASA. If not, see <http://www.gnu.org/licenses/>. + + +#include "io/SpecificationFile.H" + +using namespace std; + +SpecificationFile::SpecificationFile(const string&filename) { + ifstream fileInputStream(filename.data()); + unsigned optionCount; + fileInputStream >> strength >> optionCount; + Array<unsigned>values(optionCount); + for(unsigned i = 0; i < optionCount; ++i) { + fileInputStream >> values[i]; + } + options = Options(values); + fileInputStream.close(); +} +unsigned SpecificationFile::getStrength() const { + return strength; +} +const Options&SpecificationFile::getOptions() const { + return options; +} diff --git a/casa/io/SpecificationFile.H b/casa/io/SpecificationFile.H new file mode 100644 index 0000000..b027460 --- /dev/null +++ b/casa/io/SpecificationFile.H @@ -0,0 +1,37 @@ +// Copyright 2008, 2009 Brady J. Garvin + +// This file is part of Covering Arrays by Simulated Annealing (CASA). + +// CASA is free software: you can redistribute it and/or modify it +// under the terms of the GNU General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. + +// CASA 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 General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with CASA. If not, see <http://www.gnu.org/licenses/>. + + +#ifndef SPECIFICATION_FILE_H +#define SPECIFICATION_FILE_H + +#include <fstream> +#include <string> + +#include "Array.H" +#include "covering/bookkeeping/Options.H" + +class SpecificationFile { + unsigned strength; + Options options; +public: + SpecificationFile(const std::string&filename); + unsigned getStrength() const; + const Options&getOptions() const; +}; + +#endif diff --git a/casa/io/Usage.C b/casa/io/Usage.C new file mode 100644 index 0000000..676e374 --- /dev/null +++ b/casa/io/Usage.C @@ -0,0 +1,187 @@ +// Copyright 2008, 2009 Brady J. Garvin + +// This file is part of Covering Arrays by Simulated Annealing (CASA). + +// CASA is free software: you can redistribute it and/or modify it +// under the terms of the GNU General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. + +// CASA 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 General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with CASA. If not, see <http://www.gnu.org/licenses/>. + + +#include <cstdlib> +#include <iostream> +#include <posix/getopt.h> + +#include "io/Usage.H" + +using namespace std; + +const char*PROGRAM_NAME = + "Covering Arrays by Simulated Annealing (CASA)"; + +const char*PROGRAM_VERSION = + "1.1b"; + +const char*BUG_ADDRESS = + "bgarvin@cse.unl.edu"; + +static const char*PROGRAM_DOC = + "Builds mixed-level covering arrays under constraints\n" + "\n" + "Copyright 2008, 2009 Brady J. Garvin\n" + "\n" + "CASA is free software: you can redistribute it and/or modify it\n" + "under the terms of the GNU General Public License as published by\n" + "the Free Software Foundation, either version 3 of the License, or\n" + "(at your option) any later version.\n" + "\n" + "CASA is distributed in the hope that it will be useful, but\n" + "WITHOUT ANY WARRANTY; without even the implied warranty of\n" + "MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the\n" + "GNU General Public License for more details.\n" + "\n" + "You should have received a copy of the GNU General Public License\n" + "along with CASA. If not, see <http://www.gnu.org/licenses/>.\n"; + +static const char*USAGE_DOC = + "[OPTIONS] [MODEL_FILE]"; + +static const char*ARG_DOC = + " -o, --output [FILE] write to the given file, regardless of seed\n" + " -c, --constrain [FILE] incorporate the given constraint file\n" + "\n" + " -s, --seed [SEED] set the seed value for the random number generator\n" + "\n" + " -i, --iterations [COUNT] set the initial number of iterations allowed at each array size\n" + " -r, --retries [COUNT] set the number of retries allowed at the same array size\n" + " -p, --partition [RATIO] set the weight of the upper bound in the binary search parition\n" + "\n" + " -t, --temperature [TEMP] set the initial temperature\n" + " -d, --multiplier [RATIO] set the temperature multiplier applied each iteration\n" + "\n" + " -l, --lower-bound [SIZE] let the covering array be no smaller than the given size\n" + " -u, --upper-bound [SIZE] let the covering array be no larger than the given size\n" + " -n, --known-size [SIZE] lock the covering array at the given size\n" + "\n" + " -v, --version show the current version and exit\n" + " -h, --help show this help and exit\n"; + +static const char*shortOptions = + "o:c:s:i:r:p:t:d:l:u:n:vh"; + +static struct option longOptions[] = { + {"output", required_argument, NULL, 'o'}, + {"constrain", required_argument, NULL, 'c'}, + {"seed", required_argument, NULL, 's'}, + {"iterations", required_argument, NULL, 'i'}, + {"retries", required_argument, NULL, 'r'}, + {"partition", required_argument, NULL, 'p'}, + {"temperature", required_argument, NULL, 't'}, + {"decrement", required_argument, NULL, 'd'}, + {"lower-bound", required_argument, NULL, 'l'}, + {"upper-bound", required_argument, NULL, 'u'}, + {"known-size", required_argument, NULL, 'n'}, + {"version", no_argument, NULL, 'v'}, + {"help", no_argument, NULL, 'h'}, + {0, 0, 0, 0 }}; + +bool verbose = true; +const char* modelFile = NULL; +const char* constraintFile = NULL; +const char* outputFile = NULL; +bool seeded = false; +int seed; +double startingTemperature = 0.5L; +double decrement = 0.99999L; +unsigned iterations = 256; +unsigned retries = 2; +unsigned lowerBound = 0; +unsigned upperBound = 0; +double searchPartition = 2.L/3.L; + +static void version() { + cerr << PROGRAM_NAME << ' ' << PROGRAM_VERSION << '\n'; + exit(0); +} + +static const char*name; +static void usage(int error) { + cerr << PROGRAM_NAME << ' ' << PROGRAM_VERSION << " - " << PROGRAM_DOC << + "\n\nUsage: " << name << ' ' << USAGE_DOC << "\n\n" << ARG_DOC << "\n\n" << + "Send bug reports to <" << BUG_ADDRESS << ">.\n"; + exit(error); +} + +void parseOptions(int argc, char*const*argv) { + name = *argv; + bool seen[256]; + (void)seen; // Workaround for a bug in some versions of GCC + for (unsigned i = 256; i-- > 0;) { + seen[i] = false; + } + for (;;) { + int index = 0; + int found = getopt_long(argc, argv, shortOptions, longOptions, &index); + switch (found) { + case 'o': // output + outputFile = optarg; + break; + case 'c': // constrain + constraintFile = optarg; + break; + case 's': // seed + seeded = true; + seed = atoi(optarg); + break; + case 'i': // iterations + iterations = atoi(optarg); + break; + case 'r': // retries + retries = atoi(optarg); + break; + case 'p': // partition + searchPartition = atof(optarg); + break; + case 't': // temperature + startingTemperature = atof(optarg); + break; + case 'd': // decrement + decrement = atof(optarg); + break; + case 'l': // lower-bound + lowerBound = atoi(optarg); + break; + case 'u': // upper-bound + upperBound = atoi(optarg); + break; + case 'n': // known-size + lowerBound = upperBound = atoi(optarg); + break; + case 'v': // version + version(); + break; + case 'h': // help + usage(0); + break; + default: // done with options + if (argc - optind < 1) { + usage(1); + } + if (argc - optind > 1) { + cerr << "Warning: ignoring extraneous arguments after model file ``" << + argv[optind] << "''." << endl; + } + modelFile = argv[optind]; + return; + } + seen[(unsigned)found] = true; + } +} diff --git a/casa/io/Usage.H b/casa/io/Usage.H new file mode 100644 index 0000000..a817be3 --- /dev/null +++ b/casa/io/Usage.H @@ -0,0 +1,38 @@ +// Copyright 2008, 2009 Brady J. Garvin + +// This file is part of Covering Arrays by Simulated Annealing (CASA). + +// CASA is free software: you can redistribute it and/or modify it +// under the terms of the GNU General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. + +// CASA 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 General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with CASA. If not, see <http://www.gnu.org/licenses/>. + + +#ifndef USAGE_H +#define USAGE_H + +extern bool verbose; +extern const char* modelFile; +extern const char* constraintFile; +extern const char* outputFile; +extern bool seeded; +extern int seed; +extern double startingTemperature; +extern double decrement; +extern unsigned iterations; +extern unsigned retries; +extern unsigned lowerBound; +extern unsigned upperBound; +extern double searchPartition; + +void parseOptions(int argc, char*const*argv); + +#endif diff --git a/casa/sat/SAT.C b/casa/sat/SAT.C new file mode 100644 index 0000000..161049b --- /dev/null +++ b/casa/sat/SAT.C @@ -0,0 +1,81 @@ +// Copyright 2008, 2009 Brady J. Garvin + +// This file is part of Covering Arrays by Simulated Annealing (CASA). + +// CASA is free software: you can redistribute it and/or modify it +// under the terms of the GNU General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. + +// CASA 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 General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with CASA. If not, see <http://www.gnu.org/licenses/>. + + +// Other SAT solvers can be substituted by altering SAT.H and SAT.C. + +#include "sat/SAT.H" + +InputClause::InputClause() : + maxVariable(-1) {} + +InputClause::InputClause(Array<InputTerm>terms) : + maxVariable(-1) { + unsigned size = terms.getSize(); + for (unsigned i = 0; i < size; ++i) { + append(terms[i]); + } +} + +InputClause::InputClause(Array<unsigned>symbols) : + maxVariable(-1) { + unsigned size = symbols.getSize(); + for (unsigned i = 0; i < size; ++i) { + append(InputTerm(false, symbols[i])); + } +} + +InputClause::~InputClause() {} + +InputClause::operator vec<Lit>&() { + return literals; +} +InputClause::operator const vec<Lit>&() const { + return literals; +} + +void InputClause::clear(){ + literals.clear(); +} + +void InputClause::append(InputTerm term) { + int variable = term.getVariable(); + if (variable > maxVariable) { + maxVariable = variable; + } + literals.push(term.isNegated() ? ~Lit(variable) : Lit(variable)); +} + +void InputClause::undoAppend() { + literals.pop(); +} + +void SATSolver::reserve(int variables) { + while (variables >= solver.nVars()) { + solver.newVar(); + } +} + +void SATSolver::addClause(InputClause&clause) { + reserve(clause.getMaxVariable()); + solver.addClause(clause); +} + +bool SATSolver::operator()(const InputKnown&known) { + reserve(known.getMaxVariable()); + return solver.simplify() && solver.solve(known); +} diff --git a/casa/sat/SAT.H b/casa/sat/SAT.H new file mode 100644 index 0000000..0dd3467 --- /dev/null +++ b/casa/sat/SAT.H @@ -0,0 +1,92 @@ +// Copyright 2008, 2009 Brady J. Garvin + +// This file is part of Covering Arrays by Simulated Annealing (CASA). + +// CASA is free software: you can redistribute it and/or modify it +// under the terms of the GNU General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. + +// CASA 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 General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with CASA. If not, see <http://www.gnu.org/licenses/>. + + +// Other SAT solvers can be substituted by altering SAT.H and SAT.C. + +#ifndef SAT_H +#define SAT_H + +#include "Array.H" +#include "Solver.H" + +// A literal in a SAT clause. +class InputTerm { +protected: + int encoding; +public: + InputTerm() : + encoding(0) {} + InputTerm(int encoding) : + encoding(encoding) {} + InputTerm(bool negated, int variable) : + encoding( (variable << 1) | (int)negated) {} + + operator int() const { + return encoding; + } + InputTerm&operator =(int encoding) { + this->encoding = encoding; + return *this; + } + + bool isNegated() const { + return encoding & 1; + } + int getVariable() const { + return encoding >> 1; + } +}; + +// A SAT clause. +class InputClause { +protected: + int maxVariable; + vec<Lit> literals; +public: + InputClause(); + InputClause(Array<InputTerm>terms); + InputClause(Array<unsigned>symbols); + virtual ~InputClause(); + + operator vec<Lit>&(); + operator const vec<Lit>&() const; + + int getMaxVariable() const { + return maxVariable; + } + + void clear(); + void append(InputTerm term); + void undoAppend(); +}; + +// A partial assignment. +typedef InputClause InputKnown; + +// A solver-wrapping class. +class SATSolver { +protected: + // The miniSAT implementation. + Solver solver; +public: + void reserve(int variables); + void addClause(InputClause&clause); + bool operator ()(const InputKnown&known); +}; + +#endif diff --git a/casa/search/Filter.H b/casa/search/Filter.H new file mode 100644 index 0000000..071eb71 --- /dev/null +++ b/casa/search/Filter.H @@ -0,0 +1,60 @@ +// Copyright 2008, 2009 Brady J. Garvin + +// This file is part of Covering Arrays by Simulated Annealing (CASA). + +// CASA is free software: you can redistribute it and/or modify it +// under the terms of the GNU General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. + +// CASA 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 General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with CASA. If not, see <http://www.gnu.org/licenses/>. + + +#ifndef FILTER_H +#define FILTER_H + +#include <set> + +#include "search/Heuristic.H" +#include "search/Goal.H" + +// Controls which children (immediately reachable neighbors) are explored by a +// search. The filtering happens after children are enumerated; limitations that +// apply to the enumeration process itself (such as only computing a fixed +// number of random children) are better managed by the parameters in a +// SearchConfiguration, which are passed to the getChildren() method of the +// StateSpace. + +template<class STATE, class COST>class Filter { +public: + typedef Heuristic<STATE,COST> HeuristicT; + typedef Goal<STATE> GoalT; + + virtual ~Filter() {} + + // Mutates the children set; the heuristic and goal may guide the mutation. + virtual void operator() + (std::set<STATE>&children, const HeuristicT&heuristic, const GoalT&goal) + const {} + + // Just as the other operator(), but, at the filter's option, the parent may + // be considered to be its own child. This is useful, for example, when the + // SearchConfiguration is sampling a random subset of the children and the + // filter would prefer a different pool to choose from. + virtual void operator() + (std::set<STATE>&children, + const STATE&parent, + const HeuristicT&heuristic, + const GoalT&goal) const { + children.insert(parent); + operator()(children, heuristic, goal); + } +}; + +#endif diff --git a/casa/search/Goal.H b/casa/search/Goal.H new file mode 100644 index 0000000..d7209c8 --- /dev/null +++ b/casa/search/Goal.H @@ -0,0 +1,32 @@ +// Copyright 2008, 2009 Brady J. Garvin + +// This file is part of Covering Arrays by Simulated Annealing (CASA). + +// CASA is free software: you can redistribute it and/or modify it +// under the terms of the GNU General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. + +// CASA 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 General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with CASA. If not, see <http://www.gnu.org/licenses/>. + + +#ifndef GOAL_H +#define GOAL_H + +// Decides when a search should terminate because it has found a solution. In +// some applications the goal's RTTI is also used to inform other search objects +// (such as the heuristic). + +template<class STATE>class Goal { +public: + virtual ~Goal() {} + virtual bool isGoal(const STATE&state) = 0; +}; + +#endif diff --git a/casa/search/GreedyFilter.H b/casa/search/GreedyFilter.H new file mode 100644 index 0000000..47ddef4 --- /dev/null +++ b/casa/search/GreedyFilter.H @@ -0,0 +1,64 @@ +// Copyright 2008, 2009 Brady J. Garvin + +// This file is part of Covering Arrays by Simulated Annealing (CASA). + +// CASA is free software: you can redistribute it and/or modify it +// under the terms of the GNU General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. + +// CASA 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 General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with CASA. If not, see <http://www.gnu.org/licenses/>. + + +#ifndef GREEDYFILTER_H +#define GREEDYFILTER_H + +#include "search/Filter.H" + +// A specialization of Filter where only the heuristically best child is +// explored. Furthermore, if given the option to treat the parent as a child, +// the filter will only have the search explore children if at least one of them +// is heuristically better than the parent. + +template<class STATE, class COST>class GreedyFilter : + public Filter<STATE, COST> { + typedef Heuristic<STATE, COST> HeuristicT; + typedef Goal<STATE> GoalT; + +public: + void operator() + (std::set<STATE>&children, const HeuristicT&heuristic, const GoalT&goal) + const { + typename std::set<STATE>::iterator best = children.end(); + COST score = 0; + for(typename std::set<STATE>::iterator + iterator = children.begin(), + end = children.end(); + iterator != end; + ++iterator) { + COST estimate = heuristic.estimate(*iterator, goal); + if (best == children.end() || estimate < score) { + best = iterator; + score = estimate; + } + } + for(typename std::set<STATE>::iterator + iterator = children.begin(), + end = children.end(); + iterator != end;){ + if (iterator == best) { + ++iterator; + } else { + children.erase(iterator++); + } + } + } +}; + +#endif diff --git a/casa/search/Guide.H b/casa/search/Guide.H new file mode 100644 index 0000000..797d39f --- /dev/null +++ b/casa/search/Guide.H @@ -0,0 +1,34 @@ +// Copyright 2008, 2009 Brady J. Garvin + +// This file is part of Covering Arrays by Simulated Annealing (CASA). + +// CASA is free software: you can redistribute it and/or modify it +// under the terms of the GNU General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. + +// CASA 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 General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with CASA. If not, see <http://www.gnu.org/licenses/>. + + +#ifndef GUIDE_H +#define GUIDE_H + +// Decides the order in which states are explored. Usual policies include +// visiting the heuristically best states first, visiting states whose distance +// from the start state added to the heuristic is minimal, visiting states +// randomly, etc. There is provision to treat start states specially. + +template<class STATE, class COST>class Guide { +public: + virtual ~Guide() {} + virtual COST rankStart(const Node<STATE, COST>&start) const = 0; + virtual COST rank(const Node<STATE, COST>&node) const = 0; +}; + +#endif diff --git a/casa/search/Heuristic.H b/casa/search/Heuristic.H new file mode 100644 index 0000000..40affe5 --- /dev/null +++ b/casa/search/Heuristic.H @@ -0,0 +1,32 @@ +// Copyright 2008, 2009 Brady J. Garvin + +// This file is part of Covering Arrays by Simulated Annealing (CASA). + +// CASA is free software: you can redistribute it and/or modify it +// under the terms of the GNU General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. + +// CASA 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 General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with CASA. If not, see <http://www.gnu.org/licenses/>. + + +#ifndef HEURISTIC_H +#define HEURISTIC_H + +#include "search/Goal.H" + +// Rates the quality of a state (never a path). + +template<class STATE, class COST>class Heuristic { +public: + virtual ~Heuristic() {} + virtual COST estimate(const STATE&state, const Goal<STATE>&goal) const = 0; +}; + +#endif diff --git a/casa/search/Node.H b/casa/search/Node.H new file mode 100644 index 0000000..5e5b478 --- /dev/null +++ b/casa/search/Node.H @@ -0,0 +1,137 @@ +// Copyright 2008, 2009 Brady J. Garvin + +// This file is part of Covering Arrays by Simulated Annealing (CASA). + +// CASA is free software: you can redistribute it and/or modify it +// under the terms of the GNU General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. + +// CASA 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 General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with CASA. If not, see <http://www.gnu.org/licenses/>. + + +#ifndef NODE_H +#define NODE_H + +#include <cassert> +#include <iostream> +#include <set> + +// Represents an explored state, its heuristic estimate, the best known path +// leading to that state, and other nodes whose best paths this state is on. + +template<class STATE, class COST>class Node { +protected: + typedef Node<STATE,COST>* Edge; + + // The node immediately preceding this one on a best path. + Edge parent; + // The state. + const STATE state; + // The distance from the start state along the best path. + COST traveled; + // The heuristic estimate of the distance to a goal state. + COST estimate; + // The set of nodes who have this one as their parent. + std::set<Edge> children; + +public: + Node(Edge parent, const STATE&state, COST traveled, COST estimate) : + parent(parent), + state(state), + traveled(traveled), + estimate(estimate) { + if (parent) { + parent->children.insert(this); + } + } + + virtual ~Node() { + if (parent) { + parent->removeChild(this); + } + for (typename std::set<Edge>::iterator + iterator = children.begin(), + end = children.end(); + iterator != end;) { + Edge child = *iterator; + ++iterator; + removeChild(child); + } + } + + const STATE&getState() const { + return state; + } + + COST getTraveled() const { + return traveled; + } + void setTraveled(COST traveled) { + this->traveled = traveled; + } + + COST getEstimate() const { + return estimate; + } + void setEstimate(COST estimate) { + this->estimate = estimate; + } + + Edge getParent() const { + return parent; + } + + const std::set<Edge>&getChildren() const { + return children; + } + + void addChild(Edge child) { + assert(child); + if (child->parent) { + if (child->parent == this) { + return; + } + child->parent->removeChild(child); + } + child->parent = this; + children.insert(child); + } + + void removeChild(Edge child) { + assert(child); + if (child->parent != this) { + return; + } + child->parent = NULL; + children.erase(child); + } + + // Comparisons are made solely by state. +#define COMP(op) bool operator op(const Node&other) const { \ + return state op other.state; \ + } + COMP(<); + COMP(>); + COMP(==); + COMP(!=); +#undef COMP +}; + +template<class STATE, class COST>std::ostream&operator << + (std::ostream&out, const Node<STATE, COST>node) { + out << node.getState() << '(' << node.getTraveled() << '+' << + node.getEstimate() << "*)"; + if (node.getParent()) { + return out << "<-" << *node.getParent(); + } + return out; +} + +#endif diff --git a/casa/search/Search.H b/casa/search/Search.H new file mode 100644 index 0000000..0524ea5 --- /dev/null +++ b/casa/search/Search.H @@ -0,0 +1,460 @@ +// Copyright 2008, 2009 Brady J. Garvin + +// This file is part of Covering Arrays by Simulated Annealing (CASA). + +// CASA is free software: you can redistribute it and/or modify it +// under the terms of the GNU General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. + +// CASA 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 General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with CASA. If not, see <http://www.gnu.org/licenses/>. + + +#ifndef SEARCH_H +#define SEARCH_H + +#include <cassert> +#include <vector> +#include <set> + +#include "utility/pless.H" +#include "utility/relation.H" + +#include "events/EventSource.H" + +#include "search/SearchConfiguration.H" +#include "search/Node.H" +#include "search/StateSpace.H" +#include "search/Heuristic.H" +#include "search/Guide.H" +#include "search/Goal.H" +#include "search/Filter.H" +#include "search/SearchIteration.H" +#include "search/SearchFinish.H" + +// A highly parameterized searching object. + +// Clients of this code mostly need to understand the objects passed at +// construction time and, if pathfinding, fulfill the assumption that shortening +// a path prefix will shorten an entire path. The complexity here is merely for +// careful bookkeeping and memory management. + +// The general calling pattern is: +// <constructor> +// foreach search { +// addStartState(...); +// // Possibly more calls to addStartState(...) +// search(...); +// ... = getBest() // If we care about the best results +// // Possibly more calls to search(...) if the search is restartable +// clear(); +// } +// <destructor> + +template<class STATE, class COST>class Search : + public EventSource<SearchIteration>, + public EventSource<SearchFinish<STATE, COST> > { +public: + typedef Node<STATE, COST> NodeT; + +protected: + typedef relation<NodeT*, COST, true, false, pless<NodeT> > + VisitSetT; + typedef StateSpace<STATE, COST> + StateSpaceT; + typedef Heuristic<STATE, COST> + HeuristicT; + typedef Guide<STATE, COST> + GuideT; + typedef Goal<STATE> GoalT; + typedef Filter<STATE,COST> FilterT; + typedef SearchFinish<STATE, COST> + SearchFinishT; + + SearchConfiguration configuration; + StateSpaceT* space; + HeuristicT* heuristic; + GuideT* guide; + GoalT* goal; + FilterT* filter; + bool oneBest; + VisitSetT open; + VisitSetT closed; + std::set<const NodeT*> best; + COST bestRank; + +public: + // See the classes SearchConfiguration, StateSpace, Heuristic, Guide, Goal, + // and Filter for documentation on their role in search. The parameter + // oneBest does not affect the method of search, but merely how many solutions + // are remembered in the case of a tie in the guide's ranking. + Search + (SearchConfiguration configuration, + StateSpaceT*space, + HeuristicT*heuristic, + GuideT*guide, + GoalT*goal, + FilterT*filter, + bool oneBest) : + configuration(configuration), + space(space), + heuristic(heuristic), + guide(guide), + goal(goal), + filter(filter), + oneBest(oneBest) { + assert(space); + assert(heuristic); + assert(guide); + assert(goal); + assert(filter); + } + + virtual ~Search() { + clear(); + } + +protected: + // A leak-free way to clear the set of best nodes. + void clearBest() { + if (!configuration.useClosed) { + for (typename std::set<const NodeT*>::const_iterator + iterator = best.begin(), + end = best.end(); + iterator != end; + ++iterator) { + NodeT*node = const_cast<NodeT*>(*iterator); + if (open.key_find(node) == open.key_end()) { + delete node; + } + } + } + best.clear(); + } + + // See if the given node with the given guide ranking should be entered into + // the set of best nodes. + void updateBest(const NodeT&node, COST rank) { + if (rank < bestRank) { + clearBest(); + } + if (best.empty()) { + best.insert(&node); + bestRank = rank; + } else if (rank == bestRank) { + if (oneBest) clearBest(); + best.insert(&node); + } + } + + // Pop the best ranked node from the set of nodes that have been seen but not + // explored. + NodeT&popBestOpen() { + assert(!open.empty()); + typename VisitSetT::data_iterator pop = open.data_begin(); + assert(pop->second); + if (configuration.useClosed) { + closed.key_insert(pop->second, pop->first); + } + NodeT&result = *(pop->second); + open.data_erase(pop); + return result; + } + + // Get the children (immediately reachable neighbors) according to the + // SearchConfiguration. + std::set<STATE>getChildren(const NodeT&parent) { + if (configuration.proportionChildren) { + return space->getChildren + (parent.getState(), configuration.childrenAsk.proportion); + } + return space->getChildren + (parent.getState(), configuration.childrenAsk.count); + } + + // Return true if a node should be discarded because we have seen a better one + // representing the same state, but not explored it yet. Also, forget about + // any nodes that we have seen but not explored if they represent the same + // state but are worse. + bool replaceInOpen(NodeT&parent, NodeT&node, COST traveled) { + typename VisitSetT::key_iterator similar = open.key_find(&node); + if (similar == open.key_end()) { + // The node does not have an already seen state. + return false; + } + NodeT*visited = similar->first; + assert(visited); + if (visited->getTraveled() <= traveled) { + // The node has an already seen state and cannot improve a path; discard + // it. + return true; + } + // The node has an already seen state, but may improve some paths; use it + // instead. + if (configuration.useClosed) { + parent.addChild(visited); + } + visited->setTraveled(traveled); + open.key_erase(similar); + COST rank = guide->rank(*visited); + open.key_insert(visited, rank); + updateBest(*visited, rank); + return true; + } + + // Correct any out-of-date distance calculations when we change a path prefix. + // The arguments are the newly connected parent and child nodes. + void updateTraveled(NodeT&parent, NodeT&visited) { + // Setup to DFS from the visited node. + std::set<NodeT*>parentSet; + std::set<NodeT*>visitedSet; + parentSet.insert(&parent); + visitedSet.insert(&visited); + std::vector<const std::set<NodeT*>*>extrusion; + std::vector<typename std::set<NodeT*>::const_iterator>path; + extrusion.push_back(&parentSet); + path.push_back(extrusion.back()->begin()); + extrusion.push_back(&visitedSet); + path.push_back(extrusion.back()->begin()); + // Run the DFS, updating traveled distances and resorting. + for (;;) { + if (path.back() == extrusion.back()->end()) { + path.pop_back(); + extrusion.pop_back(); + if (path.empty()) { + break; + } + ++path.back(); + } else { + typename + std::vector<typename std::set<NodeT*>::const_iterator>:: + const_reverse_iterator back = path.rbegin(); + NodeT&update = ***back; + assert(&update); + ++back; + NodeT&source = ***back; + assert(&source); + update.setTraveled(space->getTraveled(source, update.getState())); + COST rank = guide->rank(update); + typename VisitSetT::key_iterator moribund = open.key_find(&update); + if (moribund != open.key_end()) { + open.key_erase(moribund); + open.key_insert(&update, rank); + updateBest(update, rank); + ++path.back(); + } else { + moribund = closed.key_find(&update); + assert(moribund != closed.key_end()); + closed.key_erase(moribund); + closed.key_insert(&update, rank); + updateBest(update, rank); + // Push children. + extrusion.push_back(&update.getChildren()); + path.push_back(extrusion.back()->begin()); + } + } + } + } + + // Return true if a node should be discarded because we have explored a better + // node representing the same state. Also, forget about any nodes that we + // have explored if they represent the same state but are worse. + bool replaceInClosed(NodeT&parent, NodeT&node, COST traveled) { + typename VisitSetT::key_iterator similar = closed.key_find(&node); + if (similar == closed.key_end()) { + // The node does not have an already explored state. + return false; + } + NodeT*visited = similar->first; + assert(visited); + if (visited->getTraveled() <= traveled) { + // The node has an already explored state and cannot improve a path; + // discard it. + return true; + } + // The node has an already explored state, but will improve some paths; use + // it instead. + parent.addChild(visited); + updateTraveled(parent, *visited); + return true; + } + + //Add a newly seen node to the set of seen but not yet explored nodes. + void addNew(NodeT*node) { + COST rank = guide->rank(*node); + open.key_insert(node,rank); + updateBest(*node,rank); + } + +public: + // Add a start state before searching. + void addStartState(const STATE&start) { + NodeT*node = + new NodeT + (NULL, + start, + space->getTraveled(start), + heuristic->estimate(start, *goal)); + addNew(node); + } + + // Try to find a goal in the given budget. If restartable is true the search + // can be resumed by a later call to this method. + std::set<NodeT*>search(unsigned iterations, bool restartable) { + std::set<NodeT*>result; + if (open.empty()) { + return result; + } + for (unsigned i = iterations, j = configuration.prunePeriod; + i-- && result.empty();) { +#ifdef SEARCH_PROGRESS + if (!(i & 0x3FF)) { + std::cout << i << " iterations left after this one" << std::endl; + } +#endif + NodeT&parent = popBestOpen(); + // If it is time to prune exploration to the most promising frontier: + if (!--j) { + j = configuration.prunePeriod; + std::set<const NodeT*>lineage; + typename std::set<const NodeT*>::const_iterator + lineageEnd = lineage.end(); + for (const NodeT*k = &parent; k; k = k->getParent()) { + lineage.insert(k); + } + for (typename VisitSetT::key_iterator + k = closed.key_begin(), + kend = closed.key_end(); + k != kend;) { + if (lineage.find(k->first) == lineageEnd) { + delete k->first; + closed.key_erase(k++); + } else { + ++k; + } + } + for (typename VisitSetT::key_iterator + k = open.key_begin(), + kend = open.key_end(); + k != kend;++k) { + delete k->first; + } + open.clear(); + } + // Explore. + std::set<STATE>children = getChildren(parent); + if (configuration.retryChildren) { + (*filter)(children, parent.getState(), *heuristic, *goal); + } else { + (*filter)(children, *heuristic, *goal); + } + // The flag to decide if the parent information can be deleted. It is + // true when we aren't looking for paths and the parent isn't part of the + // best set. + bool parentMoribund = false; + if (!configuration.useClosed) { + typename std::set<const NodeT*>::const_iterator + asBest = best.find(&parent), + bestEnd = best.end(); + if (asBest == bestEnd) { + parentMoribund = true; + } + } + // See children. + for (typename std::set<STATE>::const_iterator + iterator = children.begin(), + end = children.end(); + iterator != end; + ++iterator) { + COST traveled = space->getTraveled(parent, *iterator); + NodeT*node = + new NodeT + (configuration.useClosed ? &parent : NULL, + *iterator, + traveled, + heuristic->estimate(*iterator, *goal)); + if (replaceInOpen(parent, *node, traveled)) { + // The new node was beaten by something in the open set. + delete node; + } else if (configuration.useClosed && + replaceInClosed(parent, *node, traveled)) { + // The new node was beaten by something in the closed set. + delete node; + } else { + // The new node is worth exploring. + addNew(node); + // Track goals. + if (goal->isGoal(*iterator)) { + result.insert(node); + // If we are just interested in finding a goal, we can return now. + if (!restartable) { + if (parentMoribund) { + delete &parent; + } + // Complete the search. + SearchFinishT finish(*this, result, iterations - i, iterations); + EventSource<SearchFinishT>::dispatch(finish); + return result; + } + } + } + } + if (parentMoribund) { + delete &parent; + } + // Complete the iteration. + SearchIteration iteration; + EventSource<SearchIteration>::dispatch(iteration); + } + // Complete the search. + SearchFinishT finish(*this, result, iterations, iterations); + EventSource<SearchFinishT>::dispatch(finish); + return result; + } + +#define GET_SET(type, member, capMember) \ + const type get ## capMember() const { \ + return member; \ + } \ + void set ## capMember(const type&member) { \ + this->member = member; \ + } + GET_SET(SearchConfiguration, configuration, SearchConfiguration); + GET_SET(StateSpaceT*, space, Space); + GET_SET(HeuristicT*, heuristic, Heuristic); + GET_SET(GuideT*, guide, Guide); + GET_SET(GoalT*, goal, Goal); +#undef GET_SET + + const std::set<const NodeT*>getBest() const { + return best; + } + + void clear() { + clearBest(); + for (typename VisitSetT::key_iterator + k = open.key_begin(), + kend = open.key_end(); + k != kend; + ++k) { + delete k->first; + } + open.clear(); + for (typename VisitSetT::key_iterator + k = closed.key_begin(), + kend = closed.key_end(); + k != kend; + ++k) { + delete k->first; + } + closed.clear(); + } +}; + +#endif diff --git a/casa/search/SearchConfiguration.H b/casa/search/SearchConfiguration.H new file mode 100644 index 0000000..469a6ae --- /dev/null +++ b/casa/search/SearchConfiguration.H @@ -0,0 +1,99 @@ +// Copyright 2008, 2009 Brady J. Garvin + +// This file is part of Covering Arrays by Simulated Annealing (CASA). + +// CASA is free software: you can redistribute it and/or modify it +// under the terms of the GNU General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. + +// CASA 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 General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with CASA. If not, see <http://www.gnu.org/licenses/>. + + +#ifndef SEARCH_CONFIGURATION_H +#define SEARCH_CONFIGURATION_H + +// Controls behaviors of the search that are parameterized by value, not code. + +struct SearchConfiguration { + // Should we keep a history of where we've been? + // Defaults to true. + // If false: + // Nodes are always without parent, so the search cannot find paths. + // States that have been visited and expanded may be visited and expanded + // again. + bool useClosed; + + // Should we allow a parent to consider itself its own child? + // Defaults to false. + // If true: + // Node's states are forcibly added to their own sets of children. + // Filters can therefore choose the trivial (no-move) transition, like in + // hill-climbing. + // The search may spin at local maxima. + bool retryChildren; + + // Should we limit the number of children by a proportion rather than a count? + // Defaults to true. + // If true: + // The state space is asked to enumerate a fixed proportion of children. + // States with more children will have longer enumerations. + // If false: + // The state space is asked to enumerate a fixed number of children. + // States with too few children will have all of them listed. + // States with too many children will not. + bool proportionChildren; + + // How many children should we ask for? + // (See the documentation of proportionChildren above.) + union { + float proportion; + unsigned count; + } childrenAsk; + + // How many iterations before each pruning of the space? + // Defaults to zero, which is treated as infinity. + // If nonzero: + // After the given number of iterations, the search will forget all visits + // except for the best nodes in the closed and open sets. + // This is sometimes an appropriate way to trade performance for memory. + unsigned prunePeriod; + + SearchConfiguration() : + useClosed(true), + retryChildren(false), + proportionChildren(true), + prunePeriod(0) { + childrenAsk.proportion = 1; + } + SearchConfiguration + (bool useClosed, + bool retryChildren, + float proportion, + unsigned prunePeriod) : + useClosed(useClosed), + retryChildren(retryChildren), + proportionChildren(true), + prunePeriod(prunePeriod) { + childrenAsk.proportion = proportion; + } + SearchConfiguration + (bool useClosed, + bool retryChildren, + unsigned count, + unsigned prunePeriod) : + useClosed(useClosed), + retryChildren(retryChildren), + proportionChildren(false), + prunePeriod(prunePeriod) { + childrenAsk.count = count; + } +}; + +#endif diff --git a/casa/search/SearchFinish.H b/casa/search/SearchFinish.H new file mode 100644 index 0000000..67d4835 --- /dev/null +++ b/casa/search/SearchFinish.H @@ -0,0 +1,55 @@ +// Copyright 2008, 2009 Brady J. Garvin + +// This file is part of Covering Arrays by Simulated Annealing (CASA). + +// CASA is free software: you can redistribute it and/or modify it +// under the terms of the GNU General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. + +// CASA 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 General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with CASA. If not, see <http://www.gnu.org/licenses/>. + + +#ifndef SEARCH_FINISH_H +#define SEARCH_FINISH_H + +#include <set> + +#include "search/Node.H" + +// A forward declaration for when this header is included by Search.H: +template<class, class>class Search; + +// A message broadcast when a search finishes (even if it was unsuccessful). + +template<class STATE, class COST>class SearchFinish { +public: + typedef Search<STATE, COST> SearchT; + typedef Node<STATE, COST> NodeT; + + const SearchT& source; + std::set<NodeT*> results; + unsigned iterations; + unsigned maxIterations; + + SearchFinish + (const SearchT&source, + const std::set<NodeT*>&results, + unsigned iterations, + unsigned maxIterations) : + source(source), + results(results), + iterations(iterations), + maxIterations(maxIterations) {} +}; + +// For inclusion from anywhere but Search.H: +#include "search/Search.H" + +#endif diff --git a/casa/search/SearchIteration.H b/casa/search/SearchIteration.H new file mode 100644 index 0000000..41a267a --- /dev/null +++ b/casa/search/SearchIteration.H @@ -0,0 +1,28 @@ +// Copyright 2008, 2009 Brady J. Garvin + +// This file is part of Covering Arrays by Simulated Annealing (CASA). + +// CASA is free software: you can redistribute it and/or modify it +// under the terms of the GNU General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. + +// CASA 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 General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with CASA. If not, see <http://www.gnu.org/licenses/>. + + +#ifndef SEARCH_ITERATION_H +#define SEARCH_ITERATION_H + +// A message broadcast when a search completes an iteration but does not finish. + +class SearchIteration { + // Information about the progress of search could go here. +}; + +#endif diff --git a/casa/search/StateGuide.H b/casa/search/StateGuide.H new file mode 100644 index 0000000..0551904 --- /dev/null +++ b/casa/search/StateGuide.H @@ -0,0 +1,34 @@ +// Copyright 2008, 2009 Brady J. Garvin + +// This file is part of Covering Arrays by Simulated Annealing (CASA). + +// CASA is free software: you can redistribute it and/or modify it +// under the terms of the GNU General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. + +// CASA 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 General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with CASA. If not, see <http://www.gnu.org/licenses/>. + + +#ifndef STATE_GUIDE_H +#define STATE_GUIDE_H + +// A specialized guide that ranks strictly by the states' heuristic estimates. + +template<class STATE, class COST>class StateGuide : public Guide<STATE, COST> { +public: + COST rankStart(const Node<STATE, COST>&start) const { + return start.getEstimate(); + } + COST rank(const Node<STATE, COST>&node) const { + return node.getEstimate(); + } +}; + +#endif diff --git a/casa/search/StateSpace.H b/casa/search/StateSpace.H new file mode 100644 index 0000000..5003f9b --- /dev/null +++ b/casa/search/StateSpace.H @@ -0,0 +1,50 @@ +// Copyright 2008, 2009 Brady J. Garvin + +// This file is part of Covering Arrays by Simulated Annealing (CASA). + +// CASA is free software: you can redistribute it and/or modify it +// under the terms of the GNU General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. + +// CASA 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 General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with CASA. If not, see <http://www.gnu.org/licenses/>. + + +#ifndef STATE_SPACE_H +#define STATE_SPACE_H + +#include <set> + +#include "search/Node.H" + +// A description of a state space, namely the state interconnections and +// distances (for pathfinding rather than statefinding). + +template<class STATE, class COST>class StateSpace { +public: + virtual ~StateSpace() {} + + // Determine the distance incurred by starting at the given state. + virtual COST getTraveled(const STATE&start) const = 0; + + // Determine the total distance traveled to reach state after taking the best + // known path reaching parent. + virtual COST getTraveled(const Node<STATE, COST>&parent, const STATE&state) + const = 0; + + // Enumerate a fixed fraction of the children of state, rounding up. + virtual std::set<STATE>getChildren(const STATE&state, float proportion) + const = 0; + + // Enumerate the children of state up to some limit. + virtual std::set<STATE>getChildren(const STATE&state, unsigned count) + const = 0; +}; + +#endif |