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

# /Users/fpy/titan-1-5-MBARI/Mers/Generators/BFIG/BFIG.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 "BFIG.h"
    00015
    00016 #ifdef _MSC_VER
    00017 #pragma warning( disable : 4786 )
    00018 #endif
    00019
    00020 #include <cstdlib>
    00021 #include <cassert>
    00022 #include "BFIGImplicant.h"
    00023 #include "BFIGImplicantNoMPI.h"
    00024 #include "BFIGConstraint.h"
    00025 #include "BFIGVariable.h"
    00026 #include "BFIGAssignment.h"
    00027 #include "BFIGObjectiveFunction.h"
    00028
    00029 using namespace Mers::Generators::BFIG;
    00030 using Mers::Generators::BFIG::BFIG;
    00031 using Mers::Generators::BFIG::BFIGVariable;
    00032 using Mers::Generators::BFIG::BFIGConstraint;
    00033 using Mers::Generators::BFIG::BFIGImplicant;
    00034 using log4cplus::LogLevel;
    00035
    00036 using Mers::Utils::Lang::String;
    00037
    00038 using std::vector;
    00039 using std::endl;
    00040
    00041
    00043
    00044 #ifdef _DEBUG
    00045 const unsigned int bfigInitialDebugState = 10;
    00046 #else
    00047 const unsigned int bfigInitialDebugState = 10;
    00048 #endif
    00049
    00051
    00052 Logger BFIG::mLogger(Logger::getInstance("Mers.Generators.BFIG.BFIG"));
    00053
    00055
    00056 BFIG::BFIG(std::vector<BFIGVariable *> const & variableSet, double cutoffCost,
    00057                 BFIGObjectiveFunction const * of)
    00058 : mName("Best-First Implicant Generator"),
    00059         mVariables(variableSet), mObjectiveFunction(of), mConflicts(),
    00060         mImplicantQueue(false, cutoffCost, true), mCandidate(NULL),
    00061         mNodesExpanded(0), mLargestQueue(1), mLargestQueueSinceReset(1),
    00062         mDebug(bfigInitialDebugState), mNumSolutions(0), mNumCandidatesSinceReset(0)
    00063 {
    00064         setDebug(bfigInitialDebugState);
    00065 }
    00066
    00068
    00069 BFIG::BFIG(vector<BFIGVariable *> const & variableSet, double cutoffCost)
    00070 : mName("Best-First Implicant Generator"),
    00071         mVariables(variableSet), mObjectiveFunction(NULL), mConflicts(),
    00072         mImplicantQueue(false, cutoffCost, true), mCandidate(NULL),
    00073         mNodesExpanded(0), mLargestQueue(1), mLargestQueueSinceReset(1),
    00074         mDebug(bfigInitialDebugState), mNumSolutions(0), mNumCandidatesSinceReset(0)
    00075 {
    00076         setDebug(bfigInitialDebugState);
    00077 }
    00078
    00080
    00081 BFIG::BFIG(vector<BFIGVariable *> const & variableSet)
    00082 : mName("Best-First Implicant Generator"),
    00083         mVariables(variableSet), mObjectiveFunction(NULL), mConflicts(),
    00084         mImplicantQueue(false, true), mCandidate(NULL),
    00085         mNodesExpanded(0), mLargestQueue(1), mLargestQueueSinceReset(1),
    00086         mDebug(bfigInitialDebugState), mNumSolutions(0), mNumCandidatesSinceReset(0)
    00087 {
    00088         setDebug(bfigInitialDebugState);
    00089 }
    00090
    00092
    00093 BFIG::~BFIG()
    00094 {
    00095         // should be taken care of by caller, but isn't:
    00096         vector<BFIGConstraint const *>::const_iterator cIter;
    00097         for (cIter = mConflicts.begin(); cIter != mConflicts.end(); cIter++)
    00098         {
    00099                 if (*cIter)
    00100                         delete (*cIter);
    00101         }
    00102
    00103         mImplicantQueue.makeEmpty();
    00104
    00105         if(mCandidate != NULL)
    00106                 delete mCandidate;
    00107
    00108 #ifdef _DEBUG
    00109   //printStatistics(mLogger);
    00110 #endif
    00111 }
    00112
    00114
    00115 String const
    00116 BFIG::getName() const
    00117 {
    00118         return mName;
    00119 }
    00120
    00122
    00123 Mers::Generators::BFIG::BFIGVariable *
    00124 BFIG::getVariableByName(String variableName)  //const
    00125 {
    00126         vector<BFIGVariable *>::iterator variableIter;
    00127
    00128         for (variableIter = mVariables.begin(); variableIter != mVariables.end();
    00129                  variableIter++)
    00130         {
    00131                 if (variableName == (*variableIter)->getNameString())
    00132                         return (*variableIter);
    00133         }
    00134
    00135         return NULL;
    00136 }
    00137
    00139
    00140 Mers::Generators::BFIG::BFIGVariable *
    00141 BFIG::getVariableByName(unsigned int variableName)  //const
    00142 {
    00143         vector<BFIGVariable *>::iterator variableIter;
    00144
    00145         for (variableIter = mVariables.begin(); variableIter != mVariables.end();
    00146                  variableIter++)
    00147         {
    00148                 if (variableName == (*variableIter)->getName())
    00149                         return (*variableIter);
    00150         }
    00151
    00152         return NULL;
    00153 }
    00154
    00156
    00157 vector<Mers::Generators::BFIG::BFIGVariable *>
    00158 BFIG::getVariables() const
    00159 {
    00160         return mVariables;
    00161 }
    00162
    00164
    00165 void
    00166 BFIG::addConflict(BFIGConstraint const * newConflict)
    00167 {
    00168         mConflicts.push_back(newConflict);
    00169
    00170         LOG4CPLUS_DEBUG(mLogger, "Added conflict: " << *newConflict);
    00171
    00172         if (mImplicantQueue.isEmpty() && mCandidate == NULL)
    00173         {
    00174                 LOG4CPLUS_ERROR_STR(mLogger, "Adding conflict to empty BFIG tree!");
    00175
    00176                 BFIGImplicant * newImp = createNewImplicant(mConflicts);
    00177                 mImplicantQueue.insert(newImp);
    00178         } else {
    00179                 unsigned int x;
    00180                 for(x = 0; x < mImplicantQueue.getLength(); x++){
    00181                         mImplicantQueue[x]->addUnentailedConflict(newConflict);
    00182                 }
    00183
    00184                 // Don't forget to add it to our current candidate.
    00185                 if(mCandidate != NULL) {
    00186                         mCandidate->addUnentailedConflict(newConflict);
    00187                 }
    00188         }
    00189 }
    00190
    00192
    00193 void
    00194 BFIG::addConflicts(vector<BFIGConstraint const *> const & newConflicts)
    00195 {
    00196         LOG4CPLUS_DEBUG_STR(mLogger, "Added conflicts:");
    00197
    00198         vector<BFIGConstraint const *>::const_iterator cIter;
    00199         for (cIter = newConflicts.begin(); cIter != newConflicts.end(); cIter++)
    00200         {
    00201                 assert(*cIter);
    00202                 mConflicts.push_back(*cIter);
    00203
    00204                 LOG4CPLUS_DEBUG(mLogger, **cIter);
    00205         }
    00206
    00207         if (mImplicantQueue.isEmpty() && mCandidate == NULL)
    00208         {
    00209                 LOG4CPLUS_ERROR_STR(mLogger, "Adding conflicts to empty BFIG tree!");
    00210
    00211                 BFIGImplicant * newImp = createNewImplicant(mConflicts);
    00212                 mImplicantQueue.insert(newImp);
    00213         } else {
    00214                 unsigned int x;
    00215                 for(x = 0; x < mImplicantQueue.getLength(); x++){
    00216                         mImplicantQueue[x]->addUnentailedConflicts(newConflicts);
    00217                 }
    00218
    00219                 // Don't forget to add it to our current candidate.
    00220                 if(mCandidate != NULL) {
    00221                         mCandidate->addUnentailedConflicts(newConflicts);
    00222                 }
    00223         }
    00224 }
    00225
    00227
    00228 Mers::Generators::BFIG::BFIGImplicant const *
    00229 BFIG::getBestImplicant(long maximumVisitedStateCount, long maxQueueSize)
    00230 {
    00231         LOG4CPLUS_TRACE(mLogger, "BFIG::getBestImplicant("
    00232                 << maximumVisitedStateCount << ", " << maxQueueSize
    00233                 << ") Looking for next best implicant.  Conflicts(" << mConflicts.size() << ")");
    00234
    00235         if(mCandidate != NULL) {
    00236                 insertExtensions(mCandidate);
    00237                 delete mCandidate;
    00238                 mCandidate = NULL;
    00239         }
    00240
    00241         if (mImplicantQueue.isEmpty())
    00242         {
    00243                 return NULL;
    00244         }
    00245
    00246         searchForImplicant(maximumVisitedStateCount, maxQueueSize);
    00247
    00248         if (mCandidate == NULL)
    00249         {
    00250                 // exhausted search - failure to find a candidate
    00251                 return NULL;
    00252         }
    00253
    00254         if (!mCandidate->entailsAllConflicts())
    00255         {
    00256                 LOG4CPLUS_DEBUG_STR(mLogger, "Solution found did not satisfy the "
    00257                         "conflicts.");
    00258
    00259                 delete mCandidate;
    00260                 mCandidate = NULL;
    00261
    00262                 return NULL;
    00263         }
    00264         mNumCandidatesSinceReset++;
    00265         return mCandidate;
    00266 }
    00267
    00269
    00270 void
    00271 BFIG::markBestFeasible()
    00272 {
    00273         if(mCandidate == NULL)
    00274                 return;
    00275
    00276         mNumSolutions++;
    00277         insertSiblings(mCandidate);
    00278         delete mCandidate;
    00279         mCandidate = NULL;
    00280 }
    00281
    00283
    00284 void BFIG::restart()
    00285 {
    00286         LOG4CPLUS_TRACE_STR(mLogger, "Restarting BFIG");
    00287         BFIGImplicant * initImp = createNewImplicant(mConflicts);
    00288         mImplicantQueue.makeEmpty();
    00289         mImplicantQueue.insert(initImp);
    00290         if(mCandidate != NULL) {
    00291                 delete mCandidate;
    00292                 mCandidate = NULL;
    00293         }
    00294 }
    00295
    00297
    00298 void BFIG::reset()
    00299 {
    00300         LOG4CPLUS_TRACE_STR(mLogger, "Resetting BFIG");
    00301         vector<BFIGConstraint const *>::const_iterator cIter;
    00302         for (cIter = mConflicts.begin(); cIter != mConflicts.end(); cIter++)
    00303         {
    00304                 if (*cIter)
    00305                         delete (*cIter);
    00306         }
    00307         mConflicts.resize(0);
    00308         mLargestQueueSinceReset = 1;
    00309         mNumCandidatesSinceReset = 0;
    00310
    00311         restart();
    00312 }
    00313
    00315
    00316 unsigned int BFIG::getNumberOfConflicts()
    00317 {
    00318         return mConflicts.size();
    00319 }
    00320
    00322
    00323
    00324 BFIGImplicant *
    00325 BFIG::createNewImplicant(std::vector<BFIGConstraint const *> &con)
    00326 {
    00327         if(mObjectiveFunction != NULL)
    00328         {
    00329                 if(!mObjectiveFunction->isMPI())
    00330                 {       // Create a non-MPI BFIG Implicant
    00331                         return new BFIGImplicantNoMPI(con, mObjectiveFunction);
    00332                 }
    00333         }
    00334         //std::cout << "Creating Implicant" << std::endl;
    00335         // The objective function is MPI, use regular BFIGImplicant
    00336         return new BFIGImplicant(con, mObjectiveFunction);
    00337 }
    00338
    00339 void
    00340 BFIG::enqueueImplicants(vector<BFIGImplicant *> const & newImplicants)
    00341 {
    00342         vector<BFIGImplicant *>::const_iterator implicantIter;
    00343         for (implicantIter = newImplicants.begin();
    00344              implicantIter != newImplicants.end();
    00345              implicantIter++)
    00346         {
    00347                 assert(*implicantIter);
    00348                 enqueueImplicant(*implicantIter);
    00349         }
    00350
    00351         if (mImplicantQueue.getLength() > mLargestQueue)
    00352                 mLargestQueue = mImplicantQueue.getLength();
    00353
    00354         if (mImplicantQueue.getLength() > mLargestQueueSinceReset)
    00355                 mLargestQueueSinceReset = mImplicantQueue.getLength();
    00356
    00357         if (mDebug > 0)
    00358         {
    00359                 LOG4CPLUS_DEBUG(mLogger, "---- Search State: ");
    00360                 printQueue(mLogger);
    00361                 printStatistics(mLogger);
    00362                 LOG4CPLUS_DEBUG(mLogger, "----");
    00363         }
    00364 }
    00365
    00367
    00368 void
    00369 BFIG::enqueueImplicant(BFIGImplicant * imp)
    00370 {
    00371         assert(imp);
    00372         mImplicantQueue.insert(imp);
    00373
    00374         if (mImplicantQueue.getLength() > mLargestQueue)
    00375                 mLargestQueue = mImplicantQueue.getLength();
    00376
    00377         if (mImplicantQueue.getLength() > mLargestQueueSinceReset)
    00378                 mLargestQueueSinceReset = mImplicantQueue.getLength();
    00379 }
    00380
    00382
    00383 unsigned int
    00384 BFIG::getLargestQueue() const
    00385 {
    00386         return mLargestQueue;
    00387 }
    00388
    00390
    00391 unsigned int
    00392 BFIG::getLargestQueueSinceReset() const
    00393 {
    00394         return mLargestQueueSinceReset;
    00395 }
    00396
    00398
    00399 unsigned int
    00400 BFIG::getNodesExpanded() const
    00401 {
    00402         return mNodesExpanded;
    00403 }
    00404
    00406
    00407 unsigned int
    00408 BFIG::getNumberCandidatesSinceReset() const
    00409 {
    00410         return mNumCandidatesSinceReset;
    00411 }
    00412
    00414
    00415 void
    00416 BFIG::setDebug(unsigned int debugState)
    00417 {
    00418         mDebug = debugState;
    00419         LOG4CPLUS_DEBUG(mLogger, "Debug Level set to " << mDebug);
    00420 }
    00421
    00423
    00424 void
    00425 BFIG::printStatistics(bool verbose) const
    00426 {
    00427         printStatistics(mLogger, verbose);
    00428 }
    00429
    00431
    00432 void
    00433 BFIG::printStatistics(Logger logger, bool verbose,
    00434         LogLevel logLevel) const
    00435 {
    00436 #if !defined(LOG4CPLUS_DISABLE_FATAL)
    00437         if(mLogger.isEnabledFor(logLevel)) {
    00438                 log4cplus::tostringstream log4cplus_buf;
    00439
    00440                 if(verbose) {
    00441                         size_t maxQueue = getLargestQueue() *
    00442                                 (sizeof(BFIGImplicant) + sizeof(BFIGImplicant*));
    00443
    00444                         log4cplus_buf << "Nodes expanded: " << getNodesExpanded() << endl;
    00445                         log4cplus_buf << "Max queue size: " << getLargestQueue() << " (" <<
    00446                                 maxQueue << " bytes)" << endl;
    00447                         log4cplus_buf << "Conflicts generated: " << mConflicts.size() << endl;
    00448                         log4cplus_buf << "Feasible implicants generated: " << mNumSolutions;
    00449                 } else {
    00450                         log4cplus_buf << "Expanded Nodes(" << getNodesExpanded() <<
    00451                                 "); Max Queue(" << getLargestQueue() << "); Conflicts(" <<
    00452                                 mConflicts.size() << "); Candidates(" << mNumSolutions << ");";
    00453                 }
    00454
    00455                 logger.forcedLog(logLevel, log4cplus_buf.str(), __FILE__, __LINE__);
    00456         }
    00457 #else
    00458         (void)verbose;
    00459         (void)logger;
    00460         (void)logLevel;
    00461 #endif
    00462 }
    00463
    00465
    00466 void
    00467 BFIG::printQueue(bool verbose) const
    00468 {
    00469         printQueue(mLogger, verbose);
    00470 }
    00471
    00473
    00474 void
    00475 BFIG::printQueue(Logger logger, bool verbose, LogLevel logLevel) const
    00476 {
    00477 #if !defined(LOG4CPLUS_DISABLE_FATAL)
    00478         if(mLogger.isEnabledFor(logLevel)) {
    00479                 unsigned int printLimit = 10;
    00480                 log4cplus::tostringstream log4cplus_buf;
    00481
    00482                 log4cplus_buf << "Implicant Queue:" << endl;
    00483
    00484                 for (unsigned int x = 0;
    00485                                  x < mImplicantQueue.getLength() && (verbose || x < printLimit); x++)
    00486                 {
    00487                         if(x != 0)
    00488                                 log4cplus_buf << endl;
    00489                         log4cplus_buf << "    " << (*(mImplicantQueue[x]));
    00490                 }
    00491                 if (!verbose && mImplicantQueue.getLength() > printLimit)
    00492                 {
    00493                         log4cplus_buf << endl << "    " << "..." << '('
    00494                                 << mImplicantQueue.getLength() << ')';
    00495                 }
    00496
    00497                 logger.forcedLog(logLevel, log4cplus_buf.str(), __FILE__, __LINE__);
    00498         }
    00499 #else
    00500         (void)logger;
    00501         (void)verbose;
    00502         (void)logLevel;
    00503 #endif
    00504 }
    00505
    00507
    00508 void BFIG::insertSiblings(BFIGImplicant * sibling)
    00509 {
    00510         BFIGImplicant * newSibling;
    00511
    00512         newSibling = sibling->generateSibling();
    00513
    00515
    00516         if (newSibling != NULL) {
    00517                 LOG4CPLUS_DEBUG(mLogger, *sibling << " has the sibling:" << endl <<
    00518                         "    " << *newSibling);
    00519
    00520                 enqueueImplicant(newSibling);
    00521         } else {
    00522                 if (mDebug > 0) {
    00523                         LOG4CPLUS_DEBUG(mLogger, *sibling << " has no siblings.");
    00524                 }
    00525         }
    00526 }
    00527
    00529
    00530 void BFIG::insertChildren(BFIGImplicant * parent)
    00531 {
    00532         vector<BFIGImplicant *> children;
    00533
    00534         // give variables so we can extend even without conflicts.
    00535         children = parent->generateChildren(&mVariables);
    00536
    00538
    00539         if (!children.empty()) {
    00540                 if(mDebug > 0) {
    00541                         LOG4CPLUS_DEBUG(mLogger, *parent << " has the children:");
    00542                         unsigned int x;
    00543
    00544                         for(x = 0; x < children.size(); x++) {
    00545                                 LOG4CPLUS_DEBUG(mLogger, *children[x]);
    00546                         }
    00547                 }
    00548
    00549                 enqueueImplicants(children);
    00550         } else {
    00551                 if (mDebug > 0) {
    00552                         LOG4CPLUS_DEBUG(mLogger, *parent << " has no children.");
    00553                 }
    00554         }
    00555 }
    00556
    00558
    00559 void BFIG::insertExtensions(BFIGImplicant * node)
    00560 {
    00561         insertSiblings(node);
    00562         insertChildren(node);
    00563 }
    00564
    00566