JaCoP.search
Class DepthFirstSearch<T extends Var>

java.lang.Object
  JaCoP.search.DepthFirstSearch<T>

Type Parameters:

T - type of variables used in this search.

All Implemented Interfaces:

Search<T>

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.

Author:

Radoslaw Szymanek and Krzysztof Kuchcinski

Field Summary

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.
int	costValue It represents the cost value of currently best solution.
IntVar	costVariable It represents the cost variable.
int	currentChildSearch It remembers what child search has been already examined.
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.
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.
boolean	respectSolutionLimitInOptimization 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.
boolean	timeOutOccured It specifies that the time-out has occured

Constructor Summary

DepthFirstSearch()
It specifies current child search.

Method Summary

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 variable for the best solution.
IntVar	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, IntVar 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(IntVar 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.
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	setWrongDecisionsOut(long out) It turns on the wrong decisions out.
java.lang.String	toString()

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

respectSolutionLimitInOptimization

public boolean respectSolutionLimitInOptimization

If it is set to true then the optimizing search will quit the search if this action is indicated by the solution listener.

costValue

public int costValue

It represents the cost value of currently best solution.

costVariable

public IntVar costVariable

It represents the cost variable.

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.

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).

timeOutOccured

public boolean timeOutOccured

It specifies that the time-out has occured

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.

Constructor Detail

DepthFirstSearch

public DepthFirstSearch()

It specifies current child search.

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.

Specified by:

id in interface Search<T extends Var>

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 interface Search<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 interface Search<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 interface Search<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 interface Search<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 interface Search<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 interface Search<T extends Var>

Returns:

the maximum depth.

getNodes

public int getNodes()

It returns number of search nodes explored by the search.

Specified by:

getNodes in interface Search<T extends Var>

Returns:

number of search nodes.

getWrongDecisions

public int getWrongDecisions()

It returns number of wrong decisions performed by the search.

Specified by:

getWrongDecisions in interface Search<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 interface Search<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 interface Search<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 interface Search<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 interface Search<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.

Specified by:

label in interface Search<T extends Var>

Parameters:

firstVariable - the index to the first variable which has not been grounded yet.

Returns:

true if the solution was found.

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.

Specified by:

setStore in interface Search<T extends Var>

Parameters:

store - the store in which context the search operates.

setCostVar

public void setCostVar(IntVar 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 interface Search<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.

Specified by:

labeling in interface Search<T extends Var>

Returns:

true if the solution was found.

labeling

public boolean labeling(Store store,
                        SelectChoicePoint<T> select)

Description copied from interface: Search

It performs search using supplied choice point selection heuristic.

Specified by:

labeling in interface Search<T extends Var>

Parameters:

store - the store within which the search is conducted.

select - the selection choice point heuristic.

Returns:

true if the solution was found.

labeling

public boolean labeling(Store store,
                        SelectChoicePoint<T> select,
                        IntVar 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.

Specified by:

labeling in interface Search<T extends Var>

Parameters:

store - constraint store which will be used by labeling.

select - the selection choice point heuristic.

costVar - variable to specify cost.

Returns:

true if the solution was found.

setAssignSolution

public void setAssignSolution(boolean value)

It decides if a solution is assigned to store after search exits.

Specified by:

setAssignSolution in interface Search<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 interface Search<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 interface Search<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 interface Search<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 interface Search<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 interface Search<T extends Var>

Parameters:

out - defines how many seconds before the search exits.

setWrongDecisionsOut

public void setWrongDecisionsOut(long out)

It turns on the wrong decisions out.

Specified by:

setWrongDecisionsOut in interface Search<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 interface Search<T extends Var>

Parameters:

master - master search which will be/is calling that slave search.

toString

public java.lang.String toString()

Specified by:

toString in interface Search<T extends Var>

Overrides:

toString in class java.lang.Object

assignSolution

public boolean assignSolution()

Description copied from interface: Search

It assigns the last solution.

Specified by:

assignSolution in interface Search<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 interface Search<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 interface Search<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 interface Search<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 interface Search<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 interface Search<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 interface Search<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 interface Search<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 interface Search<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 interface Search<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 interface Search<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 interface Search<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 interface Search<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 interface Search<T extends Var>

getCostVariable

public IntVar getCostVariable()

Description copied from interface: Search

It returns the cost variable.

Specified by:

getCostVariable in interface Search<T extends Var>

Returns:

cost variable.

getCostValue

public int getCostValue()

Description copied from interface: Search

It returns the value of the cost variable for the best solution.

Specified by:

getCostValue in interface Search<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 interface Search<T extends Var>

Parameters:

value - true if the search should optimize, false otherwise.