home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / tlx501.zip / SRC / PROPAC3.CPP < prev    next >
C/C++ Source or Header  |  1996-07-08  |  10KB  |  279 lines
  1. /****************************************************************************
  2.     $Id: propac3.cpp 501.0 1995/03/07 12:26:18 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 the TLPropagatorAC3 class. This class implements
  10.     the AC-3 arc consistency algorithm.
  11.  
  12.     $Log: propac3.cpp $
  13.     Revision 501.0  1995/03/07 12:26:18  RON
  14.     Updated for TLX 5.01
  15.     Revision 1.15  1995/02/28 15:12:40  RON
  16.     Update for release 012
  17.     Added partial support for SunPro C++ compiler
  18.     Revision 1.14  1995/01/06  15:58:07  ron
  19.     Corrected Revision keyword
  20.  
  21.     Revision 1.13  1995/01/05  15:26:34  ron
  22.     Added standard Propagate() functions
  23.  
  24.     Revision 1.12  1994/11/16  15:41:45  ron
  25.     Added module info; rearranged #include directives
  26.  
  27.     Revision 1.11  1994/10/10  16:53:04  ron
  28.     Changed to <tlx\solve\csp.h>
  29.  
  30.     Revision 1.10  1994/10/07  17:02:51  ron
  31.     Changed Unregister...() to Deregister...()
  32.  
  33.     Revision 1.9  1994/10/05  18:41:31  ron
  34.     Changed from collections to iterators
  35.  
  36.     Revision 1.8  1994/09/28  14:20:06  ron
  37.     Removed Macintosh-style #include references
  38.  
  39.     Revision 1.7  1994/09/27  20:22:41  ron
  40.     Changed path separator from / to \
  41.  
  42.     Revision 1.6  1994/09/26  15:44:22  ron
  43.     Adapted to changes in constraint check counting
  44.     Implemented support to remember first failed constraint
  45.  
  46.     Revision 1.5  1994/09/13  10:13:09  ron
  47.     Added call to reset the failed constraint pointer prior to
  48.     the propagation process.
  49.  
  50.     Revision 1.4  1994/09/07  15:43:21  ron
  51.     No changes
  52.  
  53.     Revision 1.3  1994/09/06  20:26:57  ron
  54.     Changed template source code #include from queue.cpp to ptrqueue.cpp
  55.  
  56.     Revision 1.2  1994/09/06  14:08:45  ron
  57.     Adapted to changes in CSP framework
  58.  
  59.     Revision 1.1  1994/08/16  18:13:06  ron
  60.     Initial revision
  61.  
  62. ****************************************************************************/
  63.  
  64. #include <tlx\501\_build.h>
  65.  
  66. TLX_MODULE_INFO("$Revision: 501.0 $");
  67.  
  68. //----- System headers
  69.  
  70. #include <iostream.h>
  71.  
  72. //----- Project headers
  73.  
  74. #include <tlx\501\solve\csp.h>
  75.  
  76. /*---------------------------------------------------------------------------
  77.     Template source code
  78. ---------------------------------------------------------------------------*/
  79.  
  80. #if defined(THINK_CPLUS)
  81.     // Templates are in a separate file because of segment size
  82. #elif defined(__BORLANDC__) || defined(_MSC_VER) || defined(__SC__) || defined(__WATCOMC__)
  83.     #include <tlx\501\template\ptriter.cpp>
  84.     #include <tlx\501\template\ptrqueue.cpp>
  85.     #include <tlx\501\template\ptrseq.cpp>
  86. #elif defined(__SUNPRO_CC)
  87.     #include <tlx\501\template\ptriter.cpp>
  88.     #include <tlx\501\template\ptrqueue.cpp>
  89.     #include <tlx\501\template\ptrseq.cpp>
  90. #elif defined(__IBMCPP__)
  91.   #if __IBMCPP__ < 300
  92.     #pragma implementation("tlx\\template\\ptriter.cpp")
  93.     #pragma implementation("tlx\\template\\ptrqueue.cpp")
  94.     #pragma implementation("tlx\\template\\ptrseq.cpp")
  95.   #else
  96.     #include <tlx\501\template\ptriter.cpp>
  97.     #include <tlx\501\template\ptrqueue.cpp>
  98.     #include <tlx\501\template\ptrseq.cpp>
  99.   #endif
  100. #else
  101.     #error Unsupported compiler; contact Tarma Software Research
  102. #endif
  103.  
  104. /*-------------------------------------------------------------------------*/
  105.     TLPropagatorAC3::TLPropagatorAC3()
  106.  
  107. /*  Constructor. Initializes the propagator.
  108. ---------------------------------------------------------------------------*/
  109. : TLPropagator(), mChanges(50, 50)
  110. {
  111. }
  112.  
  113. /*-------------------------------------------------------------------------*/
  114.     bool TLPropagatorAC3::CheckAC3(TLVariable &aVar)
  115.  
  116. /*  Performs the arc consistency algorithm starting from the given variable.
  117.  
  118.     The function returns nonzero if the system is consistent, else zero.
  119. ---------------------------------------------------------------------------*/
  120. {
  121.     TLVariable *var = &aVar;
  122. #ifdef __IBMCPP__
  123.     TLPtrItemIter<TLVariable> it1(var);
  124.     TLPtrIter<TLVariable> it2;
  125.     return PerformAC3(it1, it2, true);
  126. #else
  127.     return PerformAC3(TLPtrItemIter<TLVariable>(var),
  128.                   TLPtrIter<TLVariable>(), true);
  129. #endif
  130. }
  131.  
  132. /*-------------------------------------------------------------------------*/
  133.     bool TLPropagatorAC3::CheckAC3(TLPtrIter<TLVariable> &vars)
  134.  
  135. /*  Performs the arc consistency algorithm on the variables in 'vars'. It
  136.     is an adaption of Mackworth's AC-3 algorithm, modified for operation
  137.     within the general CSP framework.
  138.  
  139.     NOTE: In contrast to AC-3, we do not perform node consistency first. It
  140.     is assumed that this has been done previously, and it doesn't make
  141.     sense to execute a node consistency algorithm more than once.
  142.  
  143.     The function returns nonzero if the system is consistent, else zero.
  144. ---------------------------------------------------------------------------*/
  145. {
  146. #ifdef __IBMCPP__
  147.     TLPtrIter<TLVariable> it;
  148.     return PerformAC3(vars, it, true);
  149. #else
  150.     return PerformAC3(vars, TLPtrIter<TLVariable>(), true);
  151. #endif
  152. }
  153.  
  154. /*-------------------------------------------------------------------------*/
  155.     bool TLPropagatorAC3::CheckAC3Set(
  156.         TLPtrIter<TLVariable> &    seeds,    // Initially changed vars
  157.         TLPtrIter<TLVariable> &    range   // Set of vars for propagation
  158.     )
  159.  
  160. /*  Propagates the effects of constraints that originate with the given set
  161.     of variables. Constraint propagation continues until an inconsistency
  162.     is detected or no more changes occur. Only variables within the
  163.     original set are considered for constraint propagation, although
  164.     other variables may be modified as well.
  165. ---------------------------------------------------------------------------*/
  166. {
  167.     return PerformAC3(seeds, range, false);
  168. }
  169.  
  170. /*-------------------------------------------------------------------------*/
  171.     const char *TLPropagatorAC3::Description() const
  172.  
  173. /*  Returns a description of the propagation algorithm.
  174. ---------------------------------------------------------------------------*/
  175. {
  176.     return "AC-3 propagation";
  177. }
  178.  
  179. /*-------------------------------------------------------------------------*/
  180.     bool TLPropagatorAC3::PerformAC3(
  181.         TLPtrIter<TLVariable> &    seeds,  // Initially changed vars
  182.         TLPtrIter<TLVariable> &    range,  // Set of vars for propagation
  183.         bool                    global    // true = progate all vars
  184.     )
  185.  
  186. /*  Helper function that executes actual constraint propagation algorithm.
  187.     It starts by propagating constraints that originate with the given
  188.     set, but it will keep propagating until an inconsistency is detected
  189.     or no more changes occur.
  190.  
  191.     The 'global' flag indicates whether or not changes to variables
  192.     outside the original set should be propagated as well. If this flag
  193.     is nonzero, they will.
  194. ---------------------------------------------------------------------------*/
  195. {
  196.     // 'evalq' will hold the variables that have changed. Initially, it
  197.     // contains all variables passed along as a parameter to the function,
  198.     // but during the execution of the algorithm variables are removed from
  199.     // it. It may also happen that variables are added again.
  200.  
  201.     TLPtrQueue<TLVariable> evalq(seeds);
  202.     TLX_ASSERT(evalq.Count() == seeds.Count());
  203.     evalq.SetDelta(100);
  204.  
  205.     SetFailedConstraint(0);
  206.     mChanges.RemoveAll();               // Just to be sure
  207.     RegisterPropagator();        // Register current instance
  208.  
  209.     bool result = true;            // Assume success
  210.     int32 ccnt = TLConstraint::CheckCount();
  211.  
  212.     while (!evalq.IsEmpty())
  213.     {
  214.         // Get the next variable
  215.     TLVariable *curvar = evalq.Dequeue();
  216.  
  217.     // Ask the variable to propagate its changes
  218.     if (!curvar->PropagateChanges())
  219.     {
  220.             // The domain has become empty ==> inconsistent
  221.             TLX_TRACE(TLX, (60, "Inconsistency - Exiting evaluation loop"));
  222.             result = false;
  223.         break;
  224.     }
  225.  
  226.         // Check whether any changes have been made. If so, add the
  227.         // variables to the evaluation queue.
  228.  
  229.         while (!mChanges.IsEmpty())
  230.         {
  231.             // Check if we must consider this variable
  232.             TLVariable *var = mChanges.Dequeue();
  233.             if (global || range.Contains(var))
  234.         evalq.EnqueueUnique(var);
  235.         }
  236.     }
  237.  
  238.     mStats.mCheckCount += TLConstraint::CheckCount() - ccnt;
  239.     DeregisterPropagator();
  240.  
  241.     return result;
  242. }
  243.  
  244. /*-------------------------------------------------------------------------*/
  245.     bool TLPropagatorAC3::Propagate(TLVariable *aVar)
  246.  
  247. /*  Standard propagation function for all propagators. It must propagate
  248.     the effects of changes to 'aVar'.
  249. ---------------------------------------------------------------------------*/
  250. {
  251.     TLX_ASSERT_PTR(aVar);
  252.  
  253.     return CheckAC3(*aVar);
  254. }
  255.  
  256. /*-------------------------------------------------------------------------*/
  257.     bool TLPropagatorAC3::Propagate(TLPtrIter<TLVariable> &aSeed)
  258.  
  259. /*  Standard propagation function for all propagators. It must propagate
  260.     the effects of changes to all variables in 'aSeed'.
  261. ---------------------------------------------------------------------------*/
  262. {
  263.     return CheckAC3(aSeed);
  264. }
  265.  
  266. /*-------------------------------------------------------------------------*/
  267.     void TLPropagatorAC3::RegisterChanges(TLVariable *var)
  268.  
  269. /*  Makes changes to a variable permanent. This involves the creation of
  270.     a (temporary) record of the variable and the changes made to it, in order
  271.     to determine what constraints will have to be revised later on.
  272. ---------------------------------------------------------------------------*/
  273. {
  274.     TLX_ASSERT_PTR(var);
  275.     mChanges.Enqueue(var);
  276.     TLX_TRACE(TLX, (70, "Changes to variable %s registered", var->GetName()));
  277. }
  278.  
  279.