<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html xmlns="http://www.w3.org/1999/xhtml"> <head> <meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/> <title>CVC3: minisat_solver.h Source File</title> <link href="tabs.css" rel="stylesheet" type="text/css"/> <link href="doxygen.css" rel="stylesheet" type="text/css"/> </head> <body> <!-- Generated by Doxygen 1.7.4 --> <div id="top"> <div id="titlearea"> <table cellspacing="0" cellpadding="0"> <tbody> <tr style="height: 56px;"> <td style="padding-left: 0.5em;"> <div id="projectname">CVC3 <span id="projectnumber">2.4.1</span></div> </td> </tr> </tbody> </table> </div> <div id="navrow1" class="tabs"> <ul class="tablist"> <li><a href="index.html"><span>Main Page</span></a></li> <li><a href="pages.html"><span>Related Pages</span></a></li> <li><a href="modules.html"><span>Modules</span></a></li> <li><a href="namespaces.html"><span>Namespaces</span></a></li> <li><a href="annotated.html"><span>Classes</span></a></li> <li class="current"><a href="files.html"><span>Files</span></a></li> </ul> </div> <div id="navrow2" class="tabs2"> <ul class="tablist"> <li><a href="files.html"><span>File List</span></a></li> <li><a href="globals.html"><span>File Members</span></a></li> </ul> </div> <div class="header"> <div class="headertitle"> <div class="title">minisat_solver.h</div> </div> </div> <div class="contents"> <a href="minisat__solver_8h.html">Go to the documentation of this file.</a><div class="fragment"><pre class="fragment"><a name="l00001"></a>00001 <span class="comment">/*****************************************************************************/</span><span class="comment"></span> <a name="l00002"></a>00002 <span class="comment">/*!</span> <a name="l00003"></a>00003 <span class="comment"> *\file minisat_solver.h</span> <a name="l00004"></a>00004 <span class="comment"> *\brief Adaptation of MiniSat to DPLL(T)</span> <a name="l00005"></a>00005 <span class="comment"> *</span> <a name="l00006"></a>00006 <span class="comment"> * Author: Alexander Fuchs</span> <a name="l00007"></a>00007 <span class="comment"> *</span> <a name="l00008"></a>00008 <span class="comment"> * Created: Fri Sep 08 11:04:00 2006</span> <a name="l00009"></a>00009 <span class="comment"> *</span> <a name="l00010"></a>00010 <span class="comment"> * <hr></span> <a name="l00011"></a>00011 <span class="comment"> *</span> <a name="l00012"></a>00012 <span class="comment"> * License to use, copy, modify, sell and/or distribute this software</span> <a name="l00013"></a>00013 <span class="comment"> * and its documentation for any purpose is hereby granted without</span> <a name="l00014"></a>00014 <span class="comment"> * royalty, subject to the terms and conditions defined in the \ref</span> <a name="l00015"></a>00015 <span class="comment"> * LICENSE file provided with this distribution.</span> <a name="l00016"></a>00016 <span class="comment"> * </span> <a name="l00017"></a>00017 <span class="comment"> * <hr></span> <a name="l00018"></a>00018 <span class="comment"> */</span> <a name="l00019"></a>00019 <span class="comment">/*****************************************************************************/</span> <a name="l00020"></a>00020 <a name="l00021"></a>00021 <span class="comment">/****************************************************************************************[Solver.h]</span> <a name="l00022"></a>00022 <span class="comment">MiniSat -- Copyright (c) 2003-2005, Niklas Een, Niklas Sorensson</span> <a name="l00023"></a>00023 <span class="comment"></span> <a name="l00024"></a>00024 <span class="comment">Permission is hereby granted, free of charge, to any person obtaining a copy of this software and</span> <a name="l00025"></a>00025 <span class="comment">associated documentation files (the "Software"), to deal in the Software without restriction,</span> <a name="l00026"></a>00026 <span class="comment">including without limitation the rights to use, copy, modify, merge, publish, distribute,</span> <a name="l00027"></a>00027 <span class="comment">sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is</span> <a name="l00028"></a>00028 <span class="comment">furnished to do so, subject to the following conditions:</span> <a name="l00029"></a>00029 <span class="comment"></span> <a name="l00030"></a>00030 <span class="comment">The above copyright notice and this permission notice shall be included in all copies or</span> <a name="l00031"></a>00031 <span class="comment">substantial portions of the Software.</span> <a name="l00032"></a>00032 <span class="comment"></span> <a name="l00033"></a>00033 <span class="comment">THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT</span> <a name="l00034"></a>00034 <span class="comment">NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND</span> <a name="l00035"></a>00035 <span class="comment">NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,</span> <a name="l00036"></a>00036 <span class="comment">DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT</span> <a name="l00037"></a>00037 <span class="comment">OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.</span> <a name="l00038"></a>00038 <span class="comment">**************************************************************************************************/</span> <a name="l00039"></a>00039 <a name="l00040"></a>00040 <span class="preprocessor">#ifndef _cvc3__minisat_h_</span> <a name="l00041"></a>00041 <span class="preprocessor"></span><span class="preprocessor">#define _cvc3__minisat_h_</span> <a name="l00042"></a>00042 <span class="preprocessor"></span> <a name="l00043"></a>00043 <span class="preprocessor">#include "<a class="code" href="minisat__types_8h.html" title="MiniSat internal types.">minisat_types.h</a>"</span> <a name="l00044"></a>00044 <span class="preprocessor">#include "<a class="code" href="minisat__varorder_8h.html" title="MiniSat decision heuristics.">minisat_varorder.h</a>"</span> <a name="l00045"></a>00045 <span class="preprocessor">#include "<a class="code" href="minisat__derivation_8h.html" title="MiniSat proof logging.">minisat_derivation.h</a>"</span> <a name="l00046"></a>00046 <span class="preprocessor">#include "<a class="code" href="dpllt_8h.html" title="Generic DPLL(T) module.">dpllt.h</a>"</span> <a name="l00047"></a>00047 <span class="preprocessor">#include <queue></span> <a name="l00048"></a>00048 <span class="preprocessor">#include <stack></span> <a name="l00049"></a>00049 <span class="preprocessor">#include <vector></span> <a name="l00050"></a>00050 <span class="preprocessor">#include <limits></span> <a name="l00051"></a>00051 <span class="preprocessor">#include "<a class="code" href="hash__set_8h.html" title="hash map implementation">hash_set.h</a>"</span> <a name="l00052"></a>00052 <a name="l00053"></a>00053 <a name="l00054"></a>00054 <span class="comment">// changes to MiniSat for CVC integration:</span> <a name="l00055"></a>00055 <span class="comment">// 1) Decision heuristics</span> <a name="l00056"></a>00056 <span class="comment">// 2) Theory clauses</span> <a name="l00057"></a>00057 <span class="comment">// 3) Theory conflicts</span> <a name="l00058"></a>00058 <span class="comment">// 4) Theory implications</span> <a name="l00059"></a>00059 <span class="comment">// 5) binary clause trick</span> <a name="l00060"></a>00060 <span class="comment">//</span> <a name="l00061"></a>00061 <span class="comment">// in more detail:</span> <a name="l00062"></a>00062 <span class="comment">// 1) Decision heuristics</span> <a name="l00063"></a>00063 <span class="comment">// if a CVC decider is given (d_decider),</span> <a name="l00064"></a>00064 <span class="comment">// it is used instead of MiniSat's decision heuristics</span> <a name="l00065"></a>00065 <span class="comment">// to choose the next decision literal.</span> <a name="l00066"></a>00066 <span class="comment">//</span> <a name="l00067"></a>00067 <span class="comment">// 2) Theory clauses</span> <a name="l00068"></a>00068 <span class="comment">// any number of clauses can be added at any decision level.</span> <a name="l00069"></a>00069 <span class="comment">// see explanations for d_conflict and d_pendingClauses</span> <a name="l00070"></a>00070 <span class="comment">//</span> <a name="l00071"></a>00071 <span class="comment">// 3) Theory conflicts</span> <a name="l00072"></a>00072 <span class="comment">// theory conflicts are just treated as conflicting theory clauses</span> <a name="l00073"></a>00073 <span class="comment">//</span> <a name="l00074"></a>00074 <span class="comment">// 4) Theory implications</span> <a name="l00075"></a>00075 <span class="comment">// can be treated just as theory clauses if their explanation is retrieved immediately.</span> <a name="l00076"></a>00076 <span class="comment">// otherwise, Clause::TheoryImplication() is used as a reason</span> <a name="l00077"></a>00077 <span class="comment">// and the computation level is assumed to be the decision level,</span> <a name="l00078"></a>00078 <span class="comment">// until the explanation is retrieved (see d_theoryExplanations).</span> <a name="l00079"></a>00079 <a name="l00080"></a>00080 <a name="l00081"></a>00081 <span class="comment">// other changes:</span> <a name="l00082"></a>00082 <span class="comment">// - binary clause trick</span> <a name="l00083"></a>00083 <span class="comment">// MiniSat sometimes (watched literal, implication reason)</span> <a name="l00084"></a>00084 <span class="comment">// used a pointer to a clause to represent a unary clause.</span> <a name="l00085"></a>00085 <span class="comment">// the lowest bit was used to distinguish between a pointer,</span> <a name="l00086"></a>00086 <span class="comment">// and the integer representing the literal of the unit clause.</span> <a name="l00087"></a>00087 <span class="comment">// this saved memory and a pointer derefence.</span> <a name="l00088"></a>00088 <span class="comment">// while this is reported to increase the performance by about 10%-20%,</span> <a name="l00089"></a>00089 <span class="comment">// it also complicated the code. removing it didn't show any</span> <a name="l00090"></a>00090 <span class="comment">// worse performance, so this trick was dropped.</span> <a name="l00091"></a>00091 <span class="comment">//</span> <a name="l00092"></a>00092 <span class="comment">// - store all clauses</span> <a name="l00093"></a>00093 <span class="comment">// MiniSat stored unit and binary clauses only implicitly,</span> <a name="l00094"></a>00094 <span class="comment">// in the context and the watched literal data.</span> <a name="l00095"></a>00095 <span class="comment">// without the binary clause trick binary clauses have to be stored explicitly in d_clauses anyway.</span> <a name="l00096"></a>00096 <span class="comment">// mostly for consistency and simplicity unary clauses are stored expicitly as well.</span> <a name="l00097"></a>00097 <span class="comment">// not-so-convincing reasons are that this makes it also simpler to handle conflicting</span> <a name="l00098"></a>00098 <span class="comment">// theory unit clauses (see insertClause()) by giving the reason</span> <a name="l00099"></a>00099 <span class="comment">// (although one could use NULL instead,</span> <a name="l00100"></a>00100 <span class="comment">// but this would then complicate proof logging which is based on clause ids),</span> <a name="l00101"></a>00101 <span class="comment">// and that it helps to retrieve the clause set independently of the assignment.</span> <a name="l00102"></a>00102 <span class="comment">// (currently this is neither needed for DPLLT::checkSat nor DPLLT::continueCheck,</span> <a name="l00103"></a>00103 <span class="comment">// the two operations in DPLLTMiniSat which use MiniSat)</span> <a name="l00104"></a>00104 <span class="comment">// trying this out didn't show too much of an improvement, so it's not done.</span> <a name="l00105"></a>00105 <a name="l00106"></a>00106 <span class="keyword">namespace </span>MiniSat { <a name="l00107"></a>00107 <a name="l00108"></a>00108 <span class="comment">// assume that all stl containers use the same size type</span> <a name="l00109"></a>00109 <span class="comment">// and define it here once and for all</span> <a name="l00110"></a><a class="code" href="namespaceMiniSat.html#ad579041894c169fecdeb319f9aa5948d">00110</a> <span class="keyword">typedef</span> <a class="code" href="namespaceHash.html#a34e07ea2356b048f9871d1cfdf478da6">std::vector<int>::size_type</a> <a class="code" href="namespaceMiniSat.html#ad579041894c169fecdeb319f9aa5948d">size_type</a>; <a name="l00111"></a>00111 <a name="l00112"></a>00112 <span class="comment">//</span><span class="comment"></span> <a name="l00113"></a>00113 <span class="comment"> /// conversions between MiniSat and CVC data types:</span> <a name="l00114"></a>00114 <span class="comment"> ///</span> <a name="l00115"></a>00115 <span class="comment"></span> <a name="l00116"></a>00116 <span class="comment">// both MiniSat and CVC use integers for variables and literals.</span> <a name="l00117"></a>00117 <span class="comment">// CVC uses the integer's sign as the literals sign,</span> <a name="l00118"></a>00118 <span class="comment">// while MiniSat doubles the id and uses only positive numbers</span> <a name="l00119"></a>00119 <span class="comment">// (to be able to use them as array indizes).</span> <a name="l00120"></a>00120 <span class="comment">// e.g, for the variable p with the number 2,</span> <a name="l00121"></a>00121 <span class="comment">// CVC represents +p as 3 and -p as -3,</span> <a name="l00122"></a>00122 <span class="comment">// while MiniSat represents +p as 5 and -p as 4.</span> <a name="l00123"></a>00123 <span class="comment">//</span> <a name="l00124"></a>00124 <span class="comment">// unifying this representation is probably not worth doing,</span> <a name="l00125"></a>00125 <span class="comment">// as, first, conversion happens only at the interface level,</span> <a name="l00126"></a>00126 <span class="comment">// and second, no memory can be saved as a literal is just an integer.</span> <a name="l00127"></a>00127 <a name="l00128"></a><a class="code" href="namespaceMiniSat.html#a6d37e2f7d3903e1a85baf8f1e83eff78">00128</a> <span class="keyword">inline</span> <a class="code" href="namespaceMiniSat.html#a0d9722420b2afd308dceda22c1b05a5e">Var</a> <a class="code" href="namespaceMiniSat.html#a6d37e2f7d3903e1a85baf8f1e83eff78">cvcToMiniSat</a>(<span class="keyword">const</span> <a class="code" href="classSAT_1_1Var.html">SAT::Var</a>& var) { <a name="l00129"></a>00129 <span class="keywordflow">return</span> var.<a class="code" href="classSAT_1_1Var.html#a736443cd1ae4e1135d83c13bda3cbd80">getIndex</a>(); <a name="l00130"></a>00130 } <a name="l00131"></a>00131 <a name="l00132"></a><a class="code" href="namespaceMiniSat.html#a72756c106b9bd53cf77c2aab214e7cf5">00132</a> <span class="keyword">inline</span> <a class="code" href="classSAT_1_1Var.html">SAT::Var</a> <a class="code" href="namespaceMiniSat.html#a72756c106b9bd53cf77c2aab214e7cf5">miniSatToCVC</a>(<a class="code" href="namespaceMiniSat.html#a0d9722420b2afd308dceda22c1b05a5e">Var</a> var) { <a name="l00133"></a>00133 <span class="keywordflow">return</span> <a class="code" href="namespaceMiniSat.html#a0d9722420b2afd308dceda22c1b05a5e">SAT::Var</a>(var); <a name="l00134"></a>00134 } <a name="l00135"></a>00135 <a name="l00136"></a>00136 <a name="l00137"></a><a class="code" href="namespaceMiniSat.html#a0eb766a18a8ba93182ee46d85a40c282">00137</a> <span class="keyword">inline</span> <a class="code" href="classMiniSat_1_1Lit.html">Lit</a> <a class="code" href="namespaceMiniSat.html#a6d37e2f7d3903e1a85baf8f1e83eff78">cvcToMiniSat</a>(<span class="keyword">const</span> <a class="code" href="classSAT_1_1Lit.html">SAT::Lit</a>& literal) { <a name="l00138"></a>00138 <span class="keywordflow">return</span> <a class="code" href="classMiniSat_1_1Lit.html">MiniSat::Lit</a>(<a class="code" href="namespaceMiniSat.html#a6d37e2f7d3903e1a85baf8f1e83eff78">cvcToMiniSat</a>(literal.<a class="code" href="classSAT_1_1Lit.html#a57e2e6e37cad9595c3edbea88a41262f">getVar</a>()), literal.<a class="code" href="classSAT_1_1Lit.html#ada14f3ca2b88500b5c2500d60e7f554b">isPositive</a>()); <a name="l00139"></a>00139 } <a name="l00140"></a>00140 <a name="l00141"></a><a class="code" href="namespaceMiniSat.html#a30ac392b840d0ee1aa3877dadebff3fd">00141</a> <span class="keyword">inline</span> <a class="code" href="classSAT_1_1Lit.html">SAT::Lit</a> <a class="code" href="namespaceMiniSat.html#a72756c106b9bd53cf77c2aab214e7cf5">miniSatToCVC</a>(<a class="code" href="classMiniSat_1_1Lit.html">Lit</a> literal) { <a name="l00142"></a>00142 <span class="keywordflow">return</span> <a class="code" href="classSAT_1_1Lit.html">SAT::Lit</a>(<a class="code" href="namespaceMiniSat.html#a72756c106b9bd53cf77c2aab214e7cf5">miniSatToCVC</a>(literal.<a class="code" href="classMiniSat_1_1Lit.html#a952944c0a85fca7f8db8b532a72b3fda">var</a>()), literal.<a class="code" href="classMiniSat_1_1Lit.html#a75dadacca265ff92462528f29f1fcfd8">sign</a>()); <a name="l00143"></a>00143 } <a name="l00144"></a>00144 <a name="l00145"></a>00145 <span class="comment">// converts cvc clause into MiniSat literal list</span> <a name="l00146"></a>00146 <span class="comment">// returns true on permanently satisfied clause, i.e. clause containing 'true'</span> <a name="l00147"></a>00147 <span class="keywordtype">bool</span> <a class="code" href="namespaceMiniSat.html#a6d37e2f7d3903e1a85baf8f1e83eff78">cvcToMiniSat</a>(<span class="keyword">const</span> <a class="code" href="classSAT_1_1Clause.html">SAT::Clause</a>& clause, std::vector<Lit>& literals); <a name="l00148"></a>00148 <a name="l00149"></a>00149 <a name="l00150"></a>00150 <a name="l00151"></a>00151 <a name="l00152"></a>00152 <a name="l00153"></a>00153 <a name="l00154"></a>00154 <a name="l00155"></a>00155 <a name="l00156"></a>00156 <a name="l00157"></a>00157 <a name="l00158"></a>00158 <span class="comment">//=================================================================================================</span> <a name="l00159"></a>00159 <span class="comment">// MiniSat -- the main class:</span> <a name="l00160"></a>00160 <a name="l00161"></a>00161 <a name="l00162"></a><a class="code" href="structMiniSat_1_1SolverStats.html">00162</a> <span class="keyword">struct </span><a class="code" href="structMiniSat_1_1SolverStats.html">SolverStats</a> { <a name="l00163"></a><a class="code" href="structMiniSat_1_1SolverStats.html#aae74a427da81263e6a453bd4109f8da0">00163</a> int64_t <a class="code" href="structMiniSat_1_1SolverStats.html#a54dce5ac31ad5638d8d5046c45f71ac8">starts</a>, <a class="code" href="structMiniSat_1_1SolverStats.html#a0e6f2f64d6ed499602c0389a0616a0a1">decisions</a>, <a class="code" href="structMiniSat_1_1SolverStats.html#a615f23871d55f1adcac61e4803aff7d6">propagations</a>, <a class="code" href="structMiniSat_1_1SolverStats.html#a3a48e22367a0b5fe8aae15ea465424b3">conflicts</a>, <a class="code" href="structMiniSat_1_1SolverStats.html#aae74a427da81263e6a453bd4109f8da0">theory_conflicts</a>, <a class="code" href="structMiniSat_1_1SolverStats.html#a8bcaa8cbf6c443908d1b7be97a7109e8">max_level</a>; <a name="l00164"></a><a class="code" href="structMiniSat_1_1SolverStats.html#a4a57518371483fdd7f3def6f3fb0a4d8">00164</a> int64_t <a class="code" href="structMiniSat_1_1SolverStats.html#a2d6b6031c1da1bac5f1da1faf1dc59df">clauses_literals</a>, <a class="code" href="structMiniSat_1_1SolverStats.html#a94a5728db8ce10e76aadd2436de76b16">learnts_literals</a>, <a class="code" href="structMiniSat_1_1SolverStats.html#a4a57518371483fdd7f3def6f3fb0a4d8">max_literals</a>, <a name="l00165"></a>00165 <a class="code" href="structMiniSat_1_1SolverStats.html#aa64931fc97117dd89851ae88dadc897a">del_clauses</a>, <a class="code" href="structMiniSat_1_1SolverStats.html#a516c7e93fc14492cadd8215bec03b788">del_lemmas</a>, <a class="code" href="structMiniSat_1_1SolverStats.html#a24160d9cefb9aec5f5a88c031d77c048">db_simpl</a>, <a class="code" href="structMiniSat_1_1SolverStats.html#a05f292ab1b5be5cdbe9d005c2723aec2">lm_simpl</a>, <a name="l00166"></a>00166 <a class="code" href="structMiniSat_1_1SolverStats.html#aa10f0f08361269825bc6b784fdf4af6f">debug</a>; <a name="l00167"></a><a class="code" href="structMiniSat_1_1SolverStats.html#a71377e9e8688f812a211361dd62a4bef">00167</a> <a class="code" href="structMiniSat_1_1SolverStats.html#a71377e9e8688f812a211361dd62a4bef">SolverStats</a>() : <a class="code" href="structMiniSat_1_1SolverStats.html#a54dce5ac31ad5638d8d5046c45f71ac8">starts</a>(0), <a class="code" href="structMiniSat_1_1SolverStats.html#a0e6f2f64d6ed499602c0389a0616a0a1">decisions</a>(0), <a class="code" href="structMiniSat_1_1SolverStats.html#a615f23871d55f1adcac61e4803aff7d6">propagations</a>(0), <a class="code" href="structMiniSat_1_1SolverStats.html#a3a48e22367a0b5fe8aae15ea465424b3">conflicts</a>(0), <a class="code" href="structMiniSat_1_1SolverStats.html#aae74a427da81263e6a453bd4109f8da0">theory_conflicts</a>(0), <a class="code" href="structMiniSat_1_1SolverStats.html#a8bcaa8cbf6c443908d1b7be97a7109e8">max_level</a>(0), <a name="l00168"></a>00168 <a class="code" href="structMiniSat_1_1SolverStats.html#a2d6b6031c1da1bac5f1da1faf1dc59df">clauses_literals</a>(0), <a class="code" href="structMiniSat_1_1SolverStats.html#a94a5728db8ce10e76aadd2436de76b16">learnts_literals</a>(0), <a class="code" href="structMiniSat_1_1SolverStats.html#a4a57518371483fdd7f3def6f3fb0a4d8">max_literals</a>(0), <a name="l00169"></a>00169 <a class="code" href="structMiniSat_1_1SolverStats.html#aa64931fc97117dd89851ae88dadc897a">del_clauses</a>(0), <a class="code" href="structMiniSat_1_1SolverStats.html#a516c7e93fc14492cadd8215bec03b788">del_lemmas</a>(0), <a class="code" href="structMiniSat_1_1SolverStats.html#a24160d9cefb9aec5f5a88c031d77c048">db_simpl</a>(0), <a class="code" href="structMiniSat_1_1SolverStats.html#a05f292ab1b5be5cdbe9d005c2723aec2">lm_simpl</a>(0), <a class="code" href="structMiniSat_1_1SolverStats.html#aa10f0f08361269825bc6b784fdf4af6f">debug</a>(0) { } <a name="l00170"></a>00170 }; <a name="l00171"></a>00171 <a name="l00172"></a>00172 <a name="l00173"></a>00173 <span class="comment">// solver state at a push, needed so that a pop can revert to that state</span> <a name="l00174"></a><a class="code" href="structMiniSat_1_1PushEntry.html">00174</a> <span class="keyword">struct </span><a class="code" href="structMiniSat_1_1PushEntry.html">PushEntry</a> { <a name="l00175"></a>00175 <span class="comment">// the highest id of all clauses known -</span> <a name="l00176"></a>00176 <span class="comment">// clauses with higher id must have been added after the push</span> <a name="l00177"></a><a class="code" href="structMiniSat_1_1PushEntry.html#a4b43018d1e0983ca3db78e9ffbe54061">00177</a> <span class="keywordtype">int</span> <a class="code" href="structMiniSat_1_1PushEntry.html#a4b43018d1e0983ca3db78e9ffbe54061">d_clauseID</a>; <a name="l00178"></a>00178 <span class="comment">// size of d_trail</span> <a name="l00179"></a><a class="code" href="structMiniSat_1_1PushEntry.html#a799580d161aced43d1b5f1bbfc61d76e">00179</a> <a class="code" href="namespaceMiniSat.html#ad579041894c169fecdeb319f9aa5948d">size_type</a> <a class="code" href="structMiniSat_1_1PushEntry.html#a799580d161aced43d1b5f1bbfc61d76e">d_trailSize</a>; <a name="l00180"></a><a class="code" href="structMiniSat_1_1PushEntry.html#acb3db7998ba23df03c6dafa9062c8f6e">00180</a> <a class="code" href="namespaceMiniSat.html#ad579041894c169fecdeb319f9aa5948d">size_type</a> <a class="code" href="structMiniSat_1_1PushEntry.html#acb3db7998ba23df03c6dafa9062c8f6e">d_qhead</a>; <a name="l00181"></a><a class="code" href="structMiniSat_1_1PushEntry.html#a9d77c6f6c6add1891b0f683638319719">00181</a> <a class="code" href="namespaceMiniSat.html#ad579041894c169fecdeb319f9aa5948d">size_type</a> <a class="code" href="structMiniSat_1_1PushEntry.html#a9d77c6f6c6add1891b0f683638319719">d_thead</a>; <a name="l00182"></a>00182 <span class="comment">// conflict detected in initial propagation phase of push</span> <a name="l00183"></a><a class="code" href="structMiniSat_1_1PushEntry.html#adea074c679c082080b807b0e2a38dfd1">00183</a> <span class="keywordtype">bool</span> <a class="code" href="structMiniSat_1_1PushEntry.html#adea074c679c082080b807b0e2a38dfd1">d_ok</a>; <a name="l00184"></a>00184 <a name="l00185"></a><a class="code" href="structMiniSat_1_1PushEntry.html#a31fb7450af6723063f9126c4d9b06feb">00185</a> <a class="code" href="structMiniSat_1_1PushEntry.html#a31fb7450af6723063f9126c4d9b06feb">PushEntry</a>(<span class="keywordtype">int</span> clauseID, <a class="code" href="namespaceMiniSat.html#ad579041894c169fecdeb319f9aa5948d">size_type</a> trailSize, <a class="code" href="namespaceMiniSat.html#ad579041894c169fecdeb319f9aa5948d">size_type</a> qhead, <a class="code" href="namespaceMiniSat.html#ad579041894c169fecdeb319f9aa5948d">size_type</a> thead, <span class="keywordtype">bool</span> ok) : <a name="l00186"></a>00186 <a class="code" href="structMiniSat_1_1PushEntry.html#a4b43018d1e0983ca3db78e9ffbe54061">d_clauseID</a>(clauseID), <a name="l00187"></a>00187 <a class="code" href="structMiniSat_1_1PushEntry.html#a799580d161aced43d1b5f1bbfc61d76e">d_trailSize</a>(trailSize), <a class="code" href="structMiniSat_1_1PushEntry.html#acb3db7998ba23df03c6dafa9062c8f6e">d_qhead</a>(qhead), <a class="code" href="structMiniSat_1_1PushEntry.html#a9d77c6f6c6add1891b0f683638319719">d_thead</a>(thead), <a name="l00188"></a>00188 <a class="code" href="structMiniSat_1_1PushEntry.html#adea074c679c082080b807b0e2a38dfd1">d_ok</a>(ok) <a name="l00189"></a>00189 {} <a name="l00190"></a>00190 }; <a name="l00191"></a>00191 <a name="l00192"></a>00192 <a name="l00193"></a><a class="code" href="structMiniSat_1_1SearchParams.html">00193</a> <span class="keyword">struct </span><a class="code" href="structMiniSat_1_1SearchParams.html">SearchParams</a> { <a name="l00194"></a><a class="code" href="structMiniSat_1_1SearchParams.html#a5edda8afdf5b72caac6f9dab89111042">00194</a> <span class="keywordtype">double</span> <a class="code" href="structMiniSat_1_1SearchParams.html#a5edda8afdf5b72caac6f9dab89111042">var_decay</a>, <a class="code" href="structMiniSat_1_1SearchParams.html#a69b3a22ed8d5d7e2e4e2f8c84b1f7e36">clause_decay</a>, <a class="code" href="structMiniSat_1_1SearchParams.html#a39d0f6c147449c2af63a89a186e4bdad">random_var_freq</a>; <span class="comment">// (reasonable values are: 0.95, 0.999, 0.02) </span> <a name="l00195"></a><a class="code" href="structMiniSat_1_1SearchParams.html#a426b9f808375880ecd2caa7d6977bcd7">00195</a> <a class="code" href="structMiniSat_1_1SearchParams.html#a426b9f808375880ecd2caa7d6977bcd7">SearchParams</a>(<span class="keywordtype">double</span> v = 1, <span class="keywordtype">double</span> c = 1, <span class="keywordtype">double</span> r = 0) : <a class="code" href="structMiniSat_1_1SearchParams.html#a5edda8afdf5b72caac6f9dab89111042">var_decay</a>(v), <a class="code" href="structMiniSat_1_1SearchParams.html#a69b3a22ed8d5d7e2e4e2f8c84b1f7e36">clause_decay</a>(c), <a class="code" href="structMiniSat_1_1SearchParams.html#a39d0f6c147449c2af63a89a186e4bdad">random_var_freq</a>(r) { } <a name="l00196"></a>00196 }; <a name="l00197"></a>00197 <a name="l00198"></a>00198 <a name="l00199"></a>00199 <a name="l00200"></a><a class="code" href="classMiniSat_1_1Solver.html">00200</a> <span class="keyword">class </span><a class="code" href="classMiniSat_1_1Solver.html">Solver</a> { <a name="l00201"></a>00201 <span class="comment"></span> <a name="l00202"></a>00202 <span class="comment"> /// variables</span> <a name="l00203"></a>00203 <span class="comment"></span><span class="keyword">protected</span>: <a name="l00204"></a>00204 <span class="comment">// level before first decision</span> <a name="l00205"></a><a class="code" href="classMiniSat_1_1Solver.html#a160ccfc80ff29cd6947b0d009400e434">00205</a> <span class="keyword">static</span> <span class="keyword">const</span> <span class="keywordtype">int</span> <a class="code" href="classMiniSat_1_1Solver.html#a160ccfc80ff29cd6947b0d009400e434" title="variables">d_rootLevel</a> = 0; <a name="l00206"></a>00206 <span class="comment"></span> <a name="l00207"></a>00207 <span class="comment"> /// status</span> <a name="l00208"></a>00208 <span class="comment"></span> <a name="l00209"></a>00209 <span class="comment">// a search() has been started</span> <a name="l00210"></a><a class="code" href="classMiniSat_1_1Solver.html#a53dec8ba9fc22afeeef701f1a329a669">00210</a> <span class="keywordtype">bool</span> <a class="code" href="classMiniSat_1_1Solver.html#a53dec8ba9fc22afeeef701f1a329a669" title="status">d_inSearch</a>; <a name="l00211"></a>00211 <a name="l00212"></a>00212 <span class="comment">// if false, then the clause set is unsatisfiable.</span> <a name="l00213"></a><a class="code" href="classMiniSat_1_1Solver.html#a813826a370752a20165602e79b18f7c6">00213</a> <span class="keywordtype">bool</span> <a class="code" href="classMiniSat_1_1Solver.html#a813826a370752a20165602e79b18f7c6">d_ok</a>; <a name="l00214"></a>00214 <a name="l00215"></a>00215 <span class="comment">// this clause is conflicting with the current context</span> <a name="l00216"></a>00216 <span class="comment">//</span> <a name="l00217"></a>00217 <span class="comment">// it is not necessary to store more than one conflicting clause.</span> <a name="l00218"></a>00218 <span class="comment">// if there are several conflicting clauses,</span> <a name="l00219"></a>00219 <span class="comment">// they must all have been become conflicting at the same decision level,</span> <a name="l00220"></a>00220 <span class="comment">// as in a conflicting state no decision is made.</span> <a name="l00221"></a>00221 <span class="comment">//</span> <a name="l00222"></a>00222 <span class="comment">// after backtracking on any of these conflicting clauses,</span> <a name="l00223"></a>00223 <span class="comment">// the others are also not conflicting anymore,</span> <a name="l00224"></a>00224 <span class="comment">// if the conflict really was due to the current decision level.</span> <a name="l00225"></a>00225 <span class="comment">//</span> <a name="l00226"></a>00226 <span class="comment">// this is only not the case if theory clauses are involved.</span> <a name="l00227"></a>00227 <span class="comment">// i) a conflicting theory clause is added to d_pendingClauses instead of the clause set.</span> <a name="l00228"></a>00228 <span class="comment">// it will be only moved to the clause set if it is not conflicting,</span> <a name="l00229"></a>00229 <span class="comment">// otherwise it (or some other conflicting clause) will be used for backtracking.</span> <a name="l00230"></a>00230 <span class="comment">// ii) progapations based on new theory clauses may actually be already valid</span> <a name="l00231"></a>00231 <span class="comment">// in a previous level, not only in the current decision level.</span> <a name="l00232"></a>00232 <span class="comment">// on backtracking this will be kept in the part of the trail which has to be propagated,</span> <a name="l00233"></a>00233 <span class="comment">// and be propagated again after backtracking,</span> <a name="l00234"></a>00234 <span class="comment">// thus the conflict will be computed again.</span> <a name="l00235"></a>00235 <span class="comment">//</span> <a name="l00236"></a>00236 <span class="comment">// this scheme also allows to stop the propagation as soon as one conflict clause is found,</span> <a name="l00237"></a>00237 <span class="comment">// and backtrack only in this one, instead of searching for all conflicting clauses.</span> <a name="l00238"></a>00238 <span class="comment">//</span> <a name="l00239"></a>00239 <span class="comment">// the only attempt at picking a good conflict clause is to pick the shortest one.</span> <a name="l00240"></a>00240 <span class="comment">// looking at the lowest backjumping level is probably(?) too expensive.</span> <a name="l00241"></a><a class="code" href="classMiniSat_1_1Solver.html#a431f60a202eee24b3928ca6c6195baa5">00241</a> <a class="code" href="classMiniSat_1_1Clause.html">Clause</a>* <a class="code" href="classMiniSat_1_1Solver.html#a431f60a202eee24b3928ca6c6195baa5">d_conflict</a>; <a name="l00242"></a>00242 <a name="l00243"></a>00243 <span class="comment"></span> <a name="l00244"></a>00244 <span class="comment"> /// variable assignments, and pending propagations</span> <a name="l00245"></a>00245 <span class="comment"></span> <a name="l00246"></a>00246 <span class="comment">// mapping from literals to clauses in which a literal is watched,</span> <a name="l00247"></a>00247 <span class="comment">// literal.index() is used as the index</span> <a name="l00248"></a><a class="code" href="classMiniSat_1_1Solver.html#a6a3e831d47c15ac42fe7a7002c276c0e">00248</a> std::vector<std::vector<Clause*> > <a class="code" href="classMiniSat_1_1Solver.html#a6a3e831d47c15ac42fe7a7002c276c0e" title="variable assignments, and pending propagations">d_watches</a>; <a name="l00249"></a>00249 <a name="l00250"></a>00250 <span class="comment">// The current assignments (lbool:s stored as char:s), indexed by var</span> <a name="l00251"></a><a class="code" href="classMiniSat_1_1Solver.html#a8fd906b3d57929f47f9a6eb6740e35e9">00251</a> std::vector<signed char> <a class="code" href="classMiniSat_1_1Solver.html#a8fd906b3d57929f47f9a6eb6740e35e9">d_assigns</a>; <a name="l00252"></a>00252 <a name="l00253"></a>00253 <span class="comment">// Assignment stack; stores all assigments made in the order they were made.</span> <a name="l00254"></a>00254 <span class="comment">// as theory clause and theory implications can add propagations</span> <a name="l00255"></a>00255 <span class="comment">// which are valid at earlier levels this list is _not_ necessarily ordered by level.</span> <a name="l00256"></a><a class="code" href="classMiniSat_1_1Solver.html#af092e4552ff6a34e5fcb5f67de96c845">00256</a> std::vector<Lit> <a class="code" href="classMiniSat_1_1Solver.html#af092e4552ff6a34e5fcb5f67de96c845">d_trail</a>; <a name="l00257"></a>00257 <a name="l00258"></a>00258 <span class="comment">// Separator indices for different decision levels in 'trail',</span> <a name="l00259"></a>00259 <span class="comment">// i.e. d_trail[trail_lim[i]] is the i.th decision</span> <a name="l00260"></a><a class="code" href="classMiniSat_1_1Solver.html#abf42fb28430f7b099c65c4e9b28ffb09">00260</a> std::vector<int> <a class="code" href="classMiniSat_1_1Solver.html#abf42fb28430f7b099c65c4e9b28ffb09">d_trail_lim</a>; <a name="l00261"></a>00261 <a name="l00262"></a>00262 <span class="comment">// 'd_trail_pos[var]' is the variable's position in 'trail[]'</span> <a name="l00263"></a>00263 <span class="comment">// used for proof logging</span> <a name="l00264"></a><a class="code" href="classMiniSat_1_1Solver.html#a31a1d57eabc2169a4a9fc1cf4c87a2a7">00264</a> std::vector<size_type> <a class="code" href="classMiniSat_1_1Solver.html#a31a1d57eabc2169a4a9fc1cf4c87a2a7">d_trail_pos</a>; <a name="l00265"></a>00265 <a name="l00266"></a>00266 <span class="comment">// head of propagation queue as index into the trail:</span> <a name="l00267"></a>00267 <span class="comment">// the context is the trail up to trail[qhead - 1],</span> <a name="l00268"></a>00268 <span class="comment">// the propagation queue is trail[qhead] to its end.</span> <a name="l00269"></a><a class="code" href="classMiniSat_1_1Solver.html#a22427732a96158ab53c2ffc61714fca4">00269</a> <a class="code" href="namespaceMiniSat.html#ad579041894c169fecdeb319f9aa5948d">size_type</a> <a class="code" href="classMiniSat_1_1Solver.html#a22427732a96158ab53c2ffc61714fca4">d_qhead</a>; <a name="l00270"></a>00270 <a name="l00271"></a>00271 <span class="comment">// like d_qhead for theories:</span> <a name="l00272"></a>00272 <span class="comment">// only the literals up to trail[thead - 1] have been asserted to the theories.</span> <a name="l00273"></a><a class="code" href="classMiniSat_1_1Solver.html#ad9d115b0ec2a84ce5ab3f1de19683f06">00273</a> <a class="code" href="namespaceMiniSat.html#ad579041894c169fecdeb319f9aa5948d">size_type</a> <a class="code" href="classMiniSat_1_1Solver.html#ad9d115b0ec2a84ce5ab3f1de19683f06">d_thead</a>; <a name="l00274"></a>00274 <a name="l00275"></a>00275 <span class="comment">// 'reason[var]' is the clause that implied the variables current value,</span> <a name="l00276"></a>00276 <span class="comment">// or Clause::Decision() for a decision ,</span> <a name="l00277"></a>00277 <span class="comment">// resp. (Clause::TheoryImplication()) for a theory implication with lazy explanation retrieval</span> <a name="l00278"></a><a class="code" href="classMiniSat_1_1Solver.html#a4405fbaba3ed712f704d5c85a390b558">00278</a> std::vector<Clause*> <a class="code" href="classMiniSat_1_1Solver.html#a4405fbaba3ed712f704d5c85a390b558">d_reason</a>; <a name="l00279"></a>00279 <a name="l00280"></a>00280 <span class="comment">// 'level[var]' is the decision level at which assignment was made.</span> <a name="l00281"></a>00281 <span class="comment">// except when the literal is a theory implication and the explanation</span> <a name="l00282"></a>00282 <span class="comment">// has not been retrieved yet. Then, this is the level of the literal's</span> <a name="l00283"></a>00283 <span class="comment">// assertion, and its real level will be computed during conflict analysis.</span> <a name="l00284"></a><a class="code" href="classMiniSat_1_1Solver.html#a34c9afcb69ae37cebbf43a61505009b3">00284</a> std::vector<int> <a class="code" href="classMiniSat_1_1Solver.html#a34c9afcb69ae37cebbf43a61505009b3">d_level</a>; <a name="l00285"></a>00285 <a name="l00286"></a>00286 <a name="l00287"></a>00287 <span class="comment">// Variables</span> <a name="l00288"></a>00288 <a name="l00289"></a>00289 <span class="comment">// the variables registered before the first push</span> <a name="l00290"></a>00290 <span class="comment">// and at each push level (with registerVar),</span> <a name="l00291"></a>00291 <span class="comment">// i.e. the variables occurring in the clauses at each push level.</span> <a name="l00292"></a>00292 <span class="comment">// cumulative, i.e. the variables registered in a push level</span> <a name="l00293"></a>00293 <span class="comment">// are the union of the variables registered at it and any previous level.</span> <a name="l00294"></a><a class="code" href="classMiniSat_1_1Solver.html#afc17e3fc6c5eb525504acbe000d9c5ca">00294</a> std::vector<Hash::hash_set<Var> > <a class="code" href="classMiniSat_1_1Solver.html#afc17e3fc6c5eb525504acbe000d9c5ca">d_registeredVars</a>; <a name="l00295"></a>00295 <a name="l00296"></a>00296 <span class="comment"></span> <a name="l00297"></a>00297 <span class="comment"> /// Clauses</span> <a name="l00298"></a>00298 <span class="comment"></span> <a name="l00299"></a>00299 <span class="comment">// clause id counter</span> <a name="l00300"></a><a class="code" href="classMiniSat_1_1Solver.html#ad6e3d6a97a4ae9dda9ac7b9bed97bed8">00300</a> <span class="keywordtype">int</span> <a class="code" href="classMiniSat_1_1Solver.html#ad6e3d6a97a4ae9dda9ac7b9bed97bed8" title="Clauses.">d_clauseIDCounter</a>; <a name="l00301"></a>00301 <a name="l00302"></a>00302 <span class="comment">// problem clauses (input clauses, theory clauses, explanations of theory implications).</span> <a name="l00303"></a><a class="code" href="classMiniSat_1_1Solver.html#ae4d0195d229b334f9d9c2f3122e41bd1">00303</a> std::vector<Clause*> <a class="code" href="classMiniSat_1_1Solver.html#ae4d0195d229b334f9d9c2f3122e41bd1">d_clauses</a>; <a name="l00304"></a>00304 <a name="l00305"></a>00305 <span class="comment">// learnt clauses (conflict clauses)</span> <a name="l00306"></a><a class="code" href="classMiniSat_1_1Solver.html#a0c9270be1c0980e631de98b3408a8031">00306</a> std::vector<Clause*> <a class="code" href="classMiniSat_1_1Solver.html#a0c9270be1c0980e631de98b3408a8031">d_learnts</a>; <a name="l00307"></a>00307 <a name="l00308"></a>00308 <span class="comment"></span> <a name="l00309"></a>00309 <span class="comment"> /// Temporary clauses</span> <a name="l00310"></a>00310 <span class="comment"></span> <a name="l00311"></a>00311 <span class="comment">// these are clauses which were already conflicting when added.</span> <a name="l00312"></a>00312 <span class="comment">// so, first the solver has to backtrack,</span> <a name="l00313"></a>00313 <span class="comment">// then they can be added in a consistent state.</span> <a name="l00314"></a><a class="code" href="classMiniSat_1_1Solver.html#adbae4eb042f37351c6cac493e6743813">00314</a> std::queue<Clause*> <a class="code" href="classMiniSat_1_1Solver.html#adbae4eb042f37351c6cac493e6743813" title="Temporary clauses.">d_pendingClauses</a>; <a name="l00315"></a>00315 <a name="l00316"></a>00316 <span class="comment">// these clauses are explanations for theory propagations which have been</span> <a name="l00317"></a>00317 <span class="comment">// retrieved to regress a conflict. they are gathered for the regression</span> <a name="l00318"></a>00318 <span class="comment">// in analyze, and then deleted on backtracking in backtrack.</span> <a name="l00319"></a><a class="code" href="classMiniSat_1_1Solver.html#a587104e3c6bb31d2bc7942bc1fde8b1e">00319</a> std::stack<std::pair<int, Clause*> > <a class="code" href="classMiniSat_1_1Solver.html#a587104e3c6bb31d2bc7942bc1fde8b1e">d_theoryExplanations</a>; <a name="l00320"></a>00320 <a name="l00321"></a>00321 <span class="comment"></span> <a name="l00322"></a>00322 <span class="comment"> /// Push / Pop</span> <a name="l00323"></a>00323 <span class="comment"></span> <a name="l00324"></a>00324 <span class="comment">// pushes</span> <a name="l00325"></a><a class="code" href="classMiniSat_1_1Solver.html#a6f9c67d77e57b99fef5de801623245a4">00325</a> std::vector<PushEntry> <a class="code" href="classMiniSat_1_1Solver.html#a6f9c67d77e57b99fef5de801623245a4" title="Push / Pop.">d_pushes</a>; <a name="l00326"></a>00326 <a name="l00327"></a>00327 <span class="comment">// lemmas kept after a pop, to add with the next push</span> <a name="l00328"></a><a class="code" href="classMiniSat_1_1Solver.html#a99b8d67e03c83f148906ff00e8e88851">00328</a> std::vector<Clause*> <a class="code" href="classMiniSat_1_1Solver.html#a99b8d67e03c83f148906ff00e8e88851">d_popLemmas</a>; <a name="l00329"></a>00329 <a name="l00330"></a>00330 <span class="comment">// for each variable the highest pushID of the clauses used for its implication.</span> <a name="l00331"></a>00331 <span class="comment">// for a decision or theory implication with unknown explanation this is max_int,</span> <a name="l00332"></a>00332 <span class="comment">// for a unit clause as the reason it is the clauses pushID,</span> <a name="l00333"></a>00333 <span class="comment">// for any other reason it is the max of the d_pushIDs of the literals</span> <a name="l00334"></a>00334 <span class="comment">// falsifying the literals of the reason clause</span> <a name="l00335"></a>00335 <span class="comment">//</span> <a name="l00336"></a>00336 <span class="comment">// thus, an approximation for checking if a clause literal is permanently</span> <a name="l00337"></a>00337 <span class="comment">// falsified/satisfied even after pops (as long as the clause is not popped itself),</span> <a name="l00338"></a>00338 <span class="comment">// is that the implication level of the literal it the root level,</span> <a name="l00339"></a>00339 <span class="comment">// and that clauses' pushID is <= the d_pushIDs value of the literal.</span> <a name="l00340"></a>00340 <span class="comment">//</span> <a name="l00341"></a>00341 <span class="comment">// this can be used for simplifcation of clauses, lemma minimization,</span> <a name="l00342"></a>00342 <span class="comment">// and keeping propagated literals after a pop.</span> <a name="l00343"></a><a class="code" href="classMiniSat_1_1Solver.html#ab0b2d4e87d57046e30c2cb3554925e2b">00343</a> std::vector<int> <a class="code" href="classMiniSat_1_1Solver.html#ab0b2d4e87d57046e30c2cb3554925e2b">d_pushIDs</a>; <a name="l00344"></a>00344 <a name="l00345"></a>00345 <span class="comment">// :TODO: unify var -> x arrays into one with a varInfo data structure:</span> <a name="l00346"></a>00346 <span class="comment">// d_assigns, d_reason, d_level, d_pushIDs, d_activity</span> <a name="l00347"></a>00347 <span class="comment">// probably not: d_trail_pos, d_analyze_seen</span> <a name="l00348"></a>00348 <a name="l00349"></a>00349 <span class="comment">// number of queued pop requests</span> <a name="l00350"></a><a class="code" href="classMiniSat_1_1Solver.html#acb6671d85d64f00c04ea17b3b6e144f6">00350</a> <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> <a class="code" href="classMiniSat_1_1Solver.html#acb6671d85d64f00c04ea17b3b6e144f6">d_popRequests</a>; <a name="l00351"></a>00351 <a name="l00352"></a>00352 <a name="l00353"></a>00353 <span class="comment"></span> <a name="l00354"></a>00354 <span class="comment"> /// heuristics</span> <a name="l00355"></a>00355 <span class="comment"></span> <a name="l00356"></a>00356 <span class="comment">// heuristics for keeping lemmas</span> <a name="l00357"></a>00357 <a name="l00358"></a>00358 <span class="comment">// Amount to bump next clause with.</span> <a name="l00359"></a><a class="code" href="classMiniSat_1_1Solver.html#a5b10958ebb6b146f8cfb2d6ec08ab667">00359</a> <span class="keywordtype">double</span> <a class="code" href="classMiniSat_1_1Solver.html#a5b10958ebb6b146f8cfb2d6ec08ab667" title="heuristics">d_cla_inc</a>; <a name="l00360"></a>00360 <span class="comment">// INVERSE decay factor for clause activity: stores 1/decay.</span> <a name="l00361"></a><a class="code" href="classMiniSat_1_1Solver.html#a3b0e8d36281ddcfefb54812accad5a55">00361</a> <span class="keywordtype">double</span> <a class="code" href="classMiniSat_1_1Solver.html#a3b0e8d36281ddcfefb54812accad5a55">d_cla_decay</a>; <a name="l00362"></a>00362 <a name="l00363"></a>00363 <span class="comment">// heuristics for variable decisions</span> <a name="l00364"></a>00364 <a name="l00365"></a>00365 <span class="comment">// A heuristic measurement of the activity of a variable.</span> <a name="l00366"></a><a class="code" href="classMiniSat_1_1Solver.html#a0765ad8a98718bb5523e487e32d66ae1">00366</a> std::vector<double> <a class="code" href="classMiniSat_1_1Solver.html#a0765ad8a98718bb5523e487e32d66ae1">d_activity</a>; <a name="l00367"></a>00367 <span class="comment">// Amount to bump next variable with.</span> <a name="l00368"></a><a class="code" href="classMiniSat_1_1Solver.html#aa9cba0f1df8f31b5ae94f2ce0ccb290f">00368</a> <span class="keywordtype">double</span> <a class="code" href="classMiniSat_1_1Solver.html#aa9cba0f1df8f31b5ae94f2ce0ccb290f">d_var_inc</a>; <a name="l00369"></a>00369 <span class="comment">// INVERSE decay factor for variable activity: stores 1/decay.</span> <a name="l00370"></a>00370 <span class="comment">// Use negative value for static variable order.</span> <a name="l00371"></a><a class="code" href="classMiniSat_1_1Solver.html#a354cacc000d52901cb2a60d1fe659d26">00371</a> <span class="keywordtype">double</span> <a class="code" href="classMiniSat_1_1Solver.html#a354cacc000d52901cb2a60d1fe659d26">d_var_decay</a>; <a name="l00372"></a>00372 <span class="comment">// Keeps track of the decision variable order.</span> <a name="l00373"></a><a class="code" href="classMiniSat_1_1Solver.html#aab79cd4bf5792f72c191d8149e77bc93">00373</a> <a class="code" href="classMiniSat_1_1VarOrder.html">VarOrder</a> <a class="code" href="classMiniSat_1_1Solver.html#aab79cd4bf5792f72c191d8149e77bc93">d_order</a>; <a name="l00374"></a>00374 <a name="l00375"></a>00375 <span class="comment">// heuristics for clause/lemma database cleanup</span> <a name="l00376"></a>00376 <a name="l00377"></a>00377 <span class="comment">// Number of top-level assignments since last execution of 'simplifyDB()'.</span> <a name="l00378"></a><a class="code" href="classMiniSat_1_1Solver.html#ac114e23a9bd1329c9002eb758c1595b7">00378</a> <span class="keywordtype">int</span> <a class="code" href="classMiniSat_1_1Solver.html#ac114e23a9bd1329c9002eb758c1595b7">d_simpDB_assigns</a>; <a name="l00379"></a>00379 <span class="comment">// Remaining number of propagations that must be made before next execution of 'simplifyDB()'.</span> <a name="l00380"></a><a class="code" href="classMiniSat_1_1Solver.html#a4f2b0a42acb3d470ca9500b2f4fd8077">00380</a> int64_t <a class="code" href="classMiniSat_1_1Solver.html#a4f2b0a42acb3d470ca9500b2f4fd8077">d_simpDB_props</a>; <a name="l00381"></a>00381 <span class="comment">// Number of lemmas after last execution of 'reduceDB()'.</span> <a name="l00382"></a><a class="code" href="classMiniSat_1_1Solver.html#ac380f5046f3dddbb0bdebf4107d8d506">00382</a> <span class="keywordtype">int</span> <a class="code" href="classMiniSat_1_1Solver.html#ac380f5046f3dddbb0bdebf4107d8d506">d_simpRD_learnts</a>; <a name="l00383"></a>00383 <a name="l00384"></a>00384 <span class="comment"></span> <a name="l00385"></a>00385 <span class="comment"> /// CVC interface</span> <a name="l00386"></a>00386 <span class="comment"></span> <a name="l00387"></a>00387 <span class="comment">// CVC theory API</span> <a name="l00388"></a><a class="code" href="classMiniSat_1_1Solver.html#a8336c93fe51668a8cd322f9a059d5137">00388</a> <a class="code" href="classSAT_1_1DPLLT_1_1TheoryAPI.html">SAT::DPLLT::TheoryAPI</a>* <a class="code" href="classMiniSat_1_1Solver.html#a8336c93fe51668a8cd322f9a059d5137" title="CVC interface.">d_theoryAPI</a>; <a name="l00389"></a>00389 <a name="l00390"></a>00390 <span class="comment">// CVC decision heuristic</span> <a name="l00391"></a><a class="code" href="classMiniSat_1_1Solver.html#a18b5a09a43e43ae4bde40537e652e987">00391</a> <a class="code" href="classSAT_1_1DPLLT_1_1Decider.html">SAT::DPLLT::Decider</a>* <a class="code" href="classMiniSat_1_1Solver.html#a18b5a09a43e43ae4bde40537e652e987">d_decider</a>; <a name="l00392"></a>00392 <a name="l00393"></a>00393 <span class="comment"></span> <a name="l00394"></a>00394 <span class="comment"> /// proof logging</span> <a name="l00395"></a>00395 <span class="comment"></span> <a name="l00396"></a>00396 <span class="comment">// log derivation, to create a resolution proof from a closed derivation tree proof</span> <a name="l00397"></a><a class="code" href="classMiniSat_1_1Solver.html#ad2d7fa92335dfd68f8598a5a41d17e93">00397</a> <a class="code" href="classMiniSat_1_1Derivation.html">Derivation</a>* <a class="code" href="classMiniSat_1_1Solver.html#ad2d7fa92335dfd68f8598a5a41d17e93" title="proof logging">d_derivation</a>; <a name="l00398"></a>00398 <a name="l00399"></a>00399 <span class="comment"></span> <a name="l00400"></a>00400 <span class="comment"> /// Mode of operation:</span> <a name="l00401"></a>00401 <span class="comment"></span> <a name="l00402"></a>00402 <span class="comment">// Restart frequency etc.</span> <a name="l00403"></a><a class="code" href="classMiniSat_1_1Solver.html#aece892bd1701b50038331c77b70d0949">00403</a> <a class="code" href="structMiniSat_1_1SearchParams.html">SearchParams</a> <a class="code" href="classMiniSat_1_1Solver.html#aece892bd1701b50038331c77b70d0949" title="Mode of operation:">d_default_params</a>; <a name="l00404"></a>00404 <a name="l00405"></a>00405 <span class="comment">// Controls conflict clause minimization. true by default.</span> <a name="l00406"></a><a class="code" href="classMiniSat_1_1Solver.html#a4ecef2c87d4be7bf5a0ba8b4e800e09c">00406</a> <span class="keywordtype">bool</span> <a class="code" href="classMiniSat_1_1Solver.html#a4ecef2c87d4be7bf5a0ba8b4e800e09c">d_expensive_ccmin</a>; <a name="l00407"></a>00407 <a name="l00408"></a>00408 <span class="comment"></span> <a name="l00409"></a>00409 <span class="comment"> /// Temporaries (to reduce allocation overhead).</span> <a name="l00410"></a>00410 <span class="comment"></span> <span class="comment">// Each variable is prefixed by the method in which is used:</span> <a name="l00411"></a>00411 <a name="l00412"></a><a class="code" href="classMiniSat_1_1Solver.html#ae2fd56e35cc318aed56d10fc7e5af484">00412</a> std::vector<char> <a class="code" href="classMiniSat_1_1Solver.html#ae2fd56e35cc318aed56d10fc7e5af484" title="Temporaries (to reduce allocation overhead).">d_analyze_seen</a>; <a name="l00413"></a><a class="code" href="classMiniSat_1_1Solver.html#aede680f26ad5344891484b6f821de222">00413</a> std::vector<Lit> <a class="code" href="classMiniSat_1_1Solver.html#aede680f26ad5344891484b6f821de222">d_analyze_stack</a>; <a name="l00414"></a><a class="code" href="classMiniSat_1_1Solver.html#a81ed0225fec06bae415c6d86c86781f1">00414</a> std::vector<Lit> <a class="code" href="classMiniSat_1_1Solver.html#a81ed0225fec06bae415c6d86c86781f1">d_analyze_redundant</a>; <a name="l00415"></a>00415 <a name="l00416"></a>00416 <span class="comment">// solver statistics</span> <a name="l00417"></a><a class="code" href="classMiniSat_1_1Solver.html#ac2c0d8b62a85616add0930b4947c8f96">00417</a> <a class="code" href="structMiniSat_1_1SolverStats.html">SolverStats</a> <a class="code" href="classMiniSat_1_1Solver.html#ac2c0d8b62a85616add0930b4947c8f96">d_stats</a>; <a name="l00418"></a>00418 <a name="l00419"></a>00419 <a name="l00420"></a>00420 <span class="keyword">protected</span>:<span class="comment"></span> <a name="l00421"></a>00421 <span class="comment"> /// Search:</span> <a name="l00422"></a>00422 <span class="comment"></span> <a name="l00423"></a>00423 <span class="comment">// the current decision level</span> <a name="l00424"></a><a class="code" href="classMiniSat_1_1Solver.html#a18c18c858ec2b635eede59e396f3b102">00424</a> <span class="keywordtype">int</span> <a class="code" href="classMiniSat_1_1Solver.html#a18c18c858ec2b635eede59e396f3b102" title="Search:">decisionLevel</a>()<span class="keyword"> const </span>{ <span class="keywordflow">return</span> (<span class="keywordtype">int</span>)<a class="code" href="classMiniSat_1_1Solver.html#abf42fb28430f7b099c65c4e9b28ffb09">d_trail_lim</a>.size(); } <a name="l00425"></a>00425 <a name="l00426"></a>00426 <span class="comment">// decision on p</span> <a name="l00427"></a>00427 <span class="keywordtype">bool</span> <a class="code" href="classMiniSat_1_1Solver.html#a48e255f2f05f6d56518c8e8925b30639">assume</a>(<a class="code" href="classMiniSat_1_1Lit.html">Lit</a> p); <a name="l00428"></a>00428 <a name="l00429"></a>00429 <span class="comment">// queue a literal for propagation, at decisionLevel implied by reason</span> <a name="l00430"></a>00430 <span class="keywordtype">bool</span> <a class="code" href="classMiniSat_1_1Solver.html#a7884b17f0f740781df424864717efac2">enqueue</a>(<a class="code" href="classMiniSat_1_1Lit.html">Lit</a> fact, <span class="keywordtype">int</span> <a class="code" href="classMiniSat_1_1Solver.html#a18c18c858ec2b635eede59e396f3b102" title="Search:">decisionLevel</a>, <a class="code" href="classMiniSat_1_1Clause.html">Clause</a>* reason); <a name="l00431"></a>00431 <a name="l00432"></a>00432 <span class="comment">// propagate a literal (the head of the propagation queue)</span> <a name="l00433"></a>00433 <span class="keywordtype">void</span> <a class="code" href="classMiniSat_1_1Solver.html#aace9125740233af99f0de4e0288b075e">propagate</a>(); <a name="l00434"></a>00434 <a name="l00435"></a>00435 <span class="comment">// perform a lookahead on the best split literals.</span> <a name="l00436"></a>00436 <span class="comment">// this is done on the propositional level only, without involving theories.</span> <a name="l00437"></a>00437 <span class="keywordtype">void</span> <a class="code" href="classMiniSat_1_1Solver.html#a5ff984eddca26831d3057733f3848fdf">propLookahead</a>(<span class="keyword">const</span> <a class="code" href="structMiniSat_1_1SearchParams.html">SearchParams</a>& params); <a name="l00438"></a>00438 <span class="comment"></span> <a name="l00439"></a>00439 <span class="comment"> /// Conflict handling</span> <a name="l00440"></a>00440 <span class="comment"></span> <a name="l00441"></a>00441 <span class="comment">// conflict analysis: returns conflict clause and level to backtrack to</span> <a name="l00442"></a>00442 <span class="comment">// clause implies its first literal in level out_btlevel</span> <a name="l00443"></a>00443 <a class="code" href="classMiniSat_1_1Clause.html">Clause</a>* <a class="code" href="classMiniSat_1_1Solver.html#ab4bacf381f8980c23eb2184c712b882d" title="Conflict handling.">analyze</a>(<span class="keywordtype">int</span>& out_btlevel); <a name="l00444"></a>00444 <a name="l00445"></a>00445 <span class="comment">// conflict analysis: conflict clause minimization (helper method for 'analyze()')</span> <a name="l00446"></a>00446 <span class="keywordtype">void</span> <a class="code" href="classMiniSat_1_1Solver.html#affb21521fe39f5d003e61180dc3f5f3c">analyze_minimize</a>(std::vector<Lit>& out_learnt, <a class="code" href="classMiniSat_1_1Inference.html">Inference</a>* inference, <span class="keywordtype">int</span>& pushID); <a name="l00447"></a>00447 <a name="l00448"></a>00448 <span class="comment">// conflict analysis: conflict clause minimization (helper method for 'analyze()')</span> <a name="l00449"></a>00449 <span class="keywordtype">bool</span> <a class="code" href="classMiniSat_1_1Solver.html#ab91573c3ebb667e9e94f30f889598434">analyze_removable</a>(<a class="code" href="classMiniSat_1_1Lit.html">Lit</a> p, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> min_level, <span class="keywordtype">int</span> pushID); <a name="l00450"></a>00450 <a name="l00451"></a>00451 <span class="comment">// backtrack to level, add conflict clause</span> <a name="l00452"></a>00452 <span class="keywordtype">void</span> <a class="code" href="classMiniSat_1_1Solver.html#a49421463a8047553ffbd5fc9d04c0ad8">backtrack</a>(<span class="keywordtype">int</span> level, <a class="code" href="classMiniSat_1_1Clause.html">Clause</a>* clause); <a name="l00453"></a>00453 <a name="l00454"></a>00454 <span class="comment">// is the current state conflicting, i.e. is there a conflicting clause?</span> <a name="l00455"></a>00455 <span class="keywordtype">bool</span> <a class="code" href="classMiniSat_1_1Solver.html#a41ac244ff15b83ca4a863ee85cf27814">isConflicting</a>() <span class="keyword">const</span>; <a name="l00456"></a>00456 <a name="l00457"></a>00457 <span class="comment">// mark this clause as conflicting</span> <a name="l00458"></a>00458 <span class="keywordtype">void</span> <a class="code" href="classMiniSat_1_1Solver.html#abe256fba9eac8bb202c8c58c87b1bb82">updateConflict</a>(<a class="code" href="classMiniSat_1_1Clause.html">Clause</a>* clause); <a name="l00459"></a>00459 <a name="l00460"></a>00460 <span class="comment">// returns the level in which this clause implies its first literal.</span> <a name="l00461"></a>00461 <span class="comment">// precondition: all clause literals except for the first must be falsified.</span> <a name="l00462"></a>00462 <span class="keywordtype">int</span> <a class="code" href="classMiniSat_1_1Solver.html#a4d5144ec81209e86f7374972b8a78aa0">getImplicationLevel</a>(<span class="keyword">const</span> <a class="code" href="classMiniSat_1_1Clause.html">Clause</a>& clause) <span class="keyword">const</span>; <a name="l00463"></a>00463 <a name="l00464"></a>00464 <span class="comment">// returns the level in which this clause became falsified</span> <a name="l00465"></a>00465 <span class="comment">// (or at least fully assigned).</span> <a name="l00466"></a>00466 <span class="comment">// precondition: no clause literal is undefined.</span> <a name="l00467"></a>00467 <span class="keywordtype">int</span> <a class="code" href="classMiniSat_1_1Solver.html#a0d0c1aef5c834bc7ba7682ac3fe5b59c">getConflictLevel</a>(<span class="keyword">const</span> <a class="code" href="classMiniSat_1_1Clause.html">Clause</a>& clause) <span class="keyword">const</span>; <a name="l00468"></a>00468 <a name="l00469"></a>00469 <span class="comment">// if this literal is a theory implied literal and its explanation has not been retrieved,</span> <a name="l00470"></a>00470 <span class="comment">// then this is done now and the literal's reason is updated.</span> <a name="l00471"></a>00471 <span class="comment">// precondition: literal must be a propagated literal</span> <a name="l00472"></a>00472 <span class="keywordtype">void</span> <a class="code" href="classMiniSat_1_1Solver.html#a22b59f22e9df28fcb892e5873d998c75">resolveTheoryImplication</a>(<a class="code" href="classMiniSat_1_1Lit.html">Lit</a> literal); <a name="l00473"></a>00473 <a name="l00474"></a>00474 <span class="comment"></span> <a name="l00475"></a>00475 <span class="comment"> /// unit propagation</span> <a name="l00476"></a>00476 <span class="comment"></span> <a name="l00477"></a>00477 <span class="comment">// return the watched clauses for a literal</span> <a name="l00478"></a><a class="code" href="classMiniSat_1_1Solver.html#ac8d866ffb2253fdc01fe310558871da3">00478</a> std::vector<Clause*>& <a class="code" href="classMiniSat_1_1Solver.html#ac8d866ffb2253fdc01fe310558871da3" title="unit propagation">getWatches</a>(<a class="code" href="classMiniSat_1_1Lit.html">Lit</a> literal) { <span class="keywordflow">return</span> <a class="code" href="classMiniSat_1_1Solver.html#a6a3e831d47c15ac42fe7a7002c276c0e" title="variable assignments, and pending propagations">d_watches</a>[literal.<a class="code" href="classMiniSat_1_1Lit.html#a91d2d44275fe1e43cee4ce673b2ab41d">index</a>()]; }; <a name="l00479"></a>00479 <a name="l00480"></a>00480 <span class="comment">// return the watched clauses for a literal</span> <a name="l00481"></a><a class="code" href="classMiniSat_1_1Solver.html#a8987b0395fc1f850ee7b748e9685560a">00481</a> <span class="keyword">const</span> std::vector<Clause*>& <a class="code" href="classMiniSat_1_1Solver.html#a8987b0395fc1f850ee7b748e9685560a">getWatches</a>(<a class="code" href="classMiniSat_1_1Lit.html">Lit</a> literal)<span class="keyword"> const </span>{ <span class="keywordflow">return</span> <a class="code" href="classMiniSat_1_1Solver.html#a6a3e831d47c15ac42fe7a7002c276c0e" title="variable assignments, and pending propagations">d_watches</a>[literal.<a class="code" href="classMiniSat_1_1Lit.html#a91d2d44275fe1e43cee4ce673b2ab41d">index</a>()]; }; <a name="l00482"></a>00482 <a name="l00483"></a>00483 <span class="comment">// adds a watch to a clause literal</span> <a name="l00484"></a>00484 <span class="comment">// precondition: literal must be one of the first two literals in clause</span> <a name="l00485"></a><a class="code" href="classMiniSat_1_1Solver.html#af3891961fe824bc91b47b59ee1e4a90b">00485</a> <span class="keywordtype">void</span> <a class="code" href="classMiniSat_1_1Solver.html#af3891961fe824bc91b47b59ee1e4a90b">addWatch</a>(<a class="code" href="classMiniSat_1_1Lit.html">Lit</a> literal, <a class="code" href="classMiniSat_1_1Clause.html">Clause</a>* clause) { <a class="code" href="classMiniSat_1_1Solver.html#ac8d866ffb2253fdc01fe310558871da3" title="unit propagation">getWatches</a>(literal).push_back(clause); }; <a name="l00486"></a>00486 <a name="l00487"></a>00487 <span class="comment">// removes the clause from the list of watched clauses</span> <a name="l00488"></a>00488 <span class="keywordtype">void</span> <a class="code" href="classMiniSat_1_1Solver.html#a94c3f4932f4c9d17b4a6dc1839c813f5" title="Conflict handling.">removeWatch</a>(std::vector<Clause*>& ws, <a class="code" href="classMiniSat_1_1Clause.html">Clause</a>* elem); <a name="l00489"></a>00489 <a name="l00490"></a>00490 <span class="comment"></span> <a name="l00491"></a>00491 <span class="comment"> /// Operations on clauses:</span> <a name="l00492"></a>00492 <span class="comment"></span> <a name="l00493"></a>00493 <span class="comment">// registers a variable - any variable has to be registered before it is used in the search.</span> <a name="l00494"></a>00494 <span class="keywordtype">void</span> <a class="code" href="classMiniSat_1_1Solver.html#a7a11f6c3676dd169d093a4e7c5af5299" title="Operations on clauses:">registerVar</a>(<a class="code" href="namespaceMiniSat.html#a0d9722420b2afd308dceda22c1b05a5e">Var</a> var); <a name="l00495"></a>00495 <a name="l00496"></a>00496 <span class="comment">// checks if a variable is already registered (pop can remove a variable)</span> <a name="l00497"></a>00497 <span class="keywordtype">bool</span> <a class="code" href="classMiniSat_1_1Solver.html#a31a0f344abc3fd65ee540f954b014f62" title="Operations on clauses:">isRegistered</a>(<a class="code" href="namespaceMiniSat.html#a0d9722420b2afd308dceda22c1b05a5e">Var</a> var); <a name="l00498"></a>00498 <a name="l00499"></a>00499 <span class="comment">// creates/adds a clause or a lemma and returns it; registers all variables,</span> <a name="l00500"></a>00500 <span class="comment">// used by all other addClause methods</span> <a name="l00501"></a>00501 <span class="keywordtype">void</span> <a class="code" href="classMiniSat_1_1Solver.html#a36711ef6cb28057fa6f00235f58c03ff">addClause</a>(std::vector<Lit>& literals, <a class="code" href="classCVC3_1_1Theorem.html">CVC3::Theorem</a> theorem, <span class="keywordtype">int</span> clauseID); <a name="l00502"></a>00502 <a name="l00503"></a>00503 <span class="comment">// adds a clause or a lemma to the solver, watched lists, and checks if it is unit/conflicting</span> <a name="l00504"></a>00504 <span class="comment">// clause activity heuristics are updated.</span> <a name="l00505"></a>00505 <span class="comment">// precondition: all variables are registered</span> <a name="l00506"></a>00506 <span class="comment">// precondition: a lemma is propagating its first literal</span> <a name="l00507"></a>00507 <span class="keywordtype">void</span> <a class="code" href="classMiniSat_1_1Solver.html#aa0d36a2c07c88350dd9d54e62b3cef7b">insertClause</a>(<a class="code" href="classMiniSat_1_1Clause.html">Clause</a>* clause); <a name="l00508"></a>00508 <a name="l00509"></a>00509 <span class="comment">// add a lemma which has not been computed just now (see push(), createFrom()),</span> <a name="l00510"></a>00510 <span class="comment">// so it is not necessary propagating (which is assumed by insertClause())</span> <a name="l00511"></a>00511 <span class="keywordtype">void</span> <a class="code" href="classMiniSat_1_1Solver.html#a2ba80609ff72dbd93ae116a25923808d">insertLemma</a>(<span class="keyword">const</span> <a class="code" href="classMiniSat_1_1Clause.html">Clause</a>* lemma, <span class="keywordtype">int</span> clauseID, <span class="keywordtype">int</span> pushID); <a name="l00512"></a>00512 <a name="l00513"></a>00513 <span class="comment">// simplify clause based on root level assignment</span> <a name="l00514"></a>00514 <span class="comment">// precondition: all variables are registered</span> <a name="l00515"></a>00515 <span class="keywordtype">bool</span> <a class="code" href="classMiniSat_1_1Solver.html#abe63b049c7c54b810266baffb315c89b">simplifyClause</a>(std::vector<Lit>& literals, <span class="keywordtype">int</span> clausePushID) <span class="keyword">const</span>; <a name="l00516"></a>00516 <a name="l00517"></a>00517 <span class="comment">// order a clause such that it is consistent with the current assignment,</span> <a name="l00518"></a>00518 <span class="comment">// i.e. the two first literals can be taken as the watched literals.</span> <a name="l00519"></a>00519 <span class="comment">// precondition: all variables are registered</span> <a name="l00520"></a>00520 <span class="keywordtype">void</span> <a class="code" href="classMiniSat_1_1Solver.html#aa8b5dfa883cace427d4b8b89769ca6df">orderClause</a>(std::vector<Lit>& literals) <span class="keyword">const</span>; <a name="l00521"></a>00521 <a name="l00522"></a>00522 <span class="comment">// deallocate a clause, and removes it from watches if just_dealloc is false</span> <a name="l00523"></a>00523 <span class="keywordtype">void</span> <span class="keyword">remove</span>(<a class="code" href="classMiniSat_1_1Clause.html">Clause</a>* c, <span class="keywordtype">bool</span> just_dealloc = <span class="keyword">false</span>); <a name="l00524"></a>00524 <a name="l00525"></a>00525 <span class="comment">// assuming that the literal is implied at the root level:</span> <a name="l00526"></a>00526 <span class="comment">// will the literal be assigned as long as the clause exists, even over pops?</span> <a name="l00527"></a>00527 <span class="keywordtype">bool</span> <a class="code" href="classMiniSat_1_1Solver.html#a871c1c054262f9673518c46f7efc8450">isImpliedAt</a>(<a class="code" href="classMiniSat_1_1Lit.html">Lit</a> lit, <span class="keywordtype">int</span> clausePushID) <span class="keyword">const</span>; <a name="l00528"></a>00528 <a name="l00529"></a>00529 <span class="comment">// is this clause permanently satisfied?</span> <a name="l00530"></a>00530 <span class="keywordtype">bool</span> <a class="code" href="classMiniSat_1_1Solver.html#ad64d6215811b4c4ca6c5ac86da4c787d">isPermSatisfied</a>(<a class="code" href="classMiniSat_1_1Clause.html">Clause</a>* c) <span class="keyword">const</span>; <a name="l00531"></a>00531 <a name="l00532"></a>00532 <a name="l00533"></a>00533 <span class="comment">// Push / Pop</span> <a name="l00534"></a>00534 <a name="l00535"></a>00535 <span class="comment">// sets the d_pushIDs entry of var implied by from</span> <a name="l00536"></a>00536 <span class="keywordtype">void</span> <a class="code" href="classMiniSat_1_1Solver.html#a07e86f7cb7f6a34c4e28df990cbf43d1">setPushID</a>(<a class="code" href="namespaceMiniSat.html#a0d9722420b2afd308dceda22c1b05a5e">Var</a> var, <a class="code" href="classMiniSat_1_1Clause.html">Clause</a>* from); <a name="l00537"></a>00537 <a name="l00538"></a>00538 <span class="comment">// returns the d_pushIDs entry of a var</span> <a name="l00539"></a>00539 <span class="comment">// makes only sense for a var with a defined value</span> <a name="l00540"></a><a class="code" href="classMiniSat_1_1Solver.html#a4f5805d21238ad316845059fb378a05f">00540</a> <span class="keywordtype">int</span> <a class="code" href="classMiniSat_1_1Solver.html#a4f5805d21238ad316845059fb378a05f">getPushID</a>(<a class="code" href="namespaceMiniSat.html#a0d9722420b2afd308dceda22c1b05a5e">Var</a> var)<span class="keyword"> const </span>{ <span class="keywordflow">return</span> <a class="code" href="classMiniSat_1_1Solver.html#ab0b2d4e87d57046e30c2cb3554925e2b">d_pushIDs</a>[var]; } <a name="l00541"></a><a class="code" href="classMiniSat_1_1Solver.html#aa095aa10adf85a246b525e0bc717e942">00541</a> <span class="keywordtype">int</span> <a class="code" href="classMiniSat_1_1Solver.html#aa095aa10adf85a246b525e0bc717e942">getPushID</a>(<a class="code" href="classMiniSat_1_1Lit.html">Lit</a> lit)<span class="keyword"> const </span>{ <span class="keywordflow">return</span> <a class="code" href="classMiniSat_1_1Solver.html#aa095aa10adf85a246b525e0bc717e942">getPushID</a>(lit.<a class="code" href="classMiniSat_1_1Lit.html#a952944c0a85fca7f8db8b532a72b3fda">var</a>()); } <a name="l00542"></a>00542 <a name="l00543"></a>00543 <span class="comment">// pop the most recent push</span> <a name="l00544"></a>00544 <span class="keywordtype">void</span> <a class="code" href="classMiniSat_1_1Solver.html#a2f75013fed205f5b38cd23b9d87dcd1a">pop</a>(); <a name="l00545"></a>00545 <span class="keywordtype">void</span> <a class="code" href="classMiniSat_1_1Solver.html#a6662641d5c0dea8d89041f5cf9dbc4af">popClauses</a>(<span class="keyword">const</span> <a class="code" href="structMiniSat_1_1PushEntry.html">PushEntry</a>& pushEntry, std::vector<Clause*>& clauses); <a name="l00546"></a>00546 <a name="l00547"></a>00547 <span class="comment"></span> <a name="l00548"></a>00548 <span class="comment"> /// Activity:</span> <a name="l00549"></a>00549 <span class="comment"></span> <a name="l00550"></a><a class="code" href="classMiniSat_1_1Solver.html#ab4af8739e981ec3caaa5a20ef1eb2f0f">00550</a> <span class="keywordtype">void</span> <a class="code" href="classMiniSat_1_1Solver.html#ab4af8739e981ec3caaa5a20ef1eb2f0f" title="Activity:">varBumpActivity</a>(<a class="code" href="classMiniSat_1_1Lit.html">Lit</a> p) { <a name="l00551"></a>00551 <span class="keywordflow">if</span> (<a class="code" href="classMiniSat_1_1Solver.html#a354cacc000d52901cb2a60d1fe659d26">d_var_decay</a> < 0) <span class="keywordflow">return</span>; <span class="comment">// (negative decay means static variable order -- don't bump)</span> <a name="l00552"></a>00552 <span class="keywordflow">if</span> ( (<a class="code" href="classMiniSat_1_1Solver.html#a0765ad8a98718bb5523e487e32d66ae1">d_activity</a>[p.<a class="code" href="classMiniSat_1_1Lit.html#a952944c0a85fca7f8db8b532a72b3fda">var</a>()] += <a class="code" href="classMiniSat_1_1Solver.html#aa9cba0f1df8f31b5ae94f2ce0ccb290f">d_var_inc</a>) > 1e100 ) <a class="code" href="classMiniSat_1_1Solver.html#a711410b67cec21e4fc1480ea6490f4f2" title="Activity.">varRescaleActivity</a>(); <a name="l00553"></a>00553 <a class="code" href="classMiniSat_1_1Solver.html#aab79cd4bf5792f72c191d8149e77bc93">d_order</a>.<a class="code" href="classMiniSat_1_1VarOrder.html#a75869a564989c014a16d43f4422f0316">update</a>(p.<a class="code" href="classMiniSat_1_1Lit.html#a952944c0a85fca7f8db8b532a72b3fda">var</a>()); } <a name="l00554"></a><a class="code" href="classMiniSat_1_1Solver.html#a91d54211b76e271e6838b57fca9ecfad">00554</a> <span class="keywordtype">void</span> <a class="code" href="classMiniSat_1_1Solver.html#a91d54211b76e271e6838b57fca9ecfad">varDecayActivity</a> () { <span class="keywordflow">if</span> (<a class="code" href="classMiniSat_1_1Solver.html#a354cacc000d52901cb2a60d1fe659d26">d_var_decay</a> >= 0) <a class="code" href="classMiniSat_1_1Solver.html#aa9cba0f1df8f31b5ae94f2ce0ccb290f">d_var_inc</a> *= <a class="code" href="classMiniSat_1_1Solver.html#a354cacc000d52901cb2a60d1fe659d26">d_var_decay</a>; } <a name="l00555"></a>00555 <span class="keywordtype">void</span> <a class="code" href="classMiniSat_1_1Solver.html#a711410b67cec21e4fc1480ea6490f4f2" title="Activity.">varRescaleActivity</a>(); <a name="l00556"></a><a class="code" href="classMiniSat_1_1Solver.html#a3e6ce9dc49e278926bfcc32289a343c1">00556</a> <span class="keywordtype">void</span> <a class="code" href="classMiniSat_1_1Solver.html#a3e6ce9dc49e278926bfcc32289a343c1">claDecayActivity</a>() { <a class="code" href="classMiniSat_1_1Solver.html#a5b10958ebb6b146f8cfb2d6ec08ab667" title="heuristics">d_cla_inc</a> *= <a class="code" href="classMiniSat_1_1Solver.html#a3b0e8d36281ddcfefb54812accad5a55">d_cla_decay</a>; } <a name="l00557"></a>00557 <span class="keywordtype">void</span> <a class="code" href="classMiniSat_1_1Solver.html#a3cdc4675e024f72e82d718596159456d">claRescaleActivity</a>() ; <a name="l00558"></a><a class="code" href="classMiniSat_1_1Solver.html#a4154a7c87f54bcbf48e8e1689dae68a9">00558</a> <span class="keywordtype">void</span> <a class="code" href="classMiniSat_1_1Solver.html#a4154a7c87f54bcbf48e8e1689dae68a9">claBumpActivity</a> (<a class="code" href="classMiniSat_1_1Clause.html">Clause</a>* c) { <a name="l00559"></a>00559 <span class="keywordtype">float</span> act = c-><a class="code" href="classMiniSat_1_1Clause.html#af64021472c748c6adbfb88238cae5a9d">activity</a>() + (float)<a class="code" href="classMiniSat_1_1Solver.html#a5b10958ebb6b146f8cfb2d6ec08ab667" title="heuristics">d_cla_inc</a>; <a name="l00560"></a>00560 c-><a class="code" href="classMiniSat_1_1Clause.html#a013f54f33ca6995dea2c116725d34258">setActivity</a>(act); <a name="l00561"></a>00561 <span class="keywordflow">if</span> (act > 1e20) <a class="code" href="classMiniSat_1_1Solver.html#a3cdc4675e024f72e82d718596159456d">claRescaleActivity</a>(); <a name="l00562"></a>00562 } <a name="l00563"></a>00563 <a name="l00564"></a>00564 <a name="l00565"></a>00565 <span class="comment"></span> <a name="l00566"></a>00566 <span class="comment"> /// debugging</span> <a name="l00567"></a>00567 <span class="comment"></span> <a name="l00568"></a>00568 <span class="comment">// are all clauses (excluding lemmas) satisfied?</span> <a name="l00569"></a>00569 <span class="keywordtype">bool</span> <a class="code" href="classMiniSat_1_1Solver.html#a4d58130f36a501e919bb82f5f1438e32" title="debugging">allClausesSatisfied</a>(); <a name="l00570"></a>00570 <a name="l00571"></a>00571 <span class="comment">// checks that the first two literals of a clause are watched</span> <a name="l00572"></a>00572 <span class="keywordtype">void</span> <a class="code" href="classMiniSat_1_1Solver.html#a6b4bb1db7b767e1368884b178f523dcf">checkWatched</a>(<span class="keyword">const</span> <a class="code" href="classMiniSat_1_1Clause.html">Clause</a>& clause) <span class="keyword">const</span>; <a name="l00573"></a>00573 <span class="keywordtype">void</span> <a class="code" href="classMiniSat_1_1Solver.html#a6b4bb1db7b767e1368884b178f523dcf">checkWatched</a>() <span class="keyword">const</span>; <a name="l00574"></a>00574 <a name="l00575"></a>00575 <span class="comment">// checks that for each clause one of these holds:</span> <a name="l00576"></a>00576 <span class="comment">// 1) the first two literals are undefined</span> <a name="l00577"></a>00577 <span class="comment">// 2) one of the first two literals is satisfied</span> <a name="l00578"></a>00578 <span class="comment">// 3) the first literal is undefined and all other literals are falsified</span> <a name="l00579"></a>00579 <span class="comment">// 4) all literals are falsified</span> <a name="l00580"></a>00580 <span class="keywordtype">void</span> <a class="code" href="classMiniSat_1_1Solver.html#ad4c405a5b6aac64b41c190aaa68004aa">checkClause</a>(<span class="keyword">const</span> <a class="code" href="classMiniSat_1_1Clause.html">Clause</a>& clause) <span class="keyword">const</span>; <a name="l00581"></a>00581 <span class="keywordtype">void</span> <a class="code" href="classMiniSat_1_1Solver.html#a9e152e0ed1d83a51f7886df8cd5fe681">checkClauses</a>() <span class="keyword">const</span>; <a name="l00582"></a>00582 <a name="l00583"></a>00583 <span class="comment">// checks that each literal in the context(trail) is either</span> <a name="l00584"></a>00584 <span class="comment">// 1) a decision</span> <a name="l00585"></a>00585 <span class="comment">// 2) or implied by previous context literals</span> <a name="l00586"></a>00586 <span class="keywordtype">void</span> <a class="code" href="classMiniSat_1_1Solver.html#a9457fd91045b9496ef5bdcd1a93fcae5">checkTrail</a>() <span class="keyword">const</span>; <a name="l00587"></a>00587 <a name="l00588"></a>00588 <span class="comment">// print the current propagation step</span> <a name="l00589"></a>00589 <span class="keywordtype">void</span> <a class="code" href="classMiniSat_1_1Solver.html#a776adc363c0056e2077fbe659ae6f709">protocolPropagation</a>() <span class="keyword">const</span>; <a name="l00590"></a>00590 <a name="l00591"></a>00591 <a name="l00592"></a>00592 <span class="keyword">public</span>:<span class="comment"></span> <a name="l00593"></a>00593 <span class="comment"> /// Initialization</span> <a name="l00594"></a>00594 <span class="comment"></span> <a name="l00595"></a>00595 <span class="comment">// assumes that this is the SAT solver in control of CVC theories,</span> <a name="l00596"></a>00596 <span class="comment">// so it immediately pushs a new theory context.</span> <a name="l00597"></a>00597 <span class="comment">//</span> <a name="l00598"></a>00598 <span class="comment">// uses MiniSat's internal decision heuristics if decider is NULL</span> <a name="l00599"></a>00599 <span class="comment">//</span> <a name="l00600"></a>00600 <span class="comment">// if logDerivation then the derivation will be logged in getDerivation(),</span> <a name="l00601"></a>00601 <span class="comment">// which provides a prove if the empty clause is derived.</span> <a name="l00602"></a>00602 <a class="code" href="classMiniSat_1_1Solver.html#ae192cadcb9b0cace709e816612b42f02" title="Initialization.">Solver</a>(<a class="code" href="classSAT_1_1DPLLT_1_1TheoryAPI.html">SAT::DPLLT::TheoryAPI</a>* theoryAPI, <a class="code" href="classSAT_1_1DPLLT_1_1Decider.html">SAT::DPLLT::Decider</a>* decider, <a name="l00603"></a>00603 <span class="keywordtype">bool</span> logDerivation); <a name="l00604"></a>00604 <a name="l00605"></a>00605 <span class="comment">// copies clauses, assignment as unit clauses, and lemmas</span> <a name="l00606"></a>00606 <span class="comment">// will be in root level</span> <a name="l00607"></a>00607 <span class="keyword">static</span> <a class="code" href="classMiniSat_1_1Solver.html">Solver</a>* <a class="code" href="classMiniSat_1_1Solver.html#a7fce9c6a705405959f91d559a6e06ee4">createFrom</a>(<span class="keyword">const</span> <a class="code" href="classMiniSat_1_1Solver.html">Solver</a>* solver); <a name="l00608"></a>00608 <a name="l00609"></a>00609 <span class="comment">// releases all memory, but does not pop theories.</span> <a name="l00610"></a>00610 <span class="comment">// this is according to the semantics expected by CVC:</span> <a name="l00611"></a>00611 <span class="comment">// is the solver detects unsatisfiability, it pops all theory levels.</span> <a name="l00612"></a>00612 <span class="comment">// otherwise the caller is responsible for resetting the theory levels.</span> <a name="l00613"></a>00613 <a class="code" href="classMiniSat_1_1Solver.html#aba52d3c92fafceb6fe39f937f2d73db3">~Solver</a>(); <a name="l00614"></a>00614 <a name="l00615"></a>00615 <span class="comment"></span> <a name="l00616"></a>00616 <span class="comment"> /// problem specification</span> <a name="l00617"></a>00617 <span class="comment"></span> <a name="l00618"></a>00618 <span class="comment">// converts cvc clause into MiniSat clause with the given id.</span> <a name="l00619"></a>00619 <span class="comment">// returns NULL on permanently satisfied clause, i.e. clause containing 'true'</span> <a name="l00620"></a>00620 <a class="code" href="classMiniSat_1_1Clause.html">Clause</a>* <a class="code" href="classMiniSat_1_1Solver.html#abbb1190222cc3ad99638caf6e86ee698" title="problem specification">cvcToMiniSat</a>(<span class="keyword">const</span> <a class="code" href="classSAT_1_1Clause.html">SAT::Clause</a>& clause, <span class="keywordtype">int</span> <span class="keywordtype">id</span>); <a name="l00621"></a>00621 <a name="l00622"></a>00622 <span class="comment">// adds a unit clause given as a literal</span> <a name="l00623"></a>00623 <span class="keywordtype">void</span> <a class="code" href="classMiniSat_1_1Solver.html#a36711ef6cb28057fa6f00235f58c03ff">addClause</a>(<a class="code" href="classMiniSat_1_1Lit.html">Lit</a> p, <a class="code" href="classCVC3_1_1Theorem.html">CVC3::Theorem</a> theorem); <a name="l00624"></a>00624 <a name="l00625"></a>00625 <span class="comment">// adds a (copy of) clause, uses original clause id if wished</span> <a name="l00626"></a>00626 <span class="keywordtype">void</span> <a class="code" href="classMiniSat_1_1Solver.html#a36711ef6cb28057fa6f00235f58c03ff">addClause</a>(<span class="keyword">const</span> <a class="code" href="classMiniSat_1_1Clause.html">Clause</a>& clause, <span class="keywordtype">bool</span> keepClauseID); <a name="l00627"></a>00627 <a name="l00628"></a>00628 <span class="comment">// adds a CVC clause</span> <a name="l00629"></a>00629 <span class="keywordtype">void</span> <a class="code" href="classMiniSat_1_1Solver.html#a36711ef6cb28057fa6f00235f58c03ff">addClause</a>(<span class="keyword">const</span> <a class="code" href="classSAT_1_1Clause.html">SAT::Clause</a>& clause, <span class="keywordtype">bool</span> isTheoryClause); <a name="l00630"></a>00630 <a name="l00631"></a>00631 <span class="comment">// adds a CVC formula</span> <a name="l00632"></a>00632 <span class="keywordtype">void</span> <a class="code" href="classMiniSat_1_1Solver.html#ab7ceeed839df517256ce77c126f28e00">addFormula</a>(<span class="keyword">const</span> <a class="code" href="classSAT_1_1CNF__Formula.html">SAT::CNF_Formula</a>& cnf, <span class="keywordtype">bool</span> isTheoryClause); <a name="l00633"></a>00633 <a name="l00634"></a>00634 <span class="comment">// returns a unique id for a new clause</span> <a name="l00635"></a>00635 <span class="comment">// (addClause will then use the negation for theory clauses)</span> <a name="l00636"></a><a class="code" href="classMiniSat_1_1Solver.html#a7323aff4aaa93c01e6008e8e033d2b8f">00636</a> <span class="keywordtype">int</span> <a class="code" href="classMiniSat_1_1Solver.html#a7323aff4aaa93c01e6008e8e033d2b8f">nextClauseID</a>() { <a name="l00637"></a>00637 <a class="code" href="debug_8h.html#a2637b2fffa22e3c9fad40cda8fcc3bce" title="If something goes horribly wrong, print a message and abort immediately with exit(1).">FatalAssert</a>(<a class="code" href="classMiniSat_1_1Solver.html#ad6e3d6a97a4ae9dda9ac7b9bed97bed8" title="Clauses.">d_clauseIDCounter</a> >= 0, <span class="stringliteral">"MiniSat::Solver::nextClauseID: overflow"</span>); <a name="l00638"></a>00638 <span class="keywordflow">return</span> <a class="code" href="classMiniSat_1_1Solver.html#ad6e3d6a97a4ae9dda9ac7b9bed97bed8" title="Clauses.">d_clauseIDCounter</a>++; <a name="l00639"></a>00639 }; <a name="l00640"></a>00640 <a name="l00641"></a>00641 <span class="comment">// removes permanently satisfied clauses</span> <a name="l00642"></a>00642 <span class="keywordtype">void</span> <a class="code" href="classMiniSat_1_1Solver.html#a4e6b8a057747d66f650e6e785f8fc334">simplifyDB</a>(); <a name="l00643"></a>00643 <a name="l00644"></a>00644 <span class="comment">// removes 'bad' lemmas</span> <a name="l00645"></a>00645 <span class="keywordtype">void</span> <a class="code" href="classMiniSat_1_1Solver.html#a62eea2c00917497fbfb843bf9ca4482e">reduceDB</a>(); <a name="l00646"></a>00646 <a name="l00647"></a>00647 <span class="comment"></span> <a name="l00648"></a>00648 <span class="comment"> /// search</span> <a name="l00649"></a>00649 <span class="comment"></span> <a name="l00650"></a>00650 <span class="comment">// (continue) search with current clause set and context</span> <a name="l00651"></a>00651 <span class="comment">// until model is found (in d_trail), or unsatisfiability detected.</span> <a name="l00652"></a>00652 <span class="comment">// </span> <a name="l00653"></a>00653 <span class="comment">// between two calls clauses may be added,</span> <a name="l00654"></a>00654 <span class="comment">// but everything else (including the theories) should remain untouched.</span> <a name="l00655"></a>00655 <span class="comment">//</span> <a name="l00656"></a>00656 <span class="comment">// the prover becomes essentially unusable if unsatisfiability is detected,</span> <a name="l00657"></a>00657 <span class="comment">// only data may be retrieved (clauses, statistics, proof, ...)</span> <a name="l00658"></a>00658 <a class="code" href="namespaceCVC3.html#a060d21b3207cc3471e24f8dbcff3498b">CVC3::QueryResult</a> <a class="code" href="classMiniSat_1_1Solver.html#af43d31ac67426e7b3b699491b02d62c1" title="search">search</a>(); <a name="l00659"></a>00659 <a name="l00660"></a>00660 <span class="comment">// returns a resolution proof for unsatisfiability if</span> <a name="l00661"></a>00661 <span class="comment">// - createProof was true in the call to the constructor</span> <a name="l00662"></a>00662 <span class="comment">// - the last call to search returned status UNSATISFIABLE</span> <a name="l00663"></a>00663 <span class="comment">// returns NULL otherwise</span> <a name="l00664"></a>00664 <a class="code" href="classMiniSat_1_1Derivation.html">Derivation</a>* <a class="code" href="classMiniSat_1_1Solver.html#ac051d3f7a6f6e93269769f2ff8eb9878">getProof</a>(); <a name="l00665"></a>00665 <a name="l00666"></a>00666 <span class="comment">// is the solver currently in a search state?</span> <a name="l00667"></a>00667 <span class="comment">// i.e. search() has been called and not been undone by a pop request.</span> <a name="l00668"></a><a class="code" href="classMiniSat_1_1Solver.html#ae28b9db22e418c5907fb82dbe49a6832">00668</a> <span class="keywordtype">bool</span> <a class="code" href="classMiniSat_1_1Solver.html#ae28b9db22e418c5907fb82dbe49a6832">inSearch</a>()<span class="keyword"> const </span>{ <span class="keywordflow">return</span> <a class="code" href="classMiniSat_1_1Solver.html#a53dec8ba9fc22afeeef701f1a329a669" title="status">d_inSearch</a> && <a class="code" href="classMiniSat_1_1Solver.html#acb6671d85d64f00c04ea17b3b6e144f6">d_popRequests</a> == 0; } <a name="l00669"></a>00669 <a name="l00670"></a>00670 <span class="comment">// is the solver in a consistent state?</span> <a name="l00671"></a><a class="code" href="classMiniSat_1_1Solver.html#a7eb95fc222427a795a3b5ae48e94518e">00671</a> <span class="keywordtype">bool</span> <a class="code" href="classMiniSat_1_1Solver.html#a7eb95fc222427a795a3b5ae48e94518e">isConsistent</a>()<span class="keyword"> const </span>{ <span class="keywordflow">return</span> !<a class="code" href="classMiniSat_1_1Solver.html#a41ac244ff15b83ca4a863ee85cf27814">isConflicting</a>(); } <a name="l00672"></a>00672 <a name="l00673"></a>00673 <a name="l00674"></a>00674 <span class="comment"></span> <a name="l00675"></a>00675 <span class="comment"> /// Push / Pop</span> <a name="l00676"></a>00676 <span class="comment"></span> <a name="l00677"></a>00677 <span class="comment">// push the current solver state</span> <a name="l00678"></a>00678 <span class="comment">// can only be done when solver is not already in a search (inSearch()).</span> <a name="l00679"></a>00679 <span class="keywordtype">void</span> <a class="code" href="classMiniSat_1_1Solver.html#aec12c38c0c17d7067e12da239353ebc8" title="Push / Pop.">push</a>(); <a name="l00680"></a>00680 <a name="l00681"></a>00681 <span class="comment">// pop all theory levels pushed by the solver,</span> <a name="l00682"></a>00682 <span class="comment">// i.e. all (current) decision levels of the solver.</span> <a name="l00683"></a>00683 <span class="keywordtype">void</span> <a class="code" href="classMiniSat_1_1Solver.html#a80f70ef105eabcf61758427d041281d6">popTheories</a>(); <a name="l00684"></a>00684 <a name="l00685"></a>00685 <span class="comment">// request to pop theories - all request are done when doPops is called</span> <a name="l00686"></a>00686 <span class="keywordtype">void</span> <a class="code" href="classMiniSat_1_1Solver.html#a8be8edbecd5a07bd39990ee7ba0918e3">requestPop</a>(); <a name="l00687"></a>00687 <a name="l00688"></a>00688 <span class="comment">// perform all pop requests (calls to requestPop)</span> <a name="l00689"></a>00689 <span class="keywordtype">void</span> <a class="code" href="classMiniSat_1_1Solver.html#a8cc5207e3580ab0f09c6e9c225eaebff">doPops</a>(); <a name="l00690"></a>00690 <a name="l00691"></a>00691 <span class="comment">// has there been a push which hasn't been (requested to be) undone yet?</span> <a name="l00692"></a><a class="code" href="classMiniSat_1_1Solver.html#a1bcf27269a8286f82b3235d982e4724e">00692</a> <span class="keywordtype">bool</span> <a class="code" href="classMiniSat_1_1Solver.html#a1bcf27269a8286f82b3235d982e4724e">inPush</a>()<span class="keyword"> const </span>{ <span class="keywordflow">return</span> <a class="code" href="classMiniSat_1_1Solver.html#a6f9c67d77e57b99fef5de801623245a4" title="Push / Pop.">d_pushes</a>.size() > <a class="code" href="classMiniSat_1_1Solver.html#acb6671d85d64f00c04ea17b3b6e144f6">d_popRequests</a>; } <a name="l00693"></a>00693 <a name="l00694"></a>00694 <a name="l00695"></a>00695 <span class="comment"></span> <a name="l00696"></a>00696 <span class="comment"> /// clauses / assignment</span> <a name="l00697"></a>00697 <span class="comment"></span> <a name="l00698"></a>00698 <span class="comment">// get the current value of a variable/literal</span> <a name="l00699"></a><a class="code" href="classMiniSat_1_1Solver.html#adc9d01899ff6c1eefea8749a1a97309b">00699</a> <a class="code" href="classMiniSat_1_1lbool.html">lbool</a> <a class="code" href="classMiniSat_1_1Solver.html#adc9d01899ff6c1eefea8749a1a97309b" title="clauses / assignment">getValue</a>(<a class="code" href="namespaceMiniSat.html#a0d9722420b2afd308dceda22c1b05a5e">Var</a> x)<span class="keyword"> const </span>{ <span class="keywordflow">return</span> <a class="code" href="namespaceMiniSat.html#a1c28cb1733880d6dbc7aff894cb5527d">toLbool</a>(<a class="code" href="classMiniSat_1_1Solver.html#a8fd906b3d57929f47f9a6eb6740e35e9">d_assigns</a>[x]); } <a name="l00700"></a><a class="code" href="classMiniSat_1_1Solver.html#a2c6d2ce4210d3bfbc3d659dd724d02f0">00700</a> <a class="code" href="classMiniSat_1_1lbool.html">lbool</a> <a class="code" href="classMiniSat_1_1Solver.html#a2c6d2ce4210d3bfbc3d659dd724d02f0">getValue</a>(<a class="code" href="classMiniSat_1_1Lit.html">Lit</a> p)<span class="keyword"> const </span>{ <span class="keywordflow">return</span> p.<a class="code" href="classMiniSat_1_1Lit.html#a75dadacca265ff92462528f29f1fcfd8">sign</a>() ? <a class="code" href="classMiniSat_1_1Solver.html#a2c6d2ce4210d3bfbc3d659dd724d02f0">getValue</a>(p.<a class="code" href="classMiniSat_1_1Lit.html#a952944c0a85fca7f8db8b532a72b3fda">var</a>()) : ~<a class="code" href="classMiniSat_1_1Solver.html#a2c6d2ce4210d3bfbc3d659dd724d02f0">getValue</a>(p.<a class="code" href="classMiniSat_1_1Lit.html#a952944c0a85fca7f8db8b532a72b3fda">var</a>()); } <a name="l00701"></a>00701 <a name="l00702"></a>00702 <span class="comment">// get the assignment level of a variable/literal (which should have a value)</span> <a name="l00703"></a><a class="code" href="classMiniSat_1_1Solver.html#a68a7d96223af2e9b67d8b25d047284e4">00703</a> <span class="keywordtype">int</span> <a class="code" href="classMiniSat_1_1Solver.html#a68a7d96223af2e9b67d8b25d047284e4">getLevel</a>(<a class="code" href="namespaceMiniSat.html#a0d9722420b2afd308dceda22c1b05a5e">Var</a> var)<span class="keyword"> const </span>{ <span class="keywordflow">return</span> <a class="code" href="classMiniSat_1_1Solver.html#a34c9afcb69ae37cebbf43a61505009b3">d_level</a>[var]; }; <a name="l00704"></a><a class="code" href="classMiniSat_1_1Solver.html#a70b4f991bd7a679be32a89aa1d22eb8d">00704</a> <span class="keywordtype">int</span> <a class="code" href="classMiniSat_1_1Solver.html#a70b4f991bd7a679be32a89aa1d22eb8d">getLevel</a>(<a class="code" href="classMiniSat_1_1Lit.html">Lit</a> lit)<span class="keyword"> const </span>{ <span class="keywordflow">return</span> <a class="code" href="classMiniSat_1_1Solver.html#a70b4f991bd7a679be32a89aa1d22eb8d">getLevel</a>(lit.<a class="code" href="classMiniSat_1_1Lit.html#a952944c0a85fca7f8db8b532a72b3fda">var</a>()); }; <a name="l00705"></a>00705 <a name="l00706"></a>00706 <span class="comment">// set the assignment level of a variable/literal</span> <a name="l00707"></a><a class="code" href="classMiniSat_1_1Solver.html#adf6fbd3cddfa511acae41f180b187454">00707</a> <span class="keywordtype">void</span> <a class="code" href="classMiniSat_1_1Solver.html#adf6fbd3cddfa511acae41f180b187454">setLevel</a>(<a class="code" href="namespaceMiniSat.html#a0d9722420b2afd308dceda22c1b05a5e">Var</a> var, <span class="keywordtype">int</span> level) { <a class="code" href="classMiniSat_1_1Solver.html#a34c9afcb69ae37cebbf43a61505009b3">d_level</a>[var] = level; }; <a name="l00708"></a><a class="code" href="classMiniSat_1_1Solver.html#aae4dc01729a30c592f939d7d922f5774">00708</a> <span class="keywordtype">void</span> <a class="code" href="classMiniSat_1_1Solver.html#aae4dc01729a30c592f939d7d922f5774">setLevel</a>(<a class="code" href="classMiniSat_1_1Lit.html">Lit</a> lit, <span class="keywordtype">int</span> level) { <a class="code" href="classMiniSat_1_1Solver.html#aae4dc01729a30c592f939d7d922f5774">setLevel</a>(lit.<a class="code" href="classMiniSat_1_1Lit.html#a952944c0a85fca7f8db8b532a72b3fda">var</a>(), level); }; <a name="l00709"></a>00709 <a name="l00710"></a>00710 <span class="comment">// this clause is the reason for a propagation and thus can't be removed</span> <a name="l00711"></a>00711 <span class="comment">// precondition: the first literal of the reason clause must be the propagated literal</span> <a name="l00712"></a><a class="code" href="classMiniSat_1_1Solver.html#a344d9206f065425f276b408e86b7e1d3">00712</a> <span class="keywordtype">bool</span> <a class="code" href="classMiniSat_1_1Solver.html#a344d9206f065425f276b408e86b7e1d3">isReason</a>(<span class="keyword">const</span> <a class="code" href="classMiniSat_1_1Clause.html">Clause</a>* c)<span class="keyword"> const </span>{ <span class="keywordflow">return</span> c-><a class="code" href="classMiniSat_1_1Clause.html#adf5aa50a639b4b5bb71e5ea76d45b8e2">size</a>() > 0 && <a class="code" href="classMiniSat_1_1Solver.html#a4405fbaba3ed712f704d5c85a390b558">d_reason</a>[((*c)[0]).var()] == c; } <a name="l00713"></a>00713 <a name="l00714"></a>00714 <span class="comment">// returns the implication reason of a variable (its value must be defined)</span> <a name="l00715"></a><a class="code" href="classMiniSat_1_1Solver.html#a8660c6ceafa236f5533e432bb859aeba">00715</a> <a class="code" href="classMiniSat_1_1Clause.html">Clause</a>* <a class="code" href="classMiniSat_1_1Solver.html#a8660c6ceafa236f5533e432bb859aeba">getReason</a>(<a class="code" href="namespaceMiniSat.html#a0d9722420b2afd308dceda22c1b05a5e">Var</a> var)<span class="keyword"> const </span>{ <span class="keywordflow">return</span> <a class="code" href="classMiniSat_1_1Solver.html#a4405fbaba3ed712f704d5c85a390b558">d_reason</a>[var]; }; <a name="l00716"></a>00716 <a name="l00717"></a>00717 <span class="comment">// like getReason, but if resolveTheoryImplication is true,</span> <a name="l00718"></a>00718 <span class="comment">// then additionaly if literal is a theory implication resolveTheoryImplication() is called.</span> <a name="l00719"></a>00719 <a class="code" href="classMiniSat_1_1Clause.html">Clause</a>* <a class="code" href="classMiniSat_1_1Solver.html#a8660c6ceafa236f5533e432bb859aeba">getReason</a>(<a class="code" href="classMiniSat_1_1Lit.html">Lit</a> literal, <span class="keywordtype">bool</span> <a class="code" href="classMiniSat_1_1Solver.html#a22b59f22e9df28fcb892e5873d998c75">resolveTheoryImplication</a> = <span class="keyword">true</span>); <a name="l00720"></a>00720 <a name="l00721"></a>00721 <span class="comment">// the current clause set</span> <a name="l00722"></a><a class="code" href="classMiniSat_1_1Solver.html#a70a7ffd14675ce9d3f1d445a79505278">00722</a> <span class="keyword">const</span> std::vector<Clause*>& <a class="code" href="classMiniSat_1_1Solver.html#a70a7ffd14675ce9d3f1d445a79505278">getClauses</a>()<span class="keyword"> const </span>{ <span class="keywordflow">return</span> <a class="code" href="classMiniSat_1_1Solver.html#ae4d0195d229b334f9d9c2f3122e41bd1">d_clauses</a>; } <a name="l00723"></a>00723 <a name="l00724"></a>00724 <span class="comment">// the current lemma set</span> <a name="l00725"></a><a class="code" href="classMiniSat_1_1Solver.html#aadbf5bfce16879745ac1fc7e5226957c">00725</a> <span class="keyword">const</span> std::vector<Clause*>& <a class="code" href="classMiniSat_1_1Solver.html#aadbf5bfce16879745ac1fc7e5226957c">getLemmas</a>()<span class="keyword"> const </span>{ <span class="keywordflow">return</span> <a class="code" href="classMiniSat_1_1Solver.html#a0c9270be1c0980e631de98b3408a8031">d_learnts</a>; } <a name="l00726"></a>00726 <a name="l00727"></a>00727 <span class="comment">// the current variable assignments</span> <a name="l00728"></a><a class="code" href="classMiniSat_1_1Solver.html#a16a71aec47f38eed46547c52ca9b152b">00728</a> <span class="keyword">const</span> std::vector<Lit>& <a class="code" href="classMiniSat_1_1Solver.html#a16a71aec47f38eed46547c52ca9b152b">getTrail</a>()<span class="keyword"> const </span>{ <span class="keywordflow">return</span> <a class="code" href="classMiniSat_1_1Solver.html#af092e4552ff6a34e5fcb5f67de96c845">d_trail</a>; } <a name="l00729"></a>00729 <a name="l00730"></a>00730 <span class="comment">// the derivation, logged if != NULL</span> <a name="l00731"></a><a class="code" href="classMiniSat_1_1Solver.html#a82e89493435ed86eb83f6af47fc78379">00731</a> <a class="code" href="classMiniSat_1_1Derivation.html">Derivation</a>* <a class="code" href="classMiniSat_1_1Solver.html#a82e89493435ed86eb83f6af47fc78379">getDerivation</a>() { <span class="keywordflow">return</span> <a class="code" href="classMiniSat_1_1Solver.html#ad2d7fa92335dfd68f8598a5a41d17e93" title="proof logging">d_derivation</a>; } <a name="l00732"></a>00732 <span class="comment"></span> <a name="l00733"></a>00733 <span class="comment"> /// Statistics</span> <a name="l00734"></a>00734 <span class="comment"></span> <a name="l00735"></a>00735 <span class="comment">// derivation statistics</span> <a name="l00736"></a><a class="code" href="classMiniSat_1_1Solver.html#ac386ec8bbd27857254bae149db775412">00736</a> <span class="keyword">const</span> <a class="code" href="structMiniSat_1_1SolverStats.html">SolverStats</a>& <a class="code" href="classMiniSat_1_1Solver.html#ac386ec8bbd27857254bae149db775412" title="Statistics.">getStats</a>()<span class="keyword"> const </span>{ <span class="keywordflow">return</span> <a class="code" href="classMiniSat_1_1Solver.html#ac2c0d8b62a85616add0930b4947c8f96">d_stats</a>; } <a name="l00737"></a>00737 <a name="l00738"></a>00738 <span class="comment">// number of assigned variabels (context size)</span> <a name="l00739"></a><a class="code" href="classMiniSat_1_1Solver.html#af2bc4c7b90705664cf10982944640b3f">00739</a> <span class="keywordtype">int</span> <a class="code" href="classMiniSat_1_1Solver.html#af2bc4c7b90705664cf10982944640b3f">nAssigns</a>()<span class="keyword"> const </span>{ <span class="keywordflow">return</span> <a class="code" href="classMiniSat_1_1Solver.html#af092e4552ff6a34e5fcb5f67de96c845">d_trail</a>.size(); } <a name="l00740"></a>00740 <a name="l00741"></a>00741 <span class="comment">// number of stored clauses (does not include clauses removed by simplifyDB)</span> <a name="l00742"></a><a class="code" href="classMiniSat_1_1Solver.html#af57851d84d9e00837b1b09106bf5db27">00742</a> <span class="keywordtype">int</span> <a class="code" href="classMiniSat_1_1Solver.html#af57851d84d9e00837b1b09106bf5db27">nClauses</a>()<span class="keyword"> const </span>{ <span class="keywordflow">return</span> <a class="code" href="classMiniSat_1_1Solver.html#ae4d0195d229b334f9d9c2f3122e41bd1">d_clauses</a>.size(); } <a name="l00743"></a>00743 <a name="l00744"></a>00744 <span class="comment">// number of stored lemmas (forgotten lemmas are not counted)</span> <a name="l00745"></a><a class="code" href="classMiniSat_1_1Solver.html#a2beb4ee59904cb55b5b3e69886a0701c">00745</a> <span class="keywordtype">int</span> <a class="code" href="classMiniSat_1_1Solver.html#a2beb4ee59904cb55b5b3e69886a0701c">nLearnts</a>()<span class="keyword"> const </span>{ <span class="keywordflow">return</span> <a class="code" href="classMiniSat_1_1Solver.html#a0c9270be1c0980e631de98b3408a8031">d_learnts</a>.size(); } <a name="l00746"></a>00746 <a name="l00747"></a>00747 <span class="comment">// variable with the highest id + 1</span> <a name="l00748"></a>00748 <span class="comment">// not necessaribly the number of variables, if they are not enumerated without gap</span> <a name="l00749"></a><a class="code" href="classMiniSat_1_1Solver.html#a679fa13af0d75beca98981dc40f3f2a2">00749</a> <span class="keywordtype">int</span> <a class="code" href="classMiniSat_1_1Solver.html#a679fa13af0d75beca98981dc40f3f2a2">nVars</a>()<span class="keyword"> const </span>{ <span class="keywordflow">return</span> <a class="code" href="classMiniSat_1_1Solver.html#a8fd906b3d57929f47f9a6eb6740e35e9">d_assigns</a>.size(); } <a name="l00750"></a>00750 <a name="l00751"></a>00751 <span class="comment"></span> <a name="l00752"></a>00752 <span class="comment"> /// String representation:</span> <a name="l00753"></a>00753 <span class="comment"></span> <a name="l00754"></a>00754 <span class="comment">// literal id, sign, current assignment as string</span> <a name="l00755"></a>00755 std::string <a class="code" href="classMiniSat_1_1Solver.html#ac4949ee43735e3de2869ff606ccc197c" title="String representation:">toString</a>(<a class="code" href="classMiniSat_1_1Lit.html">Lit</a> literal, <span class="keywordtype">bool</span> showAssignment) <span class="keyword">const</span>; <a name="l00756"></a>00756 <a name="l00757"></a>00757 <span class="comment">// clause as string, showAssignment true -> show current assignment of each literal</span> <a name="l00758"></a>00758 std::string <a class="code" href="classMiniSat_1_1Solver.html#ac4949ee43735e3de2869ff606ccc197c" title="String representation:">toString</a>(<span class="keyword">const</span> std::vector<Lit>& clause, <span class="keywordtype">bool</span> showAssignment) <span class="keyword">const</span>; <a name="l00759"></a>00759 <a name="l00760"></a>00760 <span class="comment">// clause as string, showAssignment true -> show current assignment of each literal</span> <a name="l00761"></a>00761 std::string <a class="code" href="classMiniSat_1_1Solver.html#ac4949ee43735e3de2869ff606ccc197c" title="String representation:">toString</a>(<span class="keyword">const</span> <a class="code" href="classMiniSat_1_1Clause.html">Clause</a>& clause, <span class="keywordtype">bool</span> showAssignment) <span class="keyword">const</span>; <a name="l00762"></a>00762 <a name="l00763"></a>00763 <span class="comment">// prints lemmas, clauses, assignment to cout</span> <a name="l00764"></a>00764 <span class="keywordtype">void</span> <a class="code" href="classMiniSat_1_1Solver.html#af8254dba6facc2d13c85202d9d09b3f9">printState</a>() <span class="keyword">const</span>; <a name="l00765"></a>00765 <a name="l00766"></a>00766 <span class="comment">// output the clause set and context in DIMACS format</span> <a name="l00767"></a>00767 <span class="keywordtype">void</span> <a class="code" href="classMiniSat_1_1Solver.html#ac3d7b1cc4327878d22b91d105ea32409">printDIMACS</a>() <span class="keyword">const</span>; <a name="l00768"></a>00768 <a name="l00769"></a>00769 std::vector<SAT::Lit> <a class="code" href="classMiniSat_1_1Solver.html#aac50fbefa27ff761747fe0873722f927">curAssigns</a>() ; <a name="l00770"></a>00770 std::vector<std::vector<SAT::Lit> > <a class="code" href="classMiniSat_1_1Solver.html#afb1410338334a3220d95ec28e5a68f71">curClauses</a>(); <a name="l00771"></a>00771 }; <a name="l00772"></a>00772 <a name="l00773"></a>00773 } <a name="l00774"></a>00774 <a name="l00775"></a>00775 <a name="l00776"></a>00776 <a name="l00777"></a>00777 <a name="l00778"></a>00778 <span class="comment">//=================================================================================================</span> <a name="l00779"></a>00779 <span class="preprocessor">#endif</span> </pre></div></div> </div> <hr class="footer"/><address class="footer"><small>Generated on Wed Sep 7 2011 for CVC3 by  <a href="http://www.doxygen.org/index.html"> <img class="footer" src="doxygen.png" alt="doxygen"/></a> 1.7.4 </small></address> </body> </html>