home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / tlx501.zip / SOLVE / STDCSP.H < prev   
C/C++ Source or Header  |  1996-09-27  |  19KB  |  581 lines
  1. /****************************************************************************
  2.     $Id: stdcsp.h 501.0 1995/03/07 12:26:54 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.     Declarations for standard CSP classes. These classes build on the CSP
  10.     base classes and provide templates and ordinary classes for common
  11.     situations:
  12.  
  13.     TLNodeConOf<V>    - unary constraint on variables of type V
  14.     TLBinConOf<V>    - binary constraint on variables of type V
  15.     TLDomainOf<D>    - class template for domains of type D
  16.     TLCSProblemState    - subproblem base class for CSPs
  17.     TLCSProblemOf<V,L>    - subproblem template class for CSPs
  18.     TLCSProblemRep    - C.S. problem representation with several strategies
  19.  
  20.     $Log: stdcsp.h $
  21.     Revision 501.0  1995/03/07 12:26:54  RON
  22.     Updated for TLX 5.01
  23.     Revision 1.14  1995/02/22 12:40:00  RON
  24.     Update for release 012
  25.     Added partial support for SunPro C++ compiler
  26.     Revision 1.13  1995/01/16  12:22:45  ron
  27.     Added TLCSSubProblem parameter to varselectors
  28.  
  29.     Revision 1.12  1995/01/13  15:27:23  ron
  30.     Added local variable processing to CSSubProblem
  31.     Renamed ProcessVariable to Propagate in CSProblemRep
  32.  
  33.     Revision 1.11  1995/01/12  13:35:36  ron
  34.     Adapted to previous Searcher/ProblemRep model
  35.  
  36.     Revision 1.10  1995/01/10  16:35:57  ron
  37.     Small formatting change
  38.  
  39.     Revision 1.9  1995/01/08  11:53:05  ron
  40.     Renamed TLCSProblem to TLCSSubProblem
  41.  
  42.     Revision 1.8  1995/01/06  16:03:49  ron
  43.     Adapted to new Searcher/Problem model
  44.  
  45.     Revision 1.7  1995/01/05  15:38:26  ron
  46.     Brought inline with thesis
  47.  
  48.     Revision 1.6  1994/11/16  15:32:27  ron
  49.     Introduced TLVarSelector class
  50.  
  51.     Revision 1.5  1994/10/13  11:58:09  ron
  52.     Renamed variable selection strategies
  53.     Added |C|/(|D|^2) strategy
  54.     Made strategies integers rather than enums
  55.  
  56.     Revision 1.4  1994/10/11  19:10:08  ron
  57.     Replaced DeadEnd() by ProcessNode()
  58.  
  59.     Revision 1.3  1994/10/10  17:08:14  ron
  60.     Renamed TLStdProblemRep to TLCSProblemRep
  61.     Added several utility functions to TLCSProblemRep
  62.     Added TLSearchWatchdog monitor class
  63.  
  64.     Revision 1.2  1994/10/07  17:11:58  ron
  65.     Added TLSearchStats as a standard search monitor
  66.  
  67.     Revision 1.1  1994/10/06  17:53:10  ron
  68.     Initial revision
  69.  
  70. ****************************************************************************/
  71.  
  72. #ifndef _TLX_STDCSP_H
  73. #define _TLX_STDCSP_H
  74.  
  75. #ifndef _TLX_ITER_H
  76. #include <tlx\501\iter.h>
  77. #endif
  78. #ifndef _TLX_CSP_H
  79. #include <tlx\501\solve\csp.h>
  80. #endif
  81. #ifndef _TLX_SEARCHER_H
  82. #include <tlx\501\solve\searcher.h>
  83. #endif
  84.  
  85. class _TLXCLASS TLCSProblemRep;    // Below
  86. class _TLXCLASS TLIntVar;    // Below
  87.  
  88. /*---------------------------------------------------------------------------
  89.     TLNodeConOf<V> -
  90.  
  91.     Abstract base class for unary constraints that connect to variables of
  92.     type V (V must be derived from TLVariable).
  93. ---------------------------------------------------------------------------*/
  94.  
  95. template<class V> class _TLXCLASS TLNodeConOf: public TLNodeCon
  96. {
  97. public:
  98.     TLNodeConOf(V &);
  99.  
  100.     // The following functions hide the inherited ones for type safety
  101.  
  102.     V &            Var();
  103.     const V &        Var() const;
  104. };
  105.  
  106. /*---------------------------------------------------------------------------
  107.     TLBinConOf<V> -
  108.  
  109.     Abstract base class template for binary constraints that connect
  110.     variables of type V (V must be derived from TLVariable).
  111. ---------------------------------------------------------------------------*/
  112.  
  113. template<class V> class _TLXCLASS TLBinConOf: public TLBinCon
  114. {
  115. public:
  116.     TLBinConOf(V &, V &);
  117.  
  118.     // The following functions hide the inherited ones for type safety
  119.  
  120.     V &            Var1();
  121.     const V &        Var1() const;
  122.     V &            Var2();
  123.     const V &        Var2() const;
  124.     V &            OppositeOf(V &);
  125.     const V &        OppositeOf(const V &) const;
  126. };
  127.  
  128. /*---------------------------------------------------------------------------
  129.     TLDomainOf<D> -
  130.  
  131.     Class template for domains that contain a value of type D (D may be
  132.     a collection of type L or something similar).
  133. ---------------------------------------------------------------------------*/
  134.  
  135. template<class D> class TLDomainOf: public TLDomain
  136. {
  137.     D            mValue;        // Domain value
  138.  
  139. public:
  140.     // Constructor relies on copy constructor of type D; default destructor
  141.     // relies on D's destructor.
  142.  
  143.     TLDomainOf(const D &);
  144.  
  145.     // Access to the domain value
  146.  
  147.     D &            Value();
  148.     const D &        Value() const;
  149.  
  150.     // Implementation of output function relies on the existence of
  151.     // operator <<(ostream &, const D &).
  152.  
  153.     virtual ostream &    PrintOn(ostream &) const;
  154. };
  155.  
  156. /*---------------------------------------------------------------------------
  157.     TLCSProblemState -
  158.  
  159.     Subproblem class for use in CSPs. It contains a reference to a variable
  160.     and a domain monitor to capture changes.
  161. ---------------------------------------------------------------------------*/
  162.  
  163. class TLCSProblemState: public TLProblemState
  164. {
  165.     TLVariable *    mVar;        // Variable being assigned
  166.     TLDomainMonitor    mChanges;    // Changes to domains
  167.  
  168. public:
  169.     virtual ~TLCSProblemState();
  170.  
  171.     // Access to the variable
  172.  
  173.     TLVariable *    Var();
  174.     const TLVariable *    Var() const;
  175.  
  176.     // Overrideables for CSP subproblems:
  177.     //
  178.     // - AssignVariable(): the subproblem must perform the actual value
  179.     //   assignment. Domain capturing etc. are taken care of externally.
  180.     //
  181.     // - ProcessVariable(): any processing that can be done locally should
  182.     //   be done here. Domain capturing is active when the function is called.
  183.     //
  184.     // - DoneVariable(): called when processing on the variable is completed.
  185.     //   Local restoration should be done here; global matters (e.g. domain
  186.     //   restoration) is done externally.
  187.  
  188.     virtual void    AssignVariable() = 0;
  189.     virtual bool    ProcessVariable() { return true; }
  190.     virtual void    DoneVariable() {}
  191.  
  192.     // Helper functions to control the process of domain capturing:
  193.     //
  194.     // - SaveDomain() stores a copy of the domain of 'mVar'
  195.     // - StartCapturing() starts capturing of other domains
  196.     // - StopCapturing() stops capturing of other domains
  197.     // - RestoreDomains() restores all captured domains (including 'mVar')
  198.  
  199.     void        SaveDomain();
  200.     void        StartCapturing();
  201.     void        StopCapturing();
  202.     void        RestoreDomains();
  203.     bool        IsCapturing() const;
  204.  
  205. protected:
  206.     //TLCSProblemState(TLProblemState * = 0, TLVariable * = 0);
  207.     TLCSProblemState(TLVariable * = 0);
  208. };
  209.  
  210. /*---------------------------------------------------------------------------
  211.     TLCSProblemStateOf<V,L> -
  212.  
  213.     Class template for CSP subproblems of variables of type V and values
  214.     of type L. Type V must be TLVariable or derived thereof.
  215. ---------------------------------------------------------------------------*/
  216.  
  217. template<class V, class L> class TLCSProblemStateOf: public TLCSProblemState
  218. {
  219.     L            mValue;        // Value of the variable
  220.  
  221. public:
  222.     TLCSProblemStateOf();
  223.     //TLCSProblemStateOf(TLProblemState *, V *, const L &);
  224.     TLCSProblemStateOf(V *, const L &);
  225.  
  226.     // Type-safe access to the variable (hides inherited version), and
  227.     // access to its associated value.
  228.  
  229.     V *            Var();
  230.     const V *        Var() const;
  231.     L &            Value();
  232.     const L &        Value() const;
  233.  
  234.     // Implementation of output function relies on operator <<(ostream &,
  235.     // const L &).
  236.  
  237.     virtual ostream &    PrintOn(ostream &) const;
  238. };
  239.  
  240. /*---------------------------------------------------------------------------
  241.     TLVarSelector -
  242.  
  243.     Variable selection strategy class. Its purpose is to select the next
  244.     eligible variable from the remaining free variables.
  245. ---------------------------------------------------------------------------*/
  246.  
  247. class _TLXCLASS TLVarSelector
  248. {
  249. public:
  250.     virtual ~TLVarSelector();
  251.  
  252.     virtual const char *Description() const = 0;
  253.     virtual TLVariable *SelectVariable(TLCSProblemState *, TLCSProblemRep *,
  254.                            const TLVarList &) = 0;
  255. };
  256.  
  257. //---------------------------------------------------------------------------
  258. //  TLVSRandom: random selection strategy
  259. //---------------------------------------------------------------------------
  260.  
  261. class _TLXCLASS TLVSRandom: public TLVarSelector
  262. {
  263. public:
  264.     TLVSRandom();
  265.  
  266.     virtual const char *Description() const;
  267.     virtual TLVariable *SelectVariable(TLCSProblemState *, TLCSProblemRep *,
  268.                            const TLVarList &);
  269. };
  270.  
  271. //---------------------------------------------------------------------------
  272. //  TLVSSmallestDomain: selects variable with smallest domain
  273. //---------------------------------------------------------------------------
  274.  
  275. class _TLXCLASS TLVSSmallestDomain: public TLVarSelector
  276. {
  277. public:
  278.     TLVSSmallestDomain();
  279.  
  280.     virtual const char *Description() const;
  281.     virtual TLVariable *SelectVariable(TLCSProblemState *, TLCSProblemRep *,
  282.                            const TLVarList &);
  283. };
  284.  
  285. //---------------------------------------------------------------------------
  286. //  TLVSLargestDomain: selects variable with largest domain
  287. //---------------------------------------------------------------------------
  288.  
  289. class _TLXCLASS TLVSLargestDomain: public TLVarSelector
  290. {
  291. public:
  292.     TLVSLargestDomain();
  293.  
  294.     virtual const char *Description() const;
  295.     virtual TLVariable *SelectVariable(TLCSProblemState *, TLCSProblemRep *,
  296.                            const TLVarList &);
  297. };
  298.  
  299. //---------------------------------------------------------------------------
  300. //  TLVSMostConstrained: selects variable with most constraints
  301. //---------------------------------------------------------------------------
  302.  
  303. class _TLXCLASS TLVSMostConstrained: public TLVarSelector
  304. {
  305. public:
  306.     TLVSMostConstrained();
  307.  
  308.     virtual const char *Description() const;
  309.     virtual TLVariable *SelectVariable(TLCSProblemState *, TLCSProblemRep *,
  310.                            const TLVarList &);
  311. };
  312.  
  313. //---------------------------------------------------------------------------
  314. //  TLVSLeastConstrained: selects variable with least constraints
  315. //---------------------------------------------------------------------------
  316.  
  317. class _TLXCLASS TLVSLeastConstrained: public TLVarSelector
  318. {
  319. public:
  320.     TLVSLeastConstrained();
  321.  
  322.     virtual const char *Description() const;
  323.     virtual TLVariable *SelectVariable(TLCSProblemState *, TLCSProblemRep *,
  324.                            const TLVarList &);
  325. };
  326.  
  327. //---------------------------------------------------------------------------
  328. //  TLVSDomConMix: selects variable with smallest domain, most constraints
  329. //---------------------------------------------------------------------------
  330.  
  331. class _TLXCLASS TLVSDomConMix: public TLVarSelector
  332. {
  333. public:
  334.     TLVSDomConMix();
  335.  
  336.     virtual const char *Description() const;
  337.     virtual TLVariable *SelectVariable(TLCSProblemState *, TLCSProblemRep *,
  338.                            const TLVarList &);
  339. };
  340.  
  341. /*---------------------------------------------------------------------------
  342.     TLCSProblemRep -
  343.  
  344.     ProblemRep incorporating several commonly used selection strategies. The
  345.     problem representation must be used with variable classes that are
  346.     derived from TLCSProblemState.
  347. ---------------------------------------------------------------------------*/
  348.  
  349. class _TLXCLASS TLCSProblemRep: public TLProblemRep
  350. {
  351.     // Strategies are stored as pointers to strategy objects:
  352.  
  353.     TLPropagator *    mPropagator;    // Constraint propagation strategy
  354.     TLVarSelector *    mVarSelector;    // Variable selection strategy
  355.  
  356. protected:
  357.     TLVarList         mVars;        // All variables
  358.     TLVarList        mFreeVars;    // Free (i.e. unassigned) variables
  359.  
  360. public:
  361.     // Strategy setting and inquiry. Changes are in effect from the next
  362.     // opportunity onwards.
  363.  
  364.     TLPropagator *    GetPropagator() const;
  365.     TLPropagator *    SetPropagator(TLPropagator *);
  366.     TLVarSelector *    GetVarSelector() const;
  367.     TLVarSelector *    SetVarSelector(TLVarSelector *);
  368.  
  369.     // Overridden versions of global problem representation functions
  370.  
  371.     virtual size_t     Size() const;
  372.     virtual bool      PreProcess();
  373.     virtual ostream &    PrintOn(ostream &) const;
  374.  
  375.     // Overridden versions of subproblem functions
  376.  
  377.     virtual void    EnterState(TLProblemState *);
  378.     virtual bool    Process(TLProblemState *);
  379.     virtual void    LeaveState(TLProblemState *);
  380.     virtual size_t     GenerateBranches(TLProblemState *, TLProblemList &);
  381.  
  382. protected:
  383.     TLCSProblemRep();
  384.  
  385.     // Function to create the set of variables. They should be stored in
  386.     // the mVars data member. Afterwards, they are all preprocessed.
  387.  
  388.     virtual bool    CreateVariables() = 0;
  389.     virtual bool    PreProcessVariables();
  390.  
  391.     // Problem decomposition is divided into two steps: variable selection
  392.     // and branch generation. This problem representation provides standard
  393.     // strategies for variable selection, but they can be overridden. There
  394.     // is no implementation for branch generation, so that should be provided
  395.     // by a derived class.
  396.     //
  397.     // Note: SelectVariable() should *not* remove the variable from the
  398.     // list of free variables (this should be done by Process()).
  399.  
  400.     virtual TLVariable *SelectVariable(TLCSProblemState *);
  401.     virtual size_t    CreateBranches(TLCSProblemState *, TLVariable *,
  402.                        TLProblemList &) = 0;
  403.  
  404.     // Subproblem processing is split into several steps:
  405.     //
  406.     // 1. Variable assignment, delegated to the subproblem
  407.     // 2. Variable processing, delegated to the subproblem
  408.     // 3. Constraint propagation, performed by the function below
  409.     //
  410.     // The function below uses the installed propagation strategy object,
  411.     // but may be overridden in derived classes.
  412.  
  413.     virtual bool    Propagate(TLCSProblemState *);
  414. };
  415.  
  416. /*---------------------------------------------------------------------------
  417.     TLSolutionOf<V,L> -
  418. ---------------------------------------------------------------------------*/
  419.  
  420. template<class V, class L> class _TLXCLASS TLSolutionOf: public TLSolution
  421. {
  422.     TLPtrSeq<TLIntVar>     mVars;        // Ordered list of variables
  423.     TLSeq<int>        mValues;    // Parallel list of values
  424.  
  425. public:
  426.     Solution(TLProblemState *);            // Creates entire solution
  427.  
  428.     // PrintOn() is overridden in order to print the solution
  429.  
  430.     virtual ostream &PrintOn(ostream &) const;
  431. };
  432.  
  433. /*---------------------------------------------------------------------------
  434.     TLCSPMonitor -
  435.  
  436.     Search monitor that collects statistics about the constraint
  437.     propagation process. The following data are captured:
  438.  
  439.     - total, average, minimum, and maximum constraint checks
  440.     - average, minimum, and maximum constraint checks at each search depth
  441. ---------------------------------------------------------------------------*/
  442.  
  443. class _TLXCLASS TLCSPMonitor: public TLSearchMonitor
  444. {
  445.     // Statistics that are kept by this monitor are all one-dimensional
  446.  
  447.     typedef TLStats1<int32> IntStats;
  448.  
  449.     IntStats        mChecks;    // Overall checking statistics
  450.     TLArray<IntStats>    mLevelChecks;    // Checking stats per level
  451.     int32        mPrevCount;    // Previous # of checks
  452.  
  453. public:
  454.     TLCSPMonitor();
  455.  
  456.     // Overridden search monitor behavior.
  457.  
  458.     virtual int        DefaultEvents() const;
  459.     virtual void    OnSearchEvent(TLSearcher *, const Event &);
  460.     virtual ostream &    PrintOn(ostream &) const;
  461. };
  462.  
  463. /*---------------------------------------------------------------------------
  464.     Inline functions
  465. ---------------------------------------------------------------------------*/
  466.  
  467. //-----    TLNodeConOf<V>
  468.  
  469. template<class V> TLNodeConOf<V>::TLNodeConOf(V &aVar)
  470.     : TLNodeCon(aVar) {}
  471.  
  472. template<class V> inline V &TLNodeConOf<V>::Var()
  473.     { return (V &)TLNodeCon::Var(); }
  474.  
  475. template<class V> inline const V &TLNodeConOf<V>::Var() const
  476.     { return (const V &)TLNodeCon::Var(); }
  477.  
  478. //-----    TLBinConOf<V>
  479.  
  480. template<class V> TLBinConOf<V>::TLBinConOf(V &aVar1, V &aVar2)
  481.     : TLBinCon(aVar1, aVar2) {}
  482.  
  483. template<class V> inline V &TLBinConOf<V>::Var1()
  484.     { return (V &)TLBinCon::Var1(); }
  485.  
  486. template<class V> inline const V &TLBinConOf<V>::Var1() const
  487.     { return (const V &)TLBinCon::Var1(); }
  488.  
  489. template<class V> inline V &TLBinConOf<V>::Var2()
  490.     { return (V &)TLBinCon::Var2(); }
  491.  
  492. template<class V> inline const V &TLBinConOf<V>::Var2() const
  493.     { return (const V &)TLBinCon::Var2(); }
  494.  
  495. template<class V> inline V &TLBinConOf<V>::OppositeOf(V &aVar)
  496.     { return (V &)TLBinCon::OppositeOf(aVar); }
  497.  
  498. template<class V> inline
  499. const V &TLBinConOf<V>::OppositeOf(const V &aVar) const
  500.     { return (const V &)TLBinCon::OppositeOf(aVar); }
  501.  
  502. //-----    TLDomainOf<L>
  503.  
  504. template<class D> TLDomainOf<D>::TLDomainOf(const D &aValue)
  505.     : mValue(aValue) {}
  506.  
  507. template<class D> inline D &TLDomainOf<D>::Value()
  508.     { return mValue; }
  509.  
  510. template<class D> inline const D &TLDomainOf<D>::Value() const
  511.     { return mValue; }
  512.  
  513. template<class D> ostream &TLDomainOf<D>::PrintOn(ostream &os) const
  514.     { return os << mValue; }
  515.  
  516. //----- TLCSProblemState
  517.  
  518. inline TLVariable *TLCSProblemState::Var()
  519.     { return mVar; }
  520.  
  521. inline const TLVariable *TLCSProblemState::Var() const
  522.     { return mVar; }
  523.  
  524. inline void TLCSProblemState::SaveDomain()
  525.     { mChanges.CaptureDomain(mVar); }
  526.  
  527. inline void TLCSProblemState::StartCapturing()
  528.     { mChanges.StartCapturing(); }
  529.  
  530. inline void TLCSProblemState::StopCapturing()
  531.     { mChanges.StopCapturing(); }
  532.  
  533. inline void TLCSProblemState::RestoreDomains()
  534.     { mChanges.RestoreDomains(); }
  535.  
  536. inline bool TLCSProblemState::IsCapturing() const
  537.     { return mChanges.IsCapturing(); }
  538.  
  539. //-----    TLCSProblemStateOf<V,L>
  540.  
  541. template<class V, class L>
  542. TLCSProblemStateOf<V,L>::TLCSProblemStateOf()
  543.     : TLCSProblemState() {}
  544.  
  545. template<class V, class L>
  546. TLCSProblemStateOf<V,L>::TLCSProblemStateOf(
  547.     //TLProblemState *    aParent,
  548.     V *            aVar,
  549.     const L &        aValue)
  550.     //: TLCSProblemState(aParent, aVar), mValue(aValue) {}
  551.     : TLCSProblemState(aVar), mValue(aValue) {}
  552.  
  553. template<class V, class L> inline V *TLCSProblemStateOf<V,L>::Var()
  554.     { return (V *)TLCSProblemState::Var(); }
  555.  
  556. template<class V, class L> inline const V *TLCSProblemStateOf<V,L>::Var() const
  557.     { return (const V *)TLCSProblemState::Var(); }
  558.  
  559. template<class V, class L> inline L &TLCSProblemStateOf<V,L>::Value()
  560.     { return mValue; }
  561.  
  562. template<class V, class L> inline const L &TLCSProblemStateOf<V,L>::Value() const
  563.     { return mValue; }
  564.  
  565. template<class V, class L>
  566. ostream &TLCSProblemStateOf<V,L>::PrintOn(ostream &os) const
  567.     { return os << *Var() << "=" << mValue; }
  568.  
  569. //-----    TLCSProblemRep
  570.  
  571. inline size_t TLCSProblemRep::Size() const
  572.     { return mVars.Count(); }
  573.  
  574. inline TLPropagator *TLCSProblemRep::GetPropagator() const
  575.     { return mPropagator; }
  576.  
  577. inline TLVarSelector *TLCSProblemRep::GetVarSelector() const
  578.     { return mVarSelector; }
  579.  
  580. #endif    // _TLX_STDCSP_H
  581.