- Main Page
- Namespaces
- Classes
- Files
- Related Pages

# /Users/fpy/titan-1-5-MBARI/Mers/Generators/BFIG/CDBFIG/CDBFIG.cpp

    00001
    00002 //
    00003 // Copyright (c) 2004           Model-based Embedded and Robotic Systems Group
    00004 // All Rights Reserved          Massachusetts Institute of Technology
    00005 //
    00006 // This software is provided as is. Model-based Embedded and Robotic Systems
    00007 // (MERS) group does not assume any responsibility.
    00008 //
    00009 // Organization:        Model-based Embedded and Robotic Systems Group
    00010 //                                      Massachusetts Institute of Technology
    00011 //
    00013
    00014 #include "CDBFIG.h"
    00015
    00016 #ifdef _MSC_VER
    00017 #pragma warning( disable : 4786 )
    00018 #endif
    00019
    00020 #include <cstdlib>
    00021 #include <cassert>
    00022
    00023 #include <Mers/Generators/BFIG/BFIGImplicant.h>
    00024 #include <Mers/Generators/BFIG/BFIGConstraint.h>
    00025 #include <Mers/Generators/BFIG/BFIGVariable.h>
    00026 #include <Mers/Generators/BFIG/BFIGAssignment.h>
    00027 #include <Mers/Generators/BFIG/BFIGObjectiveFunction.h>
    00028
    00029 using Mers::Generators::BFIG::CDBFIG::CDBFIG;
    00030 using Mers::Generators::BFIG::BFIGVariable;
    00031 using Mers::Generators::BFIG::BFIGObjectiveFunction;
    00032 using log4cplus::LogLevel;
    00033 using namespace std;
    00034
    00036
    00037 Logger CDBFIG::mLogger(Logger::getInstance("Mers.Generators.BFIG.CDBFIG.CDBFIG"));
    00038
    00040
    00041 CDBFIG::CDBFIG(vector<BFIGVariable *> const & variableSet, double cutoffCost,
    00042                            BFIGObjectiveFunction const * of)
    00043 : BFIG(variableSet, cutoffCost, of)
    00044 {
    00045         mName = "Conflict-Directed Best-First Implicant Generator";
    00046         // start off the search tree with an empty node.
    00047         BFIGImplicant * initImp = createNewImplicant(mConflicts);
    00048         mImplicantQueue.insert(initImp);
    00049 }
    00051
    00052 CDBFIG::CDBFIG(vector<BFIGVariable *> const & variableSet, double cutoffCost)
    00053 : BFIG(variableSet, cutoffCost)
    00054 {
    00055         mName = "Conflict-Directed Best-First Implicant Generator";
    00056         // start off the search tree with an empty node.
    00057         BFIGImplicant * initImp = createNewImplicant(mConflicts);
    00058         mImplicantQueue.insert(initImp);
    00059 }
    00060
    00062
    00063 CDBFIG::CDBFIG(vector<BFIGVariable *> const & variableSet)
    00064 : BFIG(variableSet)
    00065 {
    00066         mName = "Conflict-Directed Best-First Implicant Generator";
    00067         // start off the search tree with an empty node.
    00068         BFIGImplicant * initImp = createNewImplicant(mConflicts);
    00069         mImplicantQueue.insert(initImp);
    00070 }
    00071
    00073
    00074 CDBFIG::~CDBFIG()
    00075 {
    00076 }
    00077
    00079
    00080 void
    00081 CDBFIG::searchForImplicant(long maxExpansionCount, long maxQueueSize)
    00082 {
    00083         LOG4CPLUS_TRACE_STR(mLogger, "CDBFIG::searchForImplicant: searching...");
    00084
    00085         if (mImplicantQueue.isEmpty())
    00086         {
    00087                 LOG4CPLUS_ERROR_STR(mLogger, "CDBFIG::searchForImplicant: Starting "
    00088                         "search in empty CDBFIG tree!");
    00089
    00090                 BFIGImplicant * newImp = createNewImplicant(mConflicts);
    00091                 mImplicantQueue.insert(newImp);
    00092         }
    00093
    00094         long i;
    00095         for (i = 0;
    00096                 (maxExpansionCount <= 0 || i < maxExpansionCount) &&
    00097                 (mImplicantQueue.getLength() > 0) &&
    00098                 (maxQueueSize <= 0 || (long)(mImplicantQueue.getLength()) < maxQueueSize);
    00099                 i++)
    00100         {
    00101                 if (searchLoop())  // found a solution?
    00102                         break;
    00103         }
    00104
    00105         if(mDebug > 0) {
    00106                 LOG4CPLUS_DEBUG(mLogger, "(Nodes expanded in search: " << i << ')');
    00107
    00108                 if ((maxExpansionCount > 0 && i >= maxExpansionCount)) {
    00109                         LOG4CPLUS_WARN_STR(mLogger, "Reached maximum expansion count.");
    00110                 }
    00111         }
    00112 }
    00113
    00115
    00116 bool
    00117 CDBFIG::searchLoop()
    00118 {
    00119         if (mImplicantQueue.isEmpty())
    00120                 return false;
    00121
    00122         LOG4CPLUS_DEBUG(mLogger, "---- Pre-get Search State: ");
    00123         printQueue(mLogger);
    00124         LOG4CPLUS_DEBUG(mLogger, "----");
    00125
    00126         if(FAILED(mImplicantQueue.getFirst(mCandidate))){
    00127                 LOG4CPLUS_ERROR_STR(mLogger, "CDBFIG::searchLoop: Failed to examine the "
    00128                         "next implicant");
    00129                 mCandidate = NULL;
    00130                 return false;
    00131         }
    00132
    00133         //LOG4CPLUS_DEBUG(mLogger, "---- Post-get Search State: ");
    00134         //printQueue(mLogger);
    00135         //LOG4CPLUS_DEBUG(mLogger, "----");
    00136
    00137         if(mDebug > 2) {
    00138                 LOG4CPLUS_DEBUG(mLogger, "Best Node: " << *mCandidate
    00139                         << ", Queue Size: " << mImplicantQueue.getLength());
    00140         }
    00141
    00142         // only return if our implicant has a full set of variables (we do
    00143         // not return partial candidates as we do not enumerate all partial
    00144         // candidates.)
    00145         if (mCandidate->entailsAllConflicts() &&
    00146                         mCandidate->getLength() == mVariables.size())
    00147         {
    00148                 LOG4CPLUS_DEBUG(mLogger, "Accepting Candidate: " << *mCandidate);
    00149                 return true;
    00150         }
    00151
    00152         // will be expanded... so siblings are ok.
    00153         if (mDebug > 0){
    00154                 LOG4CPLUS_DEBUG_STR(mLogger, "Expanding node...");
    00155         }
    00156
    00157         mNodesExpanded++;
    00158         insertExtensions(mCandidate);
    00159
    00160         delete mCandidate;
    00161         mCandidate = NULL;
    00162         return false;
    00163 }
    00164
    00166
    00167 void
    00168 CDBFIG::printStatistics(bool verbose) const
    00169 {
    00170         printStatistics(mLogger, verbose);
    00171 }
    00172
    00174
    00175 void
    00176 CDBFIG::printStatistics(Logger logger, bool verbose,
    00177         LogLevel logLevel) const
    00178 {
    00179 #if !defined(LOG4CPLUS_DISABLE_FATAL)
    00180         if(mLogger.isEnabledFor(logLevel)) {
    00181                 log4cplus::tostringstream log4cplus_buf;
    00182
    00183                 if(verbose) {
    00184                         size_t maxQueue = getLargestQueue() *
    00185                                 (sizeof(BFIGImplicant) + sizeof(BFIGImplicant*));
    00186
    00187                         log4cplus_buf << "Nodes expanded: " << getNodesExpanded() << endl;
    00188                         log4cplus_buf << "Max queue size: " << getLargestQueue() << " (" <<
    00189                                 maxQueue << " bytes)" << endl;
    00190                         log4cplus_buf << "Conflicts generated: " << mConflicts.size() << endl;
    00191                         log4cplus_buf << "Feasible implicants generated: " << mNumSolutions;
    00192                 } else {
    00193                         log4cplus_buf << "Expanded Nodes(" << getNodesExpanded() <<
    00194                                 "); Max Queue(" << getLargestQueue() << "); Conflicts(" <<
    00195                                 mConflicts.size() << "); Candidates(" << mNumSolutions << ");";
    00196                 }
    00197
    00198                 logger.forcedLog(logLevel, log4cplus_buf.str(), __FILE__, __LINE__);
    00199         }
    00200 #else
    00201         (void)verbose;
    00202         (void)logger;
    00203         (void)logLevel;
    00204 #endif
    00205 }
    00206
    00208
    00209 void
    00210 CDBFIG::printQueue(bool verbose) const
    00211 {
    00212         printQueue(mLogger, verbose);
    00213 }
    00214
    00216
    00217 void
    00218 CDBFIG::printQueue(Logger logger, bool verbose, LogLevel logLevel) const
    00219 {
    00220 #if !defined(LOG4CPLUS_DISABLE_FATAL)
    00221         if(mLogger.isEnabledFor(logLevel)) {
    00222                 unsigned int printLimit = 10;
    00223                 log4cplus::tostringstream log4cplus_buf;
    00224
    00225                 log4cplus_buf << "Implicant Queue:" << endl;
    00226
    00227                 for (unsigned int x = 0;
    00228                                  x < mImplicantQueue.getLength() && (verbose || x < printLimit); x++)
    00229                 {
    00230                         if(x != 0)
    00231                                 log4cplus_buf << endl;
    00232                         log4cplus_buf << "    " << (*(mImplicantQueue[x]));
    00233                 }
    00234                 if (!verbose && mImplicantQueue.getLength() > printLimit)
    00235                 {
    00236                         log4cplus_buf << endl << "    " << "..." << '('
    00237                                 << mImplicantQueue.getLength() << ')';
    00238                 }
    00239
    00240                 logger.forcedLog(logLevel, log4cplus_buf.str(), __FILE__, __LINE__);
    00241         }
    00242 #else
    00243         (void)logger;
    00244         (void)verbose;
    00245         (void)logLevel;
    00246 #endif
    00247 }
    00248
    00250