home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / tlx501.zip / SRC / PROPAC6.CPP < prev    next >
C/C++ Source or Header  |  1996-07-04  |  10KB  |  315 lines
  1. /****************************************************************************
  2.     $Id: propac6.cpp 501.0 1995/03/07 12:26:20 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 AC-6 constraint propagation algorithm.
  10.  
  11.     $Log: propac6.cpp $
  12.     Revision 501.0  1995/03/07 12:26:20  RON
  13.     Updated for TLX 5.01
  14.     Revision 1.10  1995/02/28 15:13:08  RON
  15.     Update for release 012
  16.     Added partial support for SunPro C++ compiler
  17.     Revision 1.9  1995/01/06  15:58:09  ron
  18.     Corrected Revision keyword
  19.  
  20.     Revision 1.8  1995/01/05  15:26:52  ron
  21.     Renamed tracing macro
  22.  
  23.     Revision 1.7  1994/11/16  15:41:52  ron
  24.     Adapted to group-style tracing
  25.     Added module info; rearranged #include directives
  26.  
  27.     Revision 1.6  1994/10/10  16:53:19  ron
  28.     Changed to <tlx\solve\ac6.h>
  29.  
  30.     Revision 1.5  1994/10/05  18:41:48  ron
  31.     Renamed TLx...() functions to tl...()
  32.  
  33.     Revision 1.4  1994/09/28  14:20:14  ron
  34.     Removed Macintosh-style #include references
  35.  
  36.     Revision 1.3  1994/09/27  20:22:43  ron
  37.     Changed path separator from / to \
  38.  
  39.     Revision 1.2  1994/09/26  15:44:56  ron
  40.     Changed include file references
  41.  
  42.     Revision 1.1  1994/08/16  18:13:07  ron
  43.     Initial revision
  44.  
  45. ****************************************************************************/
  46.  
  47. #include <tlx\501\_build.h>
  48.  
  49. TLX_MODULE_INFO("$Revision: 501.0 $");
  50.  
  51. #include <tlx\501\solve\ac6.h>
  52.  
  53. /*---------------------------------------------------------------------------
  54.     Template source code
  55. ---------------------------------------------------------------------------*/
  56.  
  57. #if defined(THINK_CPLUS)
  58.     #include "assoc.cpp"
  59.     #include "ptrseq.cpp"
  60.     #include "queue.cpp"
  61.     #pragma template_access public
  62.     #pragma template TLAssoc<TLVariableAC6 *, TLDomainElement>
  63.     #pragma template TLPtrSeq<TLVariableAC6>
  64.     #pragma template TLQueue<TLDomainRemoval>
  65. #elif defined(__BORLANDC__) || defined(__SC__) || defined(__WATCOMC__)
  66.     #include <tlx\501\template\assoc.cpp>
  67.     #include <tlx\501\template\ptrseq.cpp>
  68.     #include <tlx\501\template\queue.cpp>
  69. #elif defined(__SUNPRO_CC)
  70.     #include <tlx\501\template\assoc.cpp>
  71.     #include <tlx\501\template\ptrseq.cpp>
  72.     #include <tlx\501\template\queue.cpp>
  73. #elif defined(__IBMCPP__)
  74.   #if __IBMCPP__ < 300
  75.     #pragma implementation("tlx\\template\\assoc.cpp")
  76.     #pragma implementation("tlx\\template\\ptrseq.cpp")
  77.     #pragma implementation("tlx\\template\\queue.cpp")
  78.   #else
  79.     #include <tlx\501\template\assoc.cpp>
  80.     #include <tlx\501\template\ptrseq.cpp>
  81.     #include <tlx\501\template\queue.cpp>
  82.   #endif
  83. #else
  84.     #error Unsupported compiler; contact Tarma Software Research
  85. #endif
  86.  
  87. /*-------------------------------------------------------------------------*/
  88.     TLPropagatorAC6::TLPropagatorAC6()
  89.  
  90. /*  Default constructor.
  91. ---------------------------------------------------------------------------*/
  92. : TLPropagator()
  93. {
  94. }
  95.  
  96. /*-------------------------------------------------------------------------*/
  97.     bool TLPropagatorAC6::CheckAC6(const TLPtrSeq<TLVariable> &aVarSet)
  98.  
  99. /*  Performs the AC-6 constraint propagation algorithm on the given set
  100.     of variables. Returns nonzero if the variable configuration is
  101.     consistent, else zero.
  102.  
  103.     This function is an adaptation of the algorithm as published in:
  104.  
  105.     C. Bessiere: Arc-consistency and arc-consistency again, AI 65 (1994),
  106.              pp. 179-190.
  107. ---------------------------------------------------------------------------*/
  108. {
  109.     // Build a list of all constraints connecting the given set of variables.
  110.     // Constraints that end outside this set are not taken into account.
  111.     //
  112.     // At the same time, we are clearing all support lists of the variables.
  113.  
  114.     TLPtrSeq<TLConstraintAC6>     constraints(aVarSet.Count(), 100);
  115.     size_t            maxdomsize = 0;
  116.  
  117.     for (index_t i = aVarSet.Mini(); i <= aVarSet.Maxi(); i++)
  118.     {
  119.     TLVariableAC6 *var = DYNACAST(TLVariableAC6 *, aVarSet.PeekAt(i));
  120.     TLX_ASSERT_PTR(var);
  121.  
  122.     TLX_TRACE(TLX, (50, "Initializing variable %s", var->GetName()));
  123.  
  124.     // Clear support lists and update maximum domain size found so far.
  125.  
  126.     var->ClearSupport();
  127.     maxdomsize = tlMax(maxdomsize, var->Domain().Count());
  128.  
  129.     // Check all constraints to see if they must be added
  130.  
  131.     for (index_t j = var->Constraints().Mini();
  132.          j <= var->Constraints().Maxi(); j++)
  133.     {
  134.         TLConstraintAC6 *con = DYNACAST(TLConstraintAC6 *,
  135.                         var->Constraints().PeekAt(j));
  136.         TLX_ASSERT_PTR(con);
  137.  
  138.         // Add the constraint to the list if it's not already in it,
  139.         // and if the other end of the constraint is linked to a
  140.         // variable that is also in the set of variables under
  141.         // consideration.
  142.  
  143.         if (!constraints.Contains(con) &&
  144.             aVarSet.Contains(&con->OppositeOf(*var)))
  145.         {
  146.         TLX_TRACE(TLX, (51, "-- Adding constraint for variable %s",
  147.                   var->GetName()));
  148.         constraints.Append(con);
  149.         }
  150.     }
  151.     }
  152.  
  153.     // Iterate through all constraints, initializing the support lists of
  154.     // the variables connected by them and putting unsupported values
  155.     // on a waiting list for propagation at a later stage.
  156.     //
  157.     // We attempt to create a waiting list of a reasonable initial capacity.
  158.  
  159.     size_t initsize  = aVarSet.Count() * maxdomsize / 2;
  160.     size_t expansion = tlMin(100U, initsize / 2);
  161.     TLWaitingList waitinglist(initsize, expansion);
  162.  
  163.     TLX_TRACE(TLX, (40, "Initializing supports"));
  164.  
  165.     for (index_t i2 = constraints.Mini(); i2 <= constraints.Maxi(); i2++)
  166.     {
  167.     TLConstraintAC6 *con = constraints.PeekAt(i2);
  168.     TLX_ASSERT_PTR(con);
  169.  
  170.     // We assume that all constraints are used in two directions, i.e.
  171.     // that they are undirected edges rather than arcs.
  172.  
  173.     InitSupport(con, &con->Var1(), &con->Var2(), waitinglist);
  174.     InitSupport(con, &con->Var2(), &con->Var1(), waitinglist);
  175.     }
  176.  
  177.     // The actual propagation starts here. We iterate through the list
  178.     // of waiting variable/value pairs until it's completely empty, at
  179.     // which point we have a consisten system, or until the domain of
  180.     // one of the variables becomes empty, indicating an inconsistency.
  181.  
  182.     while (!waitinglist.IsEmpty())
  183.     {
  184.     // Get the next domain element that was removed from its domain
  185.     // previously.
  186.  
  187.     TLDomainRemoval removal(waitinglist.Dequeue());
  188.  
  189.     // Propagate the effects of the removal of this element to the
  190.     // variable/value pairs that it supported.
  191.  
  192.     TLVariableAC6 *orgvar  = removal.Key();
  193.     TLDomainElement *domel = &removal.Value();
  194.  
  195.     // Iterate through all previously supported variable/value pairs
  196.  
  197.     iter_t supiter;
  198.     for (bool ok = domel->ResetIter(supiter); ok;
  199.          ok = domel->NextIter(supiter))
  200.     {
  201.         const TLVarValueLink *supvv = domel->PeekIter(supiter);
  202.         TLVariableAC6 *supvar = supvv->PeekVar();
  203.         tVarValue supvalue      = supvv->PeekValue();
  204.  
  205.         // Find the constraint that links the two variables
  206.  
  207.         TLConstraintAC6 *con  = orgvar->FindConstraintTo(supvar);
  208.         if (!con)
  209.         {
  210.         TLX_TRACE_WARN(TLX, ("No supporting constraint found"));
  211.         continue;
  212.         }
  213.  
  214.         // Ask the constraint to find the next supporting value for
  215.         // the value of the supported variable.
  216.  
  217.         tVarValue orgvalue = domel->PeekValue() + 1;
  218.  
  219.         if (con->FindNextSupport(*supvar, supvalue, *orgvar, orgvalue))
  220.         {
  221.         // Found new supporting value; add the supported variable/
  222.         // value pair to its list of supports.
  223.  
  224.         orgvar->AddSupport(orgvalue, *supvv);
  225.         }
  226.         else
  227.         {
  228.         // No support found; remove the value from the supported
  229.         // variable's domain and add it to the waiting list.
  230.  
  231.         TLDomainRemoval newrem(supvar,
  232.                        supvar->Domain().GetElement(supvalue));
  233.         waitinglist.Enqueue(newrem);
  234.         supvar->RemoveValue(supvalue);
  235.         }
  236.     }
  237.  
  238.     // The removal and its support list will be automatically deleted
  239.     // by the compiler's call to its destructor.
  240.     }
  241.  
  242.     // If we get here, there were no inconsistencies
  243.  
  244.     return true;
  245. }
  246.  
  247. /*-------------------------------------------------------------------------*/
  248.     bool TLPropagatorAC6::InitSupport
  249.     (
  250.         TLConstraintAC6 *    aCon,     // Supporting constraints
  251.     TLVariableAC6 *        aVar1,    // First (supported) variable
  252.     TLVariableAC6 *        aVar2,    // Second (supporting) variable
  253.     TLWaitingList &        aList    // List on which to enqueue removals
  254.     )
  255.  
  256. /*  Initializes support lists for the given variables. Returns nonzero
  257.     if all went well, or zero if an empty domain was detected.
  258. ---------------------------------------------------------------------------*/
  259. {
  260.     TLX_ASSERT_PTR(aCon);
  261.     TLX_ASSERT_PTR(aVar1);
  262.     TLX_ASSERT_PTR(aVar2);
  263.     TLX_ASSERT(aVar2 == &aCon->OppositeOf(*aVar1));
  264.  
  265.     TLX_TRACE(TLX, (50, "Initializing support from %s to %s", aVar1->GetName(),
  266.            aVar2->GetName()));
  267.  
  268.     // Iterate through the domain of the first variable, looking for
  269.     // support for its values.
  270.  
  271.     if (aVar2->Domain().IsEmpty())
  272.     {
  273.     // If the domain of the variable is empty, there is no need
  274.     // for any further processing.
  275.  
  276.     TLX_TRACE_INFO(TLX, ("Variable %s has empty domain", aVar2->GetName()));
  277.     return false;
  278.     }
  279.  
  280.     for (index_t vi = aVar1->Domain().Mini(); vi <= aVar1->Domain().Maxi(); )
  281.     {
  282.     TLX_ASSERT(!aVar2->Domain().IsEmpty());
  283.  
  284.     tVarValue orgvalue = aVar2->Domain().PeekFirst().PeekValue();
  285.     tVarValue supvalue = aVar1->Domain().PeekAt(vi).PeekValue();
  286.  
  287.     if (aCon->FindNextSupport(*aVar1, supvalue, *aVar2, orgvalue))
  288.     {
  289.         // Found supporting value; add the supported variable/
  290.         // value pair to its list of supports.
  291.  
  292.         aVar2->AddSupport(orgvalue, VV_Assoc(aVar1, supvalue));
  293.         vi++;
  294.     }
  295.     else
  296.     {
  297.         // No support found; remove the value from the supported
  298.         // variable's domain and add it to the waiting list.
  299.  
  300.         TLX_TRACE(TLX, (51, "Removing unsupported value %ld from variable %s",
  301.                supvalue, aVar1->GetName()));
  302.  
  303.         TLDomainRemoval newrem(aVar1,
  304.                        aVar1->Domain().GetElement(supvalue));
  305.         aList.Enqueue(newrem);
  306.         aVar1->RemoveValue(supvalue);    // Do not increment 'vi'
  307.     }
  308.     }
  309.  
  310.     // If we get here, all domains were nonempty
  311.  
  312.     return true;
  313. }
  314.  
  315.