Package org.jacop.search
Class DepthFirstSearch<T extends Var>
- java.lang.Object
-
- org.jacop.search.DepthFirstSearch<T>
-
- Type Parameters:
T
- type of variables used in this search.
- All Implemented Interfaces:
Search<T>
- Direct Known Subclasses:
PrioritySearch
,PrioritySearch.LinkingSearch
public class DepthFirstSearch<T extends Var> extends java.lang.Object implements Search<T>
Implements Depth First Search with number of possible plugins (listeners) to be attached to modify the search.- Version:
- 4.8
-
-
Field Summary
Fields Modifier and Type Field Description (package private) boolean
assignSolution
It decides if the found solution is immediately assigned to the store.* If the solution is not assigned immediately after the search is concluded but later then special care may be required.(package private) long
backtracksOut
It specifies after how many backtracks the search exits.(package private) boolean
backtracksOutCheck
It specifies if the backtrack out is on.(package private) boolean
check
It specifies if search can exit before the search has finished.Search<? extends Var>[]
childSearches
It stores searches which will be executed when this one has assign all its variables.ConsistencyListener
consistencyListener
It is invoked when consistency function has been executed.(package private) Constraint
cost
It represents the constraint which enforces that next solution is better than currently best solution.int
costValue
It represents the cost value of currently best solution for IntVar cost.double
costValueFloat
It represents the cost value of currently best solution for FloatVar cost.Var
costVariable
It represents the cost variable.int
currentChildSearch
It remembers what child search has been already examined.(package private) static boolean
debugAll
(package private) int
decisions
It stores number of nodes with decisions during search.(package private) long
decisionsOut
It specifies after how many decisions the search exits.(package private) boolean
decisionsOutCheck
It specifies if the decisions out is on.(package private) int
depth
It represents current depth of store used in search.(package private) int
depthExcludePaths
It stores current depth of the search excluding paths in a search tree.boolean
einAinleftTree
It specifies if for setVar based search the left branch should impose EinA constraint.ExitChildListener<T>
exitChildListener
It is invoked when returning from left or right child.(package private) ExitListener
exitListener
It is executed upon search exit.(package private) SelectChoicePoint<T>
heuristic
It represents the choice point selection heuristic.java.lang.String
id
It specifies the id of the search.InitializeListener
initializeListener
It is executed when search is started, before entering the search.Search<? extends Var>
masterSearch
If this search is a sub-search then this pointer will point out to the master search (i.e.(package private) int
maxDepth
It stores the maximum depth reached during search.(package private) int
maxDepthExcludePaths
It stores the maximum depth of the search excluding paths.(package private) static java.util.concurrent.atomic.AtomicInteger
no
(package private) int
nodes
It stores number of nodes visited during search.(package private) long
nodesOut
It specifies after how many nodes the search exits.(package private) boolean
nodesOutCheck
It specifies if the nodes out is on.(package private) int
numberBacktracks
It stores number of backtracks during search.(package private) boolean
optimize
(package private) boolean
printInfo
It decides if information about search is printed.boolean
respectSolutionListenerAdvice
If it is set to true then the optimizing search will quit the search if this action is indicated by the solution listener.SolutionListener<T>
solutionListener
It is executed when a solution is found.Store
store
It represents store within which a search is performed.(package private) long
timeOut
It specifies the exact time point after which the timeout will occur (in miliseconds).(package private) boolean
timeOutCheck
It specifies if the timeout is on.(package private) TimeOutListener
timeOutListener
The object informed about the determination of the timeout.boolean
timeOutOccured
It specifies that the time-out has occured(package private) long
tOut
It specifies the number of seconds after which the search will timeout.(package private) int
wrongDecisions
It stores number of wrong decisions during search.(package private) long
wrongDecisionsOut
It specifies after how many wrong decisions the search exits.(package private) boolean
wrongDecisionsOutCheck
It specifies if the wrong decisions out is on.
-
Constructor Summary
Constructors Constructor Description DepthFirstSearch()
It specifies current child search.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description void
addChildSearch(Search<? extends Var> child)
It adds another child search to this one.boolean
assignSolution()
It assigns the last solution.boolean
assignSolution(int no)
The first solution has index 0.int
getBacktracks()
It returns number of backtracks performed by the search.ConsistencyListener
getConsistencyListener()
It returns the root of the Consistency Listener.int
getCostValue()
It returns the value of the cost int variable for the best solution.double
getCostValueFloat()
It returns the value of the cost float variable for the best solution.Var
getCostVariable()
It returns the cost variable.int
getDecisions()
It returns number of decisions performed by the search.ExitChildListener<T>
getExitChildListener()
It returns the root of the ExitChildListener.ExitListener
getExitListener()
It returns the root of the ExitListener.InitializeListener
getInitializeListener()
It returns the root of the InitializationListener.int
getMaximumDepth()
It returns the maximum depth reached by a search.int
getNodes()
It returns number of search nodes explored by the search.Domain[]
getSolution()
It returns the solution (an assignment of values to variables).Domain[]
getSolution(int no)
It returns the solution specified by the search.SolutionListener<T>
getSolutionListener()
It returns the root Solution Listener.TimeOutListener
getTimeOutListener()
It returns the root of the TimeOutListener.T[]
getVariables()
It returns the order of variables used by functions returning a solution in terms of the values.int
getWrongDecisions()
It returns number of wrong decisions performed by the search.java.lang.String
id()
It returns the string id of the search.boolean
label(int firstVariable)
This function is called recursively to assign variables one by one.boolean
labeling()
It is a labeling function called if the search is a sub-search being called from the parent search.boolean
labeling(Store store, SelectChoicePoint<T> select)
It performs search using supplied choice point selection heuristic.boolean
labeling(Store store, SelectChoicePoint<T> select, Var costVar)
It performs search using supplied choice point selection heuristic, as well as costVariable as aim at finding an optimal solution.void
printAllSolutions()
It prints all solutions.void
setAssignSolution(boolean value)
It decides if a solution is assigned to store after search exits.void
setBacktracksOut(long out)
It turns on the backtrack out.void
setChildSearch(Search<? extends Var>[] child)
It specifies the sub-searches for the current search.void
setConsistencyListener(ConsistencyListener listener)
It sets the root of the Consistency Listener.void
setCostVar(Var cost)
It sets the reference to the cost variable.void
setDecisionsOut(long out)
It turns on the decisions out.void
setExitChildListener(ExitChildListener<T> listener)
It sets the root of the ExitChild listener.void
setExitListener(ExitListener listener)
It sets the root of the Exit Listener.void
setID(java.lang.String name)
It sets the id of the store.void
setInitializeListener(InitializeListener listener)
It sets the root of the InitializeListener.void
setMasterSearch(Search<? extends Var> master)
If the search is called by a master search then the search may need to obtain some information about the master search.void
setNodesOut(long out)
It turns on the nodes out.(package private) void
setOptimizationForChildSearches(DepthFirstSearch s, Var costVar)
void
setOptimize(boolean value)
It sets the optimization flag.void
setPrintInfo(boolean value)
It decides if information about search is printed.void
setSelectChoicePoint(SelectChoicePoint<T> select)
It sets the select choice point object.void
setSolutionListener(SolutionListener<T> listener)
It returns the root of the SolutionListener.void
setStore(Store store)
It sets the reference to the store in the context of which the search operates.void
setTimeOut(long out)
It turns on the timeout.void
setTimeOutListener(TimeOutListener listener)
It sets the root of the TimeOutListener.void
setTimeOutMilliseconds(long out)
It turns on the timeout.void
setWrongDecisionsOut(long out)
It turns on the wrong decisions out.java.lang.String
toString()
java.lang.String
toStringFull()
-
-
-
Field Detail
-
debugAll
static final boolean debugAll
- See Also:
- Constant Field Values
-
respectSolutionListenerAdvice
public boolean respectSolutionListenerAdvice
If it is set to true then the optimizing search will quit the search if this action is indicated by the solution listener.
-
assignSolution
boolean assignSolution
It decides if the found solution is immediately assigned to the store.* If the solution is not assigned immediately after the search is concluded but later then special care may be required. As soon as search exits all propagations (including the first time consistency execution of the constraints) may be forgotten. Even worse some values of the variables for which the constraint was never aware of (not even at impose time) may appear back in the domain. The best remedy for this problem is to call store.consistency() method once and only once after the model is imposed and before the search is executed and never remove the level at which the store resides after store.consistency() method is executed.
-
backtracksOut
long backtracksOut
It specifies after how many backtracks the search exits.
-
backtracksOutCheck
boolean backtracksOutCheck
It specifies if the backtrack out is on.
-
check
boolean check
It specifies if search can exit before the search has finished.
-
cost
Constraint cost
It represents the constraint which enforces that next solution is better than currently best solution.
-
costValue
public int costValue
It represents the cost value of currently best solution for IntVar cost.
-
costValueFloat
public double costValueFloat
It represents the cost value of currently best solution for FloatVar cost.
-
costVariable
public Var costVariable
It represents the cost variable.
-
optimize
boolean optimize
-
decisions
int decisions
It stores number of nodes with decisions during search.
-
decisionsOut
long decisionsOut
It specifies after how many decisions the search exits.
-
decisionsOutCheck
boolean decisionsOutCheck
It specifies if the decisions out is on.
-
depth
int depth
It represents current depth of store used in search.
-
depthExcludePaths
int depthExcludePaths
It stores current depth of the search excluding paths in a search tree.
-
heuristic
SelectChoicePoint<T extends Var> heuristic
It represents the choice point selection heuristic.
-
exitChildListener
public ExitChildListener<T extends Var> exitChildListener
It is invoked when returning from left or right child.
-
consistencyListener
public ConsistencyListener consistencyListener
It is invoked when consistency function has been executed.
-
solutionListener
public SolutionListener<T extends Var> solutionListener
It is executed when a solution is found.
-
initializeListener
public InitializeListener initializeListener
It is executed when search is started, before entering the search.
-
maxDepth
int maxDepth
It stores the maximum depth reached during search.
-
maxDepthExcludePaths
int maxDepthExcludePaths
It stores the maximum depth of the search excluding paths.
-
nodes
int nodes
It stores number of nodes visited during search.
-
nodesOut
long nodesOut
It specifies after how many nodes the search exits.
-
nodesOutCheck
boolean nodesOutCheck
It specifies if the nodes out is on.
-
numberBacktracks
int numberBacktracks
It stores number of backtracks during search. A backtrack is a search node for which all children has failed.
-
printInfo
boolean printInfo
It decides if information about search is printed.
-
childSearches
public Search<? extends Var>[] childSearches
It stores searches which will be executed when this one has assign all its variables.
-
masterSearch
public Search<? extends Var> masterSearch
If this search is a sub-search then this pointer will point out to the master search (i.e. the search which have invoked this search).
-
store
public Store store
It represents store within which a search is performed.
-
timeOutListener
TimeOutListener timeOutListener
The object informed about the determination of the timeout.
-
exitListener
ExitListener exitListener
It is executed upon search exit. It allows to add learnt constraints.
-
timeOut
long timeOut
It specifies the exact time point after which the timeout will occur (in miliseconds).
-
timeOutCheck
boolean timeOutCheck
It specifies if the timeout is on.
-
timeOutOccured
public boolean timeOutOccured
It specifies that the time-out has occured
-
tOut
long tOut
It specifies the number of seconds after which the search will timeout.
-
wrongDecisions
int wrongDecisions
It stores number of wrong decisions during search. A wrong decision is a leaf of a search which has failed.
-
wrongDecisionsOut
long wrongDecisionsOut
It specifies after how many wrong decisions the search exits.
-
wrongDecisionsOutCheck
boolean wrongDecisionsOutCheck
It specifies if the wrong decisions out is on.
-
no
static java.util.concurrent.atomic.AtomicInteger no
-
id
public java.lang.String id
It specifies the id of the search.
-
einAinleftTree
public boolean einAinleftTree
It specifies if for setVar based search the left branch should impose EinA constraint.
-
currentChildSearch
public int currentChildSearch
It remembers what child search has been already examined.
-
-
Method Detail
-
setID
public void setID(java.lang.String name)
It sets the id of the store.- Parameters:
name
- the id of the store object.
-
id
public java.lang.String id()
Description copied from interface:Search
It returns the string id of the search.
-
setChildSearch
public void setChildSearch(Search<? extends Var>[] child)
Description copied from interface:Search
It specifies the sub-searches for the current search. In order for the current search to succeed at least one of those must succeed. If there are no sub-searches then the current search succeeds if all variables within select choice point object are assigned and all constraints attached to those variables are satisfied.- Specified by:
setChildSearch
in interfaceSearch<T extends Var>
- Parameters:
child
- the array containing all children searches.
-
addChildSearch
public void addChildSearch(Search<? extends Var> child)
Description copied from interface:Search
It adds another child search to this one.- Specified by:
addChildSearch
in interfaceSearch<T extends Var>
- Parameters:
child
- the search which is being added as child search.
-
setSelectChoicePoint
public void setSelectChoicePoint(SelectChoicePoint<T> select)
Description copied from interface:Search
It sets the select choice point object.- Specified by:
setSelectChoicePoint
in interfaceSearch<T extends Var>
- Parameters:
select
- the choice point heuristic used by search.
-
getBacktracks
public int getBacktracks()
It returns number of backtracks performed by the search.- Specified by:
getBacktracks
in interfaceSearch<T extends Var>
- Returns:
- the number of backtracks.
-
getDecisions
public int getDecisions()
It returns number of decisions performed by the search.- Specified by:
getDecisions
in interfaceSearch<T extends Var>
- Returns:
- the number of decisions.
-
getMaximumDepth
public int getMaximumDepth()
It returns the maximum depth reached by a search.- Specified by:
getMaximumDepth
in interfaceSearch<T extends Var>
- Returns:
- the maximum depth.
-
getNodes
public int getNodes()
It returns number of search nodes explored by the search.
-
getWrongDecisions
public int getWrongDecisions()
It returns number of wrong decisions performed by the search.- Specified by:
getWrongDecisions
in interfaceSearch<T extends Var>
- Returns:
- number of wrong decisions.
-
getSolution
public Domain[] getSolution()
Description copied from interface:Search
It returns the solution (an assignment of values to variables).- Specified by:
getSolution
in interfaceSearch<T extends Var>
- Returns:
- an array constituting the assignments.
-
getSolution
public Domain[] getSolution(int no)
Description copied from interface:Search
It returns the solution specified by the search. The first solution has an index 1.- Specified by:
getSolution
in interfaceSearch<T extends Var>
- Parameters:
no
- the solution we are interested in.- Returns:
- an array constituting the assignments.
-
getVariables
public T[] getVariables()
Description copied from interface:Search
It returns the order of variables used by functions returning a solution in terms of the values.- Specified by:
getVariables
in interfaceSearch<T extends Var>
- Returns:
- an array of variables as used by functions getSolution.
-
getSolutionListener
public SolutionListener<T> getSolutionListener()
Description copied from interface:Search
It returns the root Solution Listener.- Specified by:
getSolutionListener
in interfaceSearch<T extends Var>
- Returns:
- the root Solution Listener.
-
label
public boolean label(int firstVariable)
This function is called recursively to assign variables one by one.
-
setStore
public void setStore(Store store)
Description copied from interface:Search
It sets the reference to the store in the context of which the search operates.
-
setCostVar
public void setCostVar(Var cost)
Description copied from interface:Search
It sets the reference to the cost variable. It does not automatically mean that the search optimizes.- Specified by:
setCostVar
in interfaceSearch<T extends Var>
- Parameters:
cost
- variable used as a cost metric.
-
labeling
public boolean labeling()
It is a labeling function called if the search is a sub-search being called from the parent search. It never assigns a solution as it will be immediately retracted by search calling this one.
-
labeling
public boolean labeling(Store store, SelectChoicePoint<T> select)
Description copied from interface:Search
It performs search using supplied choice point selection heuristic.
-
setOptimizationForChildSearches
void setOptimizationForChildSearches(DepthFirstSearch s, Var costVar)
-
labeling
public boolean labeling(Store store, SelectChoicePoint<T> select, Var costVar)
Description copied from interface:Search
It performs search using supplied choice point selection heuristic, as well as costVariable as aim at finding an optimal solution.
-
setAssignSolution
public void setAssignSolution(boolean value)
It decides if a solution is assigned to store after search exits.- Specified by:
setAssignSolution
in interfaceSearch<T extends Var>
- Parameters:
value
- defines if solution is assigned.
-
setBacktracksOut
public void setBacktracksOut(long out)
It turns on the backtrack out.- Specified by:
setBacktracksOut
in interfaceSearch<T extends Var>
- Parameters:
out
- defines how many backtracks are performed before the search exits.
-
setDecisionsOut
public void setDecisionsOut(long out)
It turns on the decisions out.- Specified by:
setDecisionsOut
in interfaceSearch<T extends Var>
- Parameters:
out
- defines how many decisions are made before the search exits.
-
setNodesOut
public void setNodesOut(long out)
It turns on the nodes out.- Specified by:
setNodesOut
in interfaceSearch<T extends Var>
- Parameters:
out
- defines how many nodes are visited before the search exits.
-
setPrintInfo
public void setPrintInfo(boolean value)
It decides if information about search is printed.- Specified by:
setPrintInfo
in interfaceSearch<T extends Var>
- Parameters:
value
- defines if info is printed to standard output.
-
setTimeOut
public void setTimeOut(long out)
It turns on the timeout.- Specified by:
setTimeOut
in interfaceSearch<T extends Var>
- Parameters:
out
- defines how many seconds before the search exits.
-
setTimeOutMilliseconds
public void setTimeOutMilliseconds(long out)
Description copied from interface:Search
It turns on the timeout.- Specified by:
setTimeOutMilliseconds
in interfaceSearch<T extends Var>
- Parameters:
out
- defines how many miliseconds before the search exits.
-
setWrongDecisionsOut
public void setWrongDecisionsOut(long out)
It turns on the wrong decisions out.- Specified by:
setWrongDecisionsOut
in interfaceSearch<T extends Var>
- Parameters:
out
- defines how many wrong decisions are made before the search exits.
-
setMasterSearch
public void setMasterSearch(Search<? extends Var> master)
Description copied from interface:Search
If the search is called by a master search then the search may need to obtain some information about the master search. For example, the textual description of the solution.- Specified by:
setMasterSearch
in interfaceSearch<T extends Var>
- Parameters:
master
- master search which will be/is calling that slave search.
-
toString
public java.lang.String toString()
-
toStringFull
public java.lang.String toStringFull()
-
assignSolution
public boolean assignSolution()
Description copied from interface:Search
It assigns the last solution.- Specified by:
assignSolution
in interfaceSearch<T extends Var>
- Returns:
- true if the store is consistent after imposing the last solution.
-
assignSolution
public boolean assignSolution(int no)
Description copied from interface:Search
The first solution has index 0.- Specified by:
assignSolution
in interfaceSearch<T extends Var>
- Parameters:
no
- the solution number which we want to enforce in the store.- Returns:
- true if the store is consistent after imposing the solution.
-
getConsistencyListener
public ConsistencyListener getConsistencyListener()
Description copied from interface:Search
It returns the root of the Consistency Listener.- Specified by:
getConsistencyListener
in interfaceSearch<T extends Var>
- Returns:
- the root Consistency Listener.
-
getExitChildListener
public ExitChildListener<T> getExitChildListener()
Description copied from interface:Search
It returns the root of the ExitChildListener.- Specified by:
getExitChildListener
in interfaceSearch<T extends Var>
- Returns:
- the root of ExitChildListener.
-
getExitListener
public ExitListener getExitListener()
Description copied from interface:Search
It returns the root of the ExitListener.- Specified by:
getExitListener
in interfaceSearch<T extends Var>
- Returns:
- the root of ExitListener.
-
getTimeOutListener
public TimeOutListener getTimeOutListener()
Description copied from interface:Search
It returns the root of the TimeOutListener.- Specified by:
getTimeOutListener
in interfaceSearch<T extends Var>
- Returns:
- the root of the TimeOutListener.
-
setSolutionListener
public void setSolutionListener(SolutionListener<T> listener)
Description copied from interface:Search
It returns the root of the SolutionListener.- Specified by:
setSolutionListener
in interfaceSearch<T extends Var>
- Parameters:
listener
- the root of the SolutionListener.
-
setConsistencyListener
public void setConsistencyListener(ConsistencyListener listener)
Description copied from interface:Search
It sets the root of the Consistency Listener.- Specified by:
setConsistencyListener
in interfaceSearch<T extends Var>
- Parameters:
listener
- the new root.
-
setExitChildListener
public void setExitChildListener(ExitChildListener<T> listener)
Description copied from interface:Search
It sets the root of the ExitChild listener.- Specified by:
setExitChildListener
in interfaceSearch<T extends Var>
- Parameters:
listener
- the new root.
-
setExitListener
public void setExitListener(ExitListener listener)
Description copied from interface:Search
It sets the root of the Exit Listener.- Specified by:
setExitListener
in interfaceSearch<T extends Var>
- Parameters:
listener
- the new root.
-
setTimeOutListener
public void setTimeOutListener(TimeOutListener listener)
Description copied from interface:Search
It sets the root of the TimeOutListener.- Specified by:
setTimeOutListener
in interfaceSearch<T extends Var>
- Parameters:
listener
- the new root.
-
getInitializeListener
public InitializeListener getInitializeListener()
Description copied from interface:Search
It returns the root of the InitializationListener.- Specified by:
getInitializeListener
in interfaceSearch<T extends Var>
- Returns:
- the root of the InitializeListener.
-
setInitializeListener
public void setInitializeListener(InitializeListener listener)
Description copied from interface:Search
It sets the root of the InitializeListener.- Specified by:
setInitializeListener
in interfaceSearch<T extends Var>
- Parameters:
listener
- the new root.
-
printAllSolutions
public void printAllSolutions()
Description copied from interface:Search
It prints all solutions.- Specified by:
printAllSolutions
in interfaceSearch<T extends Var>
-
getCostVariable
public Var getCostVariable()
Description copied from interface:Search
It returns the cost variable.- Specified by:
getCostVariable
in interfaceSearch<T extends Var>
- Returns:
- cost variable.
-
getCostValue
public int getCostValue()
Description copied from interface:Search
It returns the value of the cost int variable for the best solution.- Specified by:
getCostValue
in interfaceSearch<T extends Var>
- Returns:
- the cost value.
-
getCostValueFloat
public double getCostValueFloat()
Description copied from interface:Search
It returns the value of the cost float variable for the best solution.- Specified by:
getCostValueFloat
in interfaceSearch<T extends Var>
- Returns:
- the cost value.
-
setOptimize
public void setOptimize(boolean value)
Description copied from interface:Search
It sets the optimization flag.- Specified by:
setOptimize
in interfaceSearch<T extends Var>
- Parameters:
value
- true if the search should optimize, false otherwise.
-
-