home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / tlx501.zip / SRC / CSPREP.CPP < prev    next >
C/C++ Source or Header  |  1996-07-08  |  12KB  |  363 lines
  1. /****************************************************************************
  2.     $Id: csprep.cpp 501.0 1995/03/07 12:26:12 RON Exp $
  3.  
  4.     Copyright (c) 1991-95 Tarma Software Research. All rights reserved.
  5.  
  6.     Project:    Tarma Library for C++ V5.0
  7.     Author:    Ron van der Wal
  8.  
  9.     Implementation of class TLCSProblemRep, the standard problem
  10.     representation class for CSPs.
  11.  
  12.     $Log: csprep.cpp $
  13.     Revision 501.0  1995/03/07 12:26:12  RON
  14.     Updated for TLX 5.01
  15.     Revision 1.14  1995/02/22 12:35:44  RON
  16.     Update for release 012
  17.     Added partial support for SunPro C++ compiler
  18.     Revision 1.13  1995/01/16  12:24:43  ron
  19.     Added subproblem parameter to varselectors
  20.  
  21.     Revision 1.12  1995/01/13  15:32:09  ron
  22.     Moved a number of processing steps to the subproblem
  23.  
  24.     Revision 1.11  1995/01/12  13:39:07  ron
  25.     Adapted to previous Searcher/ProblemRep model
  26.  
  27.     Revision 1.10  1995/01/10  16:32:03  ron
  28.     Added warning when no variables are created
  29.  
  30.     Revision 1.9  1995/01/08  11:43:55  ron
  31.     Renamed TLCSProblem to TLCSSubProblem
  32.  
  33.     Revision 1.8  1995/01/06  15:56:46  ron
  34.     Adapted to new Searcher/Problem model
  35.  
  36.     Revision 1.7  1995/01/05  15:22:53  ron
  37.     Added TLVarSelector classes
  38.     Brought inline with thesis
  39.  
  40.     Revision 1.6  1994/11/16  15:37:52  ron
  41.     Added module info; rearranged #include directives
  42.  
  43.     Revision 1.5  1994/10/13  11:50:46  ron
  44.     Changed strategy names slightly
  45.     Added |C|/(|D|^2) strategy
  46.  
  47.     Revision 1.4  1994/10/11  19:02:46  ron
  48.     Replaced DeadEnd() + SolveProblem() by ProcessProblem()
  49.  
  50.     Revision 1.3  1994/10/10  16:47:51  ron
  51.     Added dead-end detection, preprocess check, and implementation
  52.     of selection strategies
  53.  
  54.     Revision 1.2  1994/10/07  17:05:52  ron
  55.     Implemented various selection strategies
  56.  
  57.     Revision 1.1  1994/10/05  18:43:06  ron
  58.     Initial revision
  59.  
  60. ****************************************************************************/
  61.  
  62. #include <tlx\501\_build.h>
  63.  
  64. TLX_MODULE_INFO("$Revision: 501.0 $");
  65.  
  66. #include <iostream.h>
  67.  
  68. #include <tlx\501\log.h>
  69. #include <tlx\501\solve\stdcsp.h>
  70.  
  71. //-----    Template source code
  72.  
  73. #include <tlx\501\template\ptrseq.cpp>
  74.  
  75. /*-------------------------------------------------------------------------*/
  76.     TLCSProblemRep::TLCSProblemRep()
  77.  
  78. /*  Constructor.
  79. ---------------------------------------------------------------------------*/
  80. : mVars(100,100), mFreeVars()
  81. {
  82.     mPropagator  = 0;
  83.     mVarSelector = 0;
  84.  
  85.     mVars.BecomeOwner(true);        // Will delete variables
  86. }
  87.  
  88. /*-------------------------------------------------------------------------*/
  89.     void TLCSProblemRep::EnterState(TLProblemState *aProblem)
  90.  
  91. /*  Implements the processing step required from problem representation
  92.     classes. The variable assignment is performed.
  93. ---------------------------------------------------------------------------*/
  94. {
  95.     TLX_TRACE(TLX, (55, "CSProblemRep: EnterState"));
  96.  
  97.     TLCSProblemState *csproblem = DYNACAST(TLCSProblemState *, aProblem);
  98.     TLX_ASSERT_PTR(csproblem);
  99.     TLX_ASSERT_PTR(csproblem->Var());
  100.  
  101.     // Remove the variable from the set of free variables
  102.  
  103.     TLX_ASSERT(mFreeVars.Contains(csproblem->Var()));
  104.     mFreeVars.Extract(csproblem->Var());
  105.  
  106.     // Before the assignment takes place, save the current domain. After the
  107.     // assignment, capturing is activated; this remains in effect until the
  108.     // corresponding LeaveState().
  109.  
  110.     TLX_ASSERT(csproblem->Var()->IsActive());
  111.  
  112.     csproblem->SaveDomain();
  113.     csproblem->AssignVariable();
  114.     csproblem->StartCapturing();
  115. }
  116.  
  117. /*-------------------------------------------------------------------------*/
  118.     size_t TLCSProblemRep::GenerateBranches(
  119.         TLProblemState *    aParent,
  120.     TLProblemList &        aList)
  121.  
  122. /*  Called to decompose the given subproblem, which will act as the parent
  123.     for the new branches. If there are no free variables, this function
  124.     returns false, else it calls SelectVariable() to select the next
  125.     variable and CreateBranches() to create the branches for that variable.
  126. ---------------------------------------------------------------------------*/
  127. {
  128.     TLX_TRACE(TLX, (55, "CSProblemRep: GenerateBranches"));
  129.  
  130.     if (mFreeVars.IsEmpty())
  131.     return 0;
  132.  
  133.     TLCSProblemState *csproblem = DYNACAST(TLCSProblemState *, aParent);
  134.     TLX_ASSERT(!aParent || csproblem);
  135.  
  136.     TLVariable *var = SelectVariable(csproblem);
  137.     if (!var)
  138.     {
  139.     TLX_TRACE_WARN(TLX, ("No variable selected from free variables"));
  140.     return false;
  141.     }
  142.  
  143.     return CreateBranches(csproblem, var, aList);
  144. }
  145.  
  146. /*-------------------------------------------------------------------------*/
  147.     void TLCSProblemRep::LeaveState(TLProblemState *aProblem)
  148.  
  149. /*  Called after processing of the subproblem has been completed. This
  150.     version uses the information captured by the underlying CSProblem to
  151.     undo the changes that were made during the processing.
  152. ---------------------------------------------------------------------------*/
  153. {
  154.     TLX_TRACE(TLX, (55, "CSProblemRep: LeaveState"));
  155.  
  156.     TLCSProblemState *csproblem = DYNACAST(TLCSProblemState *, aProblem);
  157.     TLX_ASSERT_PTR(csproblem);
  158.     TLX_ASSERT_PTR(csproblem->Var());
  159.  
  160.     // Undo changes to all domains captured by this subproblem and
  161.     // reactivate the constraints on the variable. The order is the
  162.     // exact opposite of the processing order.
  163.  
  164.     csproblem->Var()->ActivateConstraints();
  165.     csproblem->DoneVariable();
  166.     csproblem->StopCapturing();
  167.     csproblem->RestoreDomains();
  168.  
  169.     TLX_ASSERT(csproblem->Var()->IsActive());
  170.  
  171.     // Return the variable to the set of free variables
  172.  
  173.     TLX_ASSERT(!mFreeVars.Contains(csproblem->Var()));
  174.     mFreeVars.Append(csproblem->Var());
  175. }
  176.  
  177. /*-------------------------------------------------------------------------*/
  178.     bool TLCSProblemRep::PreProcess()
  179.  
  180. /*  Preprocessing step. Initializes the list of free variables. If derived
  181.     classes override this function, they should call this version as part
  182.     of their own preprocessing.
  183. ---------------------------------------------------------------------------*/
  184. {
  185.     TLX_TRACE(TLX, (55, "CSProblemRep: PreProcess"));
  186.  
  187.     if (!TLProblemRep::PreProcess())
  188.     return false;
  189.  
  190.     // Discard previous set of variables, if any
  191.  
  192.     mVars.RemoveAll();
  193.  
  194.     // Let the derived class create the set of variables
  195.  
  196.     if (!CreateVariables())
  197.     return false;
  198.  
  199.     mFreeVars = mVars;
  200.  
  201.     // Perform initial propagation
  202.  
  203.     return PreProcessVariables();
  204. }
  205.  
  206. /*-------------------------------------------------------------------------*/
  207.     bool TLCSProblemRep::PreProcessVariables()
  208.  
  209. /*  Substep of general preprocessing: preprocesses all variables that were
  210.     created earlier. By default, this function applies the propagation
  211.     strategy object to the set of all variables.
  212. ---------------------------------------------------------------------------*/
  213. {
  214.     TLX_TRACE(TLX, (55, "CSProblemRep: PreProcessVariables"));
  215.  
  216.     if (mPropagator)
  217.     {
  218.         TLX_LOG_ENTRY("Preprocessing all variables");
  219.  
  220. #ifdef __IBMCPP__
  221.     TLPtrSeqIter<TLVariable> it(mVars);
  222.         bool result = mPropagator->Propagate(it);
  223. #else
  224.         bool result = mPropagator->Propagate(TLPtrSeqIter<TLVariable>(mVars));
  225. #endif
  226.         TLPropagator::Stats stats;
  227.         mPropagator->GetStats(stats);
  228.  
  229.     TLX_LOG_ENTRY("Propagation completed; %ld checks", stats.mCheckCount);
  230.         return result;
  231.     }
  232.     else
  233.         return true;
  234. }
  235.  
  236. /*-------------------------------------------------------------------------*/
  237.     ostream &TLCSProblemRep::PrintOn(ostream &os) const
  238.  
  239. /*  Prints the current state of the problem representation.
  240. ---------------------------------------------------------------------------*/
  241. {
  242.     os << mVars.Count() << " variables (" << mFreeVars.Count()
  243.         << " still free):\n";
  244.  
  245.     for (index_t i = mVars.Mini(); i <= mVars.Maxi(); ++i)
  246.     {
  247.     TLVariable *var = mVars.PeekAt(i);
  248.     if (var)
  249.     {
  250.         os << *var;
  251.         if (mFreeVars.Contains(var))
  252.         os << " -- Free";
  253.         os << "\n";
  254.     }
  255.     else
  256.         os << "*** NULL variable ***\n";
  257.     }
  258.     ReportStats(os);
  259.     return os;
  260. }
  261.  
  262. /*-------------------------------------------------------------------------*/
  263.     bool TLCSProblemRep::Process(TLProblemState *aProblem)
  264.  
  265. /*  Implements the processing step required from problem representation
  266.     classes. Constraint propagation with a consistency check.
  267. ---------------------------------------------------------------------------*/
  268. {
  269.     TLX_TRACE(TLX, (55, "CSProblemRep: Process"));
  270.  
  271.     TLCSProblemState *csproblem = DYNACAST(TLCSProblemState *, aProblem);
  272.     TLX_ASSERT_PTR(csproblem);
  273.     TLX_ASSERT_PTR(csproblem->Var());
  274.  
  275.     // Perform propagation-like processing, first locally, then globally.
  276.  
  277.     bool result = csproblem->ProcessVariable() && Propagate(csproblem);
  278.  
  279.     // Deactivate the constraints emanating from the variable
  280.  
  281.     csproblem->Var()->DeactivateConstraints();
  282.  
  283.     return result;
  284. }
  285.  
  286. /*-------------------------------------------------------------------------*/
  287.     bool TLCSProblemRep::Propagate(TLCSProblemState *aProblem)
  288.  
  289. /*  Checks the consistency of the system after the given variable has been
  290.     assigned. This implementation uses the currently installed propagator
  291.     (if any). It assumes that domain capturing has been activated elsewhere.
  292. ---------------------------------------------------------------------------*/
  293. {
  294.     TLX_TRACE(TLX, (55, "CSProblemRep: Propagate"));
  295.     TLX_ASSERT_PTR(aProblem);
  296.  
  297.     if (mPropagator)
  298.     return mPropagator->Propagate(aProblem->Var());
  299.     else
  300.     {
  301.     // If there are no more free variables, we must test the complete
  302.     // assignment. In that case, it is unwise to rely on this version
  303.     // if there is no propagator.
  304.  
  305.     if (mFreeVars.IsEmpty())
  306.         TLX_TRACE_WARN(TLX, ("No consistency check after instantiation"));
  307.  
  308.     return true;
  309.     }
  310. }
  311.  
  312. /*-------------------------------------------------------------------------*/
  313.     TLVariable *TLCSProblemRep::SelectVariable(TLCSProblemState *aProblem)
  314.  
  315. /*  Selects the next variable to explore as the branches of the given
  316.     parent subproblem. It applies the selection strategy that is
  317.     currently set and returns a pointer to the selected variable. The
  318.     variable is *not* removed from the list of free variables.
  319.  
  320.     If there is no selection strategy, the first free variable is selected.
  321. ---------------------------------------------------------------------------*/
  322. {
  323.     TLX_TRACE(TLX, (55, "CSProblemRep: SelectVariable"));
  324.  
  325.     if (mFreeVars.IsEmpty())
  326.     return 0;
  327.     else if (mVarSelector)
  328.     return mVarSelector->SelectVariable(aProblem, this, mFreeVars);
  329.     else
  330.     return mFreeVars.PeekFirst();
  331. }
  332.  
  333. /*-------------------------------------------------------------------------*/
  334.     TLPropagator *TLCSProblemRep::SetPropagator(TLPropagator *aProp)
  335.  
  336. /*  Installs a new propagation strategy object and returns the previous one.
  337. ---------------------------------------------------------------------------*/
  338. {
  339.     if (!aProp)
  340.     TLX_TRACE_WARN(TLX, ("NULL propagation strategy installed"));
  341.  
  342.     TLPropagator *old = mPropagator;
  343.     mPropagator       = aProp;
  344.  
  345.     return old;
  346. }
  347.  
  348. /*-------------------------------------------------------------------------*/
  349.     TLVarSelector *TLCSProblemRep::SetVarSelector(TLVarSelector *aSelect)
  350.  
  351. /*  Installs a new variable selection strategy and returns the previous one.
  352. ---------------------------------------------------------------------------*/
  353. {
  354.     if (!aSelect)
  355.     TLX_TRACE_WARN(TLX, ("NULL selection strategy installed"));
  356.  
  357.     TLVarSelector *old = mVarSelector;
  358.     mVarSelector       = aSelect;
  359.  
  360.     return old;
  361. }
  362.  
  363.