omnics
Class SystematicSolver

java.lang.Object
  omnics.AbstractSolver
      omnics.SystematicSolver

All Implemented Interfaces:

java.io.Serializable, Solver

Direct Known Subclasses:

Backtracking

public abstract class SystematicSolver
extends AbstractSolver

Abstract class that describes a solver capable of exploring systematically the search space in order to find one or all solutions of a problem.

Author:

Cristian Frasinaru

See Also:

Serialized Form

Field Summary

protected AssignmentStrategy	assignmentStrategy
protected long	attempts
protected long	backtrackCounter
protected BackwardStrategy	backwardStrategy
protected BoundAlgorithm	boundAlgorithm
protected VarSet	candidates
protected VarSet[]	candidatesMap
protected ConstraintSet[]	constraintsMap
static boolean	DEBUG
protected Domain[][]	domainsMap
protected EventHandler	eventHandler
protected Explainer	explainer
protected Var	failed
protected long	failures
protected java.util.List<Filter>	filters
protected boolean	firingEvents
protected ForwardStrategy	forwardStrategy
protected java.util.List<SolverListener>	listeners
protected long	longestBacktrack
protected java.util.Stack<Var>	path
protected Tuple[]	solutionMap
protected long	thrashing

Fields inherited from class omnics.AbstractSolver

analyzer, endTime, optimum, paused, problem, running, solution, solutions, solutionsLimit, startTime, timeLimit

Fields inherited from interface omnics.Solver

BENCHMARK_FORMAT, DETAILED_FORMAT

Constructor Summary

SystematicSolver(Problem problem)
Creates a new instance of SystematicSolver

Method Summary

void	addFilter(Filter filter) Adds a filter to the solver.
void	addListener(SolverListener listener)
protected void	assign(Var var, java.lang.Object value)
long	attempts() Returns the number of attemtps to extend the current solution.
java.util.List<Var>	candidates()
void	copyCandidates() Saves in memory a copy of the candidates
void	copyConstraints() Saves in memory a copy of the problem constraints
void	copyDomain(Var var) Saves in memory a copy of the variable 'var'
void	copySolution() Saves in memory a copy of the solution
Var	current() Returns the current variable.
java.lang.String	explain() Constructs an explanation for: "why the problem is not consistent?"
java.lang.String	explain(Tuple tuple) Constructs an explanation: "why this tuple is not good?"
java.lang.String	explain(Var var, java.lang.Object val) Constructs an explanation for: "why x=a is not good?"
long	failures() Returns the number of failures (backward steps).
AssignmentStrategy	getAssignmentStrategy()
BackwardStrategy	getBackwardStrategy()
BoundAlgorithm	getBoundAlgorithm() Returns the algorithm for bounding the problem.
EventHandler	getEventHandler()
Explainer	getExplainer()
Var	getFailed() Returns the last node that failed.
Filter	getFilter(java.lang.String name) Returns a certain filter.
java.util.List<Filter>	getFilters() Returns the solver's filters.
ForwardStrategy	getForwardStrategy() Returns the forward strategy: the heuristic used for selecting the next variable which will be instantiated.
java.util.List<SolverListener>	getListeners()
void	initSolution(Tuple solution) Sets the initial solution.
boolean	isApplyingFilters()
boolean	isDynamicConstrained()
boolean	isFiringEvents()
boolean	isPaused() Returns true if the solver is paused.
Var	last() Returns the last variable on the solver path
long	longestBacktrack() Returns the number of failures (backward steps).
java.util.Stack<Var>	path() Returns the current path.
void	printResult(java.io.PrintStream out)
void	printResult(java.io.PrintStream out, int format) Prints the result of the algorithm.
void	removeAllFilters() Removes a filter from the solver.
void	removeFilter(Filter filter) Removes a filter from the solver.
void	removeListener(SolverListener listener)
protected boolean	resolveSingletons() Resolves the singleton domains.
void	restoreCandidates(Var current) Restores the solution saved when the current node was 'current'
void	restoreConstraints(Var current) Restores the constraints of the problem saved when the current node was 'current'
void	restoreDomain(Var var, Var current) Restores the domain of 'var' saved when the current node was 'current'
void	restoreProblem(Var trigger) Restores the problem to a specific point.
void	restoreSolution(Var current) Restores the solution saved when the current node was 'current'
void	setApplyingFilters(boolean applyingFilters)
void	setAssignmentStrategy(AssignmentStrategy assignmentStrategy)
void	setBackwardStrategy(BackwardStrategy backwardStrategy)
void	setBoundAlgorithm(BoundAlgorithm boundAlgorithm) Sets an algorithm for bounding the problem.
void	setDynamicConstrained(boolean dynamicConstrained)
void	setEventHandler(EventHandler eventHandler)
void	setExplainer(Explainer explainer)
void	setFailed(Var failed)
void	setFiringEvents(boolean firingEvents)
void	setForwardStrategy(ForwardStrategy forwardStrategy) Sets the forward strategy: the heuristic used for selecting the next variable which will be instantiated.
void	setListeners(java.util.List<SolverListener> listeners)
void	setPaused(boolean paused) Causes the solver to pause or to resume execution.
void	stop() Stops permanently the solver.

Methods inherited from class omnics.AbstractSolver

eval, getAnalyzer, getEndTime, getProblem, getSolutionsLimit, getStartTime, getTimeLimit, isRunning, logResult, optimum, save, setAnalyzer, setEndTime, setProblem, setRunning, setSolutionsLimit, setStartTime, setTimeLimit, solution, solutions, solve, solve, solveAll, time, timeToString

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

assignmentStrategy

protected AssignmentStrategy assignmentStrategy

forwardStrategy

protected ForwardStrategy forwardStrategy

backwardStrategy

protected BackwardStrategy backwardStrategy

filters

protected java.util.List<Filter> filters

boundAlgorithm

protected BoundAlgorithm boundAlgorithm

failed

protected Var failed

attempts

protected long attempts

failures

protected long failures

backtrackCounter

protected long backtrackCounter

longestBacktrack

protected long longestBacktrack

thrashing

protected long thrashing

path

protected java.util.Stack<Var> path

candidates

protected VarSet candidates

solutionMap

protected Tuple[] solutionMap

candidatesMap

protected VarSet[] candidatesMap

domainsMap

protected Domain[][] domainsMap

constraintsMap

protected ConstraintSet[] constraintsMap

eventHandler

protected EventHandler eventHandler

firingEvents

protected boolean firingEvents

listeners

protected java.util.List<SolverListener> listeners

explainer

protected Explainer explainer

DEBUG

public static boolean DEBUG

Constructor Detail

SystematicSolver

public SystematicSolver(Problem problem)

Creates a new instance of SystematicSolver

Method Detail

initSolution

public void initSolution(Tuple solution)

Sets the initial solution.

getFailed

public Var getFailed()

Returns the last node that failed. (the solver was unable to instantiate it and had to back).

setFailed

public void setFailed(Var failed)

getForwardStrategy

public ForwardStrategy getForwardStrategy()

Returns the forward strategy: the heuristic used for selecting the next variable which will be instantiated.

setForwardStrategy

public void setForwardStrategy(ForwardStrategy forwardStrategy)

Sets the forward strategy: the heuristic used for selecting the next variable which will be instantiated.

getAssignmentStrategy

public AssignmentStrategy getAssignmentStrategy()

setAssignmentStrategy

public void setAssignmentStrategy(AssignmentStrategy assignmentStrategy)

getBackwardStrategy

public BackwardStrategy getBackwardStrategy()

setBackwardStrategy

public void setBackwardStrategy(BackwardStrategy backwardStrategy)

addFilter

public void addFilter(Filter filter)

Adds a filter to the solver.

removeFilter

public void removeFilter(Filter filter)

Removes a filter from the solver.

removeAllFilters

public void removeAllFilters()

Removes a filter from the solver.

getFilters

public java.util.List<Filter> getFilters()

Returns the solver's filters.

getFilter

public Filter getFilter(java.lang.String name)

Returns a certain filter.

getBoundAlgorithm

public BoundAlgorithm getBoundAlgorithm()

Returns the algorithm for bounding the problem.

setBoundAlgorithm

public void setBoundAlgorithm(BoundAlgorithm boundAlgorithm)

Sets an algorithm for bounding the problem.

current

public Var current()

Returns the current variable.

path

public java.util.Stack<Var> path()

Returns the current path.

candidates

public java.util.List<Var> candidates()

attempts

public long attempts()

Returns the number of attemtps to extend the current solution.

failures

public long failures()

Returns the number of failures (backward steps).

longestBacktrack

public long longestBacktrack()

Returns the number of failures (backward steps).

last

public Var last()

Returns the last variable on the solver path

copyDomain

public void copyDomain(Var var)

Saves in memory a copy of the variable 'var'

restoreDomain

public void restoreDomain(Var var,
                          Var current)

Restores the domain of 'var' saved when the current node was 'current'

copyConstraints

public void copyConstraints()

Saves in memory a copy of the problem constraints

restoreConstraints

public void restoreConstraints(Var current)

Restores the constraints of the problem saved when the current node was 'current'

copySolution

public void copySolution()

Saves in memory a copy of the solution

restoreSolution

public void restoreSolution(Var current)

Restores the solution saved when the current node was 'current'

copyCandidates

public void copyCandidates()

Saves in memory a copy of the candidates

restoreCandidates

public void restoreCandidates(Var current)

Restores the solution saved when the current node was 'current'

restoreProblem

public void restoreProblem(Var trigger)

Restores the problem to a specific point.

printResult

public void printResult(java.io.PrintStream out,
                        int format)

Description copied from interface: Solver

Prints the result of the algorithm.

Specified by:

printResult in interface Solver

Overrides:

printResult in class AbstractSolver

Parameters:

out - a PrintStream

format - DETAILED_FORMAT or BENCHMARK_FORMAT;

printResult

public void printResult(java.io.PrintStream out)

Overrides:

printResult in class AbstractSolver

isApplyingFilters

public boolean isApplyingFilters()

setApplyingFilters

public void setApplyingFilters(boolean applyingFilters)

assign

protected void assign(Var var,
                      java.lang.Object value)

resolveSingletons

protected boolean resolveSingletons()

Resolves the singleton domains. If Dx={a} then solution = solution U {x=a} candidates = candidates - {x}

getExplainer

public Explainer getExplainer()

setExplainer

public void setExplainer(Explainer explainer)

explain

public java.lang.String explain()

Constructs an explanation for: "why the problem is not consistent?"

explain

public java.lang.String explain(Var var,
                                java.lang.Object val)

Constructs an explanation for: "why x=a is not good?"

explain

public java.lang.String explain(Tuple tuple)

Constructs an explanation: "why this tuple is not good?"

addListener

public void addListener(SolverListener listener)

removeListener

public void removeListener(SolverListener listener)

getListeners

public java.util.List<SolverListener> getListeners()

setListeners

public void setListeners(java.util.List<SolverListener> listeners)

getEventHandler

public EventHandler getEventHandler()

setEventHandler

public void setEventHandler(EventHandler eventHandler)

isFiringEvents

public boolean isFiringEvents()

setFiringEvents

public void setFiringEvents(boolean firingEvents)

stop

public void stop()

Description copied from interface: Solver

Stops permanently the solver.

Specified by:

stop in interface Solver

Overrides:

stop in class AbstractSolver

isPaused

public boolean isPaused()

Description copied from interface: Solver

Returns true if the solver is paused. Use setPaused(false) to resume the execution.

Specified by:

isPaused in interface Solver

Overrides:

isPaused in class AbstractSolver

Returns:

true if the solver is pause, false if the solver is running

setPaused

public void setPaused(boolean paused)

Description copied from interface: Solver

Causes the solver to pause or to resume execution.

Specified by:

setPaused in interface Solver

Overrides:

setPaused in class AbstractSolver

Parameters:

paused - if true, the solver will pause, otherwise it will resume execution

isDynamicConstrained

public boolean isDynamicConstrained()

setDynamicConstrained

public void setDynamicConstrained(boolean dynamicConstrained)