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 Object implements Search<T>
Implements Depth First Search with number of possible plugins (listeners) to be attached to modify the search.
Version:
4.10

  • Field Details

    • debugAll

      static final boolean debugAll
      See Also:

    • 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 AtomicInteger no

    • id

      public 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 Details

    • DepthFirstSearch

      public DepthFirstSearch()
      It specifies current child search.

  • Method Details

    • setID

      public void setID(String name)
      It sets the id of the store.
      Parameters:
      name - the id of the store object.

    • id

      public 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(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 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.

    • setOptimizationForChildSearches

      void setOptimizationForChildSearches(DepthFirstSearch<T> 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.
      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.

    • setTimeOutMilliseconds

      public void setTimeOutMilliseconds(long out)
      Description copied from interface: Search
      It turns on the timeout.
      Specified by:
      setTimeOutMilliseconds in interface Search<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 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 String toString()
      Specified by:
      toString in interface Search<T extends Var>
      Overrides:
      toString in class Object

    • toStringFull

      public String toStringFull()

    • 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 Var 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 int variable for the best solution.
      Specified by:
      getCostValue in interface Search<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 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.