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

# /Users/fpy/titan-1-5-MBARI/Mers/Generators/BFIG/BFIGImplicant.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 "BFIGImplicant.h"
    00015
    00016 #ifdef _MSC_VER
    00017 #pragma warning( disable : 4786 )
    00018 #endif
    00019
    00020 #include <cassert>
    00021 #include "BFIGAssignment.h"
    00022 #include "BFIGVariable.h"
    00023 #include "BFIGConstraint.h"
    00024 #include "BFIGObjectiveFunction.h"
    00025 #include "ListManipulator.h"
    00026
    00027 using namespace std;
    00028 using Mers::Generators::BFIG::BFIGImplicant;
    00029 using Mers::Generators::BFIG::BFIGVariable;
    00030 using Mers::Generators::BFIG::BFIGAssignment;
    00031 using Mers::Generators::BFIG::BFIGConstraint;
    00032 using Mers::Generators::BFIG::ListManipulator;
    00033 using Mers::Generators::BFIG::BFIGObjectiveFunction;
    00034
    00035
    00037
    00038 typedef bool (*assignment_comp_func)(BFIGAssignment const *, BFIGAssignment const *);
    00039 typedef bool (*constraint_comp_func)(BFIGConstraint const *, BFIGConstraint const *);
    00040
    00042
    00043 static bool
    00044 assignment_less(BFIGAssignment const * a1, BFIGAssignment const * a2)
    00045 {
    00046         return ( (*a1) < (*a2) );
    00047 }
    00048
    00050
    00051 #ifdef IMPLICANT_EXTEND_ALL
    00052 static bool
    00053 assignment_cost_less(BFIGAssignment const * a1, BFIGAssignment const * a2)
    00054 {
    00055         return ( a1->getCost() < a2->getCost() );
    00056 }
    00057 #endif
    00058
    00060
    00061 static bool
    00062 constraint_shorter_fallback(BFIGConstraint const * c1, BFIGConstraint const * c2)
    00063 {
    00064         return ( (c1->primeImplicantSize() + (c1->getSize()<<1)) <
    00065                  (c2->primeImplicantSize() + (c2->getSize()<<1)) );
    00066
    00067 }
    00068
    00070
    00071 static constraint_comp_func constraint_order = constraint_shorter_fallback;
    00072
    00074
    00075 static void
    00076 printAssignmentList(vector<BFIGAssignment const *> const & as)
    00077 {
    00078         (void)printAssignmentList;
    00079         cout << "(";
    00080         vector<BFIGAssignment const *>::const_iterator aIter;
    00081         bool start = true;
    00082         for (aIter = as.begin(); aIter != as.end(); aIter++)
    00083         {
    00084                 if (start)
    00085                         start = false;
    00086                 else
    00087                         cout << ", ";
    00088                 if (*aIter)
    00089                         cout << *(*aIter);
    00090                 else
    00091                         cout << "NULL";
    00092         }
    00093         cout << ")";
    00094 }
    00095
    00097
    00098 bool BFIGImplicant::terse = false;
    00099 Logger BFIGImplicant::mLogger(
    00100         Logger::getInstance("Mers.Generators.BFIG.BFIGImplicant"));
    00101
    00103 //      CONSTRUCTOR
    00105
    00106 BFIGImplicant::BFIGImplicant(vector<BFIGAssignment const *> const & assignments_pList)
    00107 : assignments(assignments_pList), objectiveFunction(NULL),
    00108   #ifdef IMPLICANT_ENABLE_UNSORTED
    00109   assignmentsUnsorted(assignments_pList),
    00110   #endif
    00111   unentailedConflicts(), essentialConflict(false), markedFeasible(false),
    00112   siblingAssignments(), siblingParent(NULL)
    00113 {
    00114         // sort the assignments for comparison
    00115         {
    00116                 ListManipulator<BFIGAssignment const *> lm;
    00117                 lm.sort(assignments, assignment_less);
    00118         }
    00119         //cout << endl << "  Imp Assignments:  "; printAssignmentList(assignments); cout << endl;
    00120         bestCost = 0.0;
    00121         vector<BFIGAssignment const *>::const_iterator assignmentIter;
    00122         for (assignmentIter = assignments.begin(); assignmentIter != assignments.end();
    00123              assignmentIter++)
    00124         {
    00125                 assert(*assignmentIter);
    00126                 bestCost = bestCost + (*assignmentIter)->getCost();
    00127         }
    00128 }
    00129
    00131
    00132 BFIGImplicant::BFIGImplicant(vector<BFIGConstraint const *> const & unentailedConflictsList,
    00133                 BFIGObjectiveFunction const * of)
    00134 : assignments(), objectiveFunction(of),
    00135 #ifdef IMPLICANT_ENABLE_UNSORTED
    00136   assignmentsUnsorted(),
    00137 #endif
    00138   unentailedConflicts(unentailedConflictsList),
    00139   essentialConflict(false), markedFeasible(false),
    00140   siblingAssignments(), siblingParent(NULL)
    00141 {
    00142         bestCost = 0.0;
    00143 }
    00144
    00146
    00147 BFIGImplicant::BFIGImplicant(vector<BFIGAssignment const *> const & assignments_pList,
    00148                      vector<BFIGConstraint const *> const & unentailedConflictsList)
    00149 : assignments(assignments_pList), objectiveFunction(NULL),
    00150 #ifdef IMPLICANT_ENABLE_UNSORTED
    00151   assignmentsUnsorted(assignments_pList),
    00152 #endif
    00153   unentailedConflicts(unentailedConflictsList),
    00154   essentialConflict(false), markedFeasible(false),
    00155   siblingAssignments(), siblingParent(NULL)
    00156 {
    00157         // sort the assignments for comparison
    00158         {
    00159                 ListManipulator<BFIGAssignment const *> lm;
    00160                 lm.sort(assignments, assignment_less);
    00161         }
    00162
    00163         bestCost = 0.0;
    00164         vector<BFIGAssignment const *>::const_iterator assignmentIter;
    00165         for (assignmentIter = assignments.begin(); assignmentIter != assignments.end();
    00166              assignmentIter++)
    00167         {
    00168                 assert(*assignmentIter);
    00169                 bestCost = bestCost + (*assignmentIter)->getCost();
    00170         }
    00171 }
    00172
    00174
    00175 BFIGImplicant::BFIGImplicant(bool noConflicts)
    00176 : assignments(), objectiveFunction(NULL),
    00177   #ifdef IMPLICANT_ENABLE_UNSORTED
    00178   assignmentsUnsorted(),
    00179   #endif
    00180   unentailedConflicts(),
    00181   markedFeasible(false), siblingAssignments(), siblingParent(NULL)
    00182 {
    00183         bestCost = 0.0;
    00184         essentialConflict = !noConflicts;
    00185 }
    00186
    00188
    00189 BFIGImplicant::BFIGImplicant(const BFIGImplicant & i)
    00190 : assignments(i.assignments), objectiveFunction(i.objectiveFunction),
    00191   #ifdef IMPLICANT_ENABLE_UNSORTED
    00192   assignmentsUnsorted(i.assignmentsUnsorted),
    00193   #endif
    00194   unentailedConflicts(i.unentailedConflicts), bestCost(i.bestCost),
    00195   essentialConflict(i.essentialConflict), markedFeasible(i.markedFeasible),
    00196   siblingAssignments(i.siblingAssignments), siblingParent(NULL)
    00197 {
    00198         if (i.siblingParent)
    00199         {
    00200                 siblingParent = new BFIGImplicant(*(i.siblingParent));
    00201         }
    00202 }
    00203
    00205
    00206 BFIGImplicant::~BFIGImplicant()
    00207 {
    00208         if (siblingParent)
    00209         {
    00210                 delete siblingParent;
    00211         }
    00212 }
    00213
    00215
    00216 //private
    00217 // does not preserve the siblings of the source implicant!! Intentional.
    00218 BFIGImplicant::BFIGImplicant(BFIGImplicant const * parent,
    00219         BFIGAssignment const * extraAssign)
    00220 : assignments(parent->assignments), objectiveFunction(parent->objectiveFunction),
    00221 #ifdef IMPLICANT_ENABLE_UNSORTED
    00222   assignmentsUnsorted(parent->assignmentsUnsorted),
    00223 #endif
    00224   unentailedConflicts(parent->unentailedConflicts), bestCost(parent->bestCost),
    00225   essentialConflict(parent->essentialConflict), markedFeasible(false),
    00226   siblingAssignments(vector<BFIGAssignment const *>()), siblingParent(NULL)
    00227 {
    00228         LOG4CPLUS_DEBUG(mLogger, "BFIGImplicantCreateS: conflicts(" <<
    00229                 unentailedConflicts.size() << ')');
    00230
    00231         addAssignment(extraAssign);
    00232
    00233         LOG4CPLUS_DEBUG(mLogger, "Created BFIGImplicant: " << *this);
    00234         LOG4CPLUS_DEBUG(mLogger, "With conflicts(" << unentailedConflicts.size()
    00235                 << ')');
    00236 }
    00237
    00239
    00240 BFIGImplicant::BFIGImplicant(BFIGImplicant * parent,
    00241         BFIGAssignment const * extraAssign,
    00242         vector<BFIGAssignment const *> siblingAssigns)
    00243 : assignments(parent->assignments), objectiveFunction(parent->objectiveFunction),
    00244 #ifdef IMPLICANT_ENABLE_UNSORTED
    00245   assignmentsUnsorted(parent->assignmentsUnsorted),
    00246 #endif
    00247         unentailedConflicts(parent->unentailedConflicts), bestCost(parent->bestCost),
    00248   essentialConflict(parent->essentialConflict), markedFeasible(false),
    00249   siblingAssignments(siblingAssigns), siblingParent(NULL)
    00250 {
    00251         LOG4CPLUS_DEBUG(mLogger, "BFIGImplicantCreateS: conflicts(" <<
    00252                 unentailedConflicts.size() << ')');
    00253
    00254         if (!siblingAssignments.empty())
    00255         {
    00256                 siblingParent = parent;
    00257 #ifdef IMPLICANT_BASED_DP
    00258                 // rule out extensions that overlap this branch...
    00259                 siblingParent->addUnentailedConflict(extraAssign->getNegativeConstraint());
    00260 #endif
    00261         } else {
    00262                 LOG4CPLUS_WARN(mLogger, "It is inefficient to create a sibling Implicant "
    00263                         "with no siblings!");
    00264                 delete parent;
    00265         }
    00266         addAssignment(extraAssign);
    00267
    00268         LOG4CPLUS_DEBUG(mLogger, "Created BFIGImplicantS: " << *this);
    00269         LOG4CPLUS_DEBUG(mLogger, "With conflicts(" << unentailedConflicts.size()
    00270                 << ')');
    00271 }
    00272
    00274 //      PUBLIC METHODS
    00276
    00277 void
    00278 BFIGImplicant::addAssignment(BFIGAssignment const * a)
    00279 {
    00280
    00281 #ifdef IMPLICANT_ENABLE_UNSORTED
    00282         assignmentsUnsorted.push_back(a);
    00283 #endif
    00284         vector<BFIGAssignment const *>::iterator aIter;
    00285         for (aIter = assignments.begin(); aIter != assignments.end(); aIter++)
    00286         {
    00287                 if ( (*a) < (*(*aIter)) )
    00288                 {
    00289                         assignments.insert(aIter, a);
    00290                         break;
    00291                 }
    00292         }
    00293         if (aIter == assignments.end())
    00294         {
    00295                 assignments.push_back(a);
    00296         }
    00297
    00298         if(objectiveFunction != NULL)
    00299                 bestCost = objectiveFunction->getCost(assignments);
    00300         else
    00301                 bestCost += a->getCost();
    00302
    00303         // could fix unentailed conflicts here...
    00304 }
    00305
    00307
    00308 vector<BFIGAssignment const *>
    00309 BFIGImplicant::getAssignments() const
    00310 {
    00311         return assignments;
    00312 }
    00313
    00315
    00316 vector<BFIGAssignment const *>
    00317 BFIGImplicant::getAssignmentsUnsorted() const
    00318 {
    00319 #ifdef IMPLICANT_ENABLE_UNSORTED
    00320         return assignmentsUnsorted;
    00321 #else
    00322         return assignments;
    00323 #endif
    00324 }
    00325
    00327
    00328 double
    00329 BFIGImplicant::getBestCost() const
    00330 {
    00331         return bestCost;
    00332 }
    00333
    00335
    00336 double
    00337 BFIGImplicant::getTrueCost() const
    00338 {
    00339         double res = 0.0;
    00340         vector<BFIGAssignment const *>::const_iterator assignmentIter;
    00341         for (assignmentIter = assignments.begin();
    00342              assignmentIter != assignments.end();
    00343              assignmentIter++)
    00344         {
    00345                 res += (*assignmentIter)->getTrueCost();
    00346         }
    00347         return res;
    00348 }
    00349
    00351
    00352 void
    00353 BFIGImplicant::addUnentailedConflict(BFIGConstraint const * c)
    00354 {
    00355         // Inefficent to merge in place here - temporary.
    00356         vector<BFIGConstraint const *>::iterator iter;
    00357
    00358         for (iter = unentailedConflicts.begin();
    00359                 iter != unentailedConflicts.end(); iter++)
    00360         {
    00361                 if ( constraint_order(c, (*iter)) )
    00362                 {
    00363                         unentailedConflicts.insert(iter, c);
    00364                         break;
    00365                 }
    00366         }
    00367
    00368         if(iter == unentailedConflicts.end()) {
    00369                 unentailedConflicts.push_back(c);
    00370         }
    00371
    00372         if(siblingParent != NULL) {
    00373                 siblingParent->addUnentailedConflict(c);
    00374         }
    00375
    00376         LOG4CPLUS_DEBUG(mLogger, "Added 1 conflict to " << *this);
    00377         LOG4CPLUS_DEBUG(mLogger, "Conf(" << unentailedConflicts.size() << ')');
    00378 }
    00379
    00381
    00382 void
    00383 BFIGImplicant::addUnentailedConflicts(vector<BFIGConstraint const *> const & cs)
    00384 {
    00385         LOG4CPLUS_DEBUG(mLogger, "Conf(" << unentailedConflicts.size() << ')');
    00386
    00387         vector<BFIGConstraint const *>::const_iterator iter;
    00388         for (iter = cs.begin(); iter != cs.end(); iter++)
    00389         {
    00390                 unentailedConflicts.push_back((*iter));
    00391         }
    00392
    00393         {
    00394                 ListManipulator<BFIGConstraint const *> lm;
    00395                 lm.sort(unentailedConflicts, constraint_order);
    00396         }
    00397
    00398         if(siblingParent != NULL) {
    00399                 siblingParent->addUnentailedConflicts(cs);
    00400         }
    00401
    00402         LOG4CPLUS_DEBUG(mLogger, "Added " << cs.size() << " conflicts to " << *this);
    00403         LOG4CPLUS_DEBUG(mLogger, "Conf(" << unentailedConflicts.size() << ')');
    00404 }
    00405
    00407
    00408 bool
    00409 BFIGImplicant::entailsAllConflicts()  const
    00410 {
    00411         if (essentialConflict)
    00412                 return false;
    00413 #ifdef CONFLICT_CHECK_STRICT
    00414         return ((BFIGImplicant *)this)->entailsAllConflictsCheck();
    00415 #else
    00416         return (unentailedConflicts.size() == 0);
    00417 #endif
    00418 }
    00419
    00421
    00422 bool
    00423 BFIGImplicant::entailsAllConflictsCheck()
    00424 {
    00425         for (vector<BFIGConstraint const *>::iterator conflictIter =
    00426                                  unentailedConflicts.begin();
    00427              conflictIter != unentailedConflicts.end();
    00428              conflictIter = unentailedConflicts.erase(conflictIter))
    00429         {
    00430                 assert(*conflictIter);
    00431                 if (!(*conflictIter)->supportedBy(this))
    00432                         break;
    00433         }
    00434
    00435         return unentailedConflicts.empty();
    00436 }
    00437
    00439
    00440 void
    00441 BFIGImplicant::updateBestCost()
    00442 {
    00443         bestCost = 0.0;
    00444         vector<BFIGAssignment const *>::const_iterator assignmentIter;
    00445         for (assignmentIter = assignments.begin(); assignmentIter != assignments.end();
    00446              assignmentIter++)
    00447         {
    00448                 bestCost += (*assignmentIter)->getCost();
    00449         }
    00450 }
    00451
    00453
    00454 vector<BFIGImplicant *>
    00455 BFIGImplicant::generateChildren(vector<BFIGVariable *> const * varSet)
    00456 {
    00457         vector<BFIGImplicant *> ext;
    00458
    00459         // expand to children
    00460         list<BFIGAssignment const *> supports;
    00461         if (entailsAllConflictsCheck())
    00462         {
    00463                 // No conflict needs to be covered, so...
    00464                 if (varSet)
    00465                 {
    00466                         // extend to unspecified assignments - no particular order...
    00467                         vector<BFIGVariable *>::const_iterator vIter;
    00468                         for (vIter = varSet->begin(); vIter != varSet->end(); vIter++)
    00469                         {
    00470                                 if(*vIter == NULL)
    00471                                         continue;
    00472                                 if (!contains(*vIter))
    00473                                 {
    00474 #ifdef IMPLICANT_EXTEND_ALL
    00475                                         vector<BFIGAssignment const *> newSupports = (*vIter)->getAssignmentsSorted();
    00476 #ifdef _MSC_VER
    00477                                         ListManipulator<BFIGAssignment const *> lm;
    00478                                         lm.merge(supports, newSupports, assignment_cost_less);
    00479 #else
    00480                                         supports.merge<assignment_comp_func>(newSupports, assignment_cost_less);
    00481 #endif
    00482 #else
    00483                                         // this one is free...
    00484                                         vector<BFIGAssignment const *> vSupports = (*vIter)->getAssignmentsSorted();
    00485                                         for(unsigned int v = 0; v < vSupports.size(); v++){
    00486                                                 supports.push_back(vSupports[v]);
    00487                                         }
    00488                                         // could search for smallest one here...
    00489                                         break;
    00490 #endif
    00491                                 }
    00492                         }
    00493 /*#
    00494                         //#ifdef IMPLICANT_EXTEND_ALL
    00495                         //ListManipulator<BFIGAssignment const *> lm;
    00496                         //lm.sort(supports, assignment_cost_less);
    00497                         //#endif
    00498                         // else, all variables are already in implicant...
    00499 */
    00501                 } else
    00502                 {
    00503                         // can't extend to non-conflict-resolving assigns without knowing the variables.
    00504                 }
    00505         } else
    00506         {
    00507                 // we will cover another conflict
    00508                 BFIGConstraint const * firstConflict = unentailedConflicts.front();
    00509                 supports = firstConflict->getPrimeImplicants();
    00510         }
    00511 /*#
    00513         //      ListManipulator<BFIGAssignment *> lm;
    00514         //      lm.sort(supports, assignment_cost_less);
    00515 */
    00516         // find first consistent support
    00517         BFIGAssignment const * bestExtension = NULL;
    00518         list<BFIGAssignment const *>::iterator sIter = supports.begin();
    00519         while(sIter != supports.end())
    00520         {
    00521                 bestExtension = *sIter;
    00522                 sIter = supports.erase(sIter);
    00523                 if (bestExtension->compatible(assignments))
    00524                         break;
    00525                 else
    00526                         bestExtension = NULL;
    00527         }
    00528         //unsigned int x = 0;
    00529         //while (x < supports.size())
    00530         //{
    00531         //      bestExtension = supports[x++];
    00532         //      if (bestExtension->compatible(assignments))
    00533         //              break;
    00534         //      else
    00535         //              bestExtension = NULL;
    00536         //}
    00537         //supports.erase(supports.begin(), supports.begin() + x - 1);
    00538         if (bestExtension)
    00539         {
    00540                 BFIGImplicant * imp;
    00541                 if (supports.empty())
    00542                 {
    00543                         imp = new BFIGImplicant(this, bestExtension);
    00544                 } else
    00545                 {
    00546                         assert(!siblingParent);
    00547                         BFIGImplicant * newParent = new BFIGImplicant(*this);
    00548                         vector<BFIGAssignment const *> vSupports;
    00549                         for(sIter = supports.begin(); sIter != supports.end(); sIter++){
    00550                                 vSupports.push_back(*sIter);
    00551                         }
    00552                         imp = new BFIGImplicant(newParent, bestExtension, vSupports);
    00553                         // imp now owns the new memory...
    00554                 }
    00555
    00556                 // merge in order of cost
    00557                 if (ext.empty())
    00558                 {
    00559                         ext.push_back(imp);
    00560                 } else
    00561                 {
    00562                         assert(ext.size() == 1);
    00563                         if (ext.front()->getBestCost() < imp->getBestCost())
    00564                                 ext.push_back(imp);
    00565                         else{
    00566                                 ext.push_back(ext.front());
    00567                                 ext[0] = imp;
    00568                         }
    00569                 }
    00570         }
    00571
    00572         return ext;
    00573 }
    00574
    00576
    00577 BFIGImplicant * BFIGImplicant::generateSibling()
    00578 {
    00579         BFIGImplicant * sibimp = NULL;
    00580
    00581         // this one has been expanded before...
    00582         if (siblingParent != NULL)
    00583         {
    00584                 BFIGAssignment const * nextSiblingAssign = NULL;
    00585                 unsigned int x = 0;
    00586
    00587                 while (x < siblingAssignments.size())
    00588                 {
    00589                         nextSiblingAssign = siblingAssignments[x++];
    00590                         if (nextSiblingAssign->compatible(siblingParent->assignments))
    00591                                 break;
    00592                         else
    00593                                 nextSiblingAssign = NULL;
    00594                 }
    00595
    00596                 siblingAssignments.erase(siblingAssignments.begin(),
    00597                         siblingAssignments.begin() + x);
    00598
    00599                 if (nextSiblingAssign == NULL)
    00600                 {
    00601                         // all done with siblings
    00602                         // let it go...
    00603                         delete siblingParent;
    00604                 } else {
    00605                         if (!siblingAssignments.empty())
    00606                         {
    00607                                 sibimp = new BFIGImplicant(siblingParent, nextSiblingAssign,
    00608                                         siblingAssignments);
    00609                                 // sibimp now owns siblingParent memory...
    00610                         } else {
    00611                                 sibimp = new BFIGImplicant(siblingParent, nextSiblingAssign);
    00612                                 delete siblingParent;
    00613                         }
    00614                 }
    00615
    00616                 siblingParent = NULL;
    00617                 siblingAssignments.clear();
    00618         }
    00619
    00620         return sibimp;
    00621 }
    00622
    00624
    00625 vector<BFIGConstraint const *>
    00626 BFIGImplicant::getConstraints()  const
    00627 {
    00628         vector<BFIGConstraint const *> res;
    00629         vector<BFIGAssignment const *>::const_iterator aIter;
    00630         for (aIter = assignments.begin(); aIter != assignments.end(); aIter++)
    00631         {
    00632                 res.push_back((*aIter)->getConstraint());
    00633         }
    00634         return res;
    00635 }
    00636
    00638
    00639 void
    00640 BFIGImplicant::markFeasible()
    00641 {
    00642         markedFeasible = true;
    00643 }
    00644
    00646
    00647 bool
    00648 BFIGImplicant::isMarkedFeasible()  const
    00649 {
    00650         return markedFeasible;
    00651 }
    00652
    00654
    00655 BFIGImplicant *
    00656 BFIGImplicant::extendByAssignment(BFIGAssignment const * a) const
    00657 {
    00658         BFIGImplicant * ext = new BFIGImplicant(this, a);
    00659         return ext;
    00660 }
    00661
    00663
    00664 bool
    00665 BFIGImplicant::isEmpty() const
    00666 {
    00667         return (assignments.size() == 0);
    00668 }
    00669
    00671
    00672 unsigned int
    00673 BFIGImplicant::getLength() const
    00674 {
    00675         return assignments.size();
    00676 }
    00677
    00679
    00680 bool
    00681 BFIGImplicant::contains(BFIGAssignment const * a)  const
    00682 {
    00683         vector<BFIGAssignment const *>::const_iterator aIter;
    00684         for (aIter = assignments.begin(); aIter != assignments.end(); aIter++)
    00685         {
    00686                 if (a == (*aIter))  // pointer comparison
    00687                         return true;
    00688         }
    00689
    00690         return false;
    00691 }
    00692
    00694
    00695 bool
    00696 BFIGImplicant::contains(BFIGVariable const * v)  const
    00697 {
    00698         vector<BFIGAssignment const *>::const_iterator aIter;
    00699         for (aIter = assignments.begin(); aIter != assignments.end(); aIter++)
    00700         {
    00701                 if (v == (*aIter)->getVariable())  // pointer comparison
    00702                         return true;
    00703         }
    00704
    00705         return false;
    00706 }
    00707
    00709
    00710 bool
    00711 BFIGImplicant::compatible(BFIGAssignment const * a)  const
    00712 {
    00713         vector<BFIGAssignment const *>::const_iterator aIter;
    00714         for (aIter = assignments.begin(); aIter != assignments.end(); aIter++)
    00715         {
    00716                 if (!a->compatible((*aIter)))
    00717                         return false;
    00718         }
    00719
    00720         return true;
    00721 }
    00722
    00724
    00725 bool
    00726 BFIGImplicant::compatible(BFIGImplicant const & i)  const
    00727 {
    00728         vector<BFIGAssignment const *>::const_iterator aIter;
    00729         for (aIter = assignments.begin(); aIter != assignments.end(); aIter++)
    00730         {
    00731                 if (!i.compatible((*aIter)))
    00732                         return false;
    00733         }
    00734
    00735         return true;
    00736 }
    00737
    00739
    00740 void
    00741 BFIGImplicant::eliminateSiblings()
    00742 {
    00743         if (siblingParent)
    00744                 delete siblingParent;
    00745         siblingParent = NULL;
    00746         siblingAssignments.clear();
    00747 }
    00748
    00750
    00751 bool
    00752 BFIGImplicant::hasSiblings()  const
    00753 {
    00754         return !siblingAssignments.empty();
    00755 }
    00756
    00758
    00759 bool
    00760 BFIGImplicant::removeCurrentSibling()
    00761 {
    00762         if (siblingAssignments.empty())  // invalid! no more siblings!
    00763         {
    00764                 if (siblingParent)
    00765                         delete siblingParent;
    00766                 clear(false);
    00767                 return false;
    00768         }
    00769
    00770         if (!siblingParent)
    00771         {
    00772                 cerr << "Implicant cannot removeCurrentSibling with no parent!" << endl;
    00773                 clear(false);
    00774                 return false;
    00775         }
    00776
    00777         BFIGAssignment const * nextSiblingAssign = NULL;
    00778         unsigned int sib = 0;
    00779         while (sib < siblingAssignments.size())
    00780         {
    00781                 nextSiblingAssign = siblingAssignments[sib++];
    00782                 if (nextSiblingAssign->compatible(siblingParent->assignments))
    00783                         break;
    00784         }
    00785         siblingAssignments.erase(siblingAssignments.begin(),
    00786                 siblingAssignments.begin() + sib);
    00787         if (!nextSiblingAssign)  // all done with siblings
    00788         {
    00789                 delete siblingParent;
    00790                 clear(false);
    00791                 return false;
    00792         }
    00793
    00794         // replace the current sibling
    00795         assignments = siblingParent->assignments;
    00796 #ifdef IMPLICANT_ENABLE_UNSORTED
    00797         assignmentsUnsorted = siblingParent->assignmentsUnsorted;
    00798 #endif
    00799         unentailedConflicts = siblingParent->unentailedConflicts;
    00800         bestCost = siblingParent->bestCost;
    00801         essentialConflict = siblingParent->essentialConflict;
    00802         markedFeasible = false;  // ???
    00803         sib = 0;
    00804         if (!siblingAssignments.empty())
    00805         {
    00806                 // add in conflict to prevent redundant searching
    00807 #ifdef IMPLICANT_BASED_DP
    00808                 siblingParent->addUnentailedConflict(nextSiblingAssign->getNegativeConstraint());
    00809 #endif
    00810         } else
    00811         {
    00812                 delete siblingParent;
    00813                 siblingParent = NULL;
    00814         }
    00815         addAssignment(nextSiblingAssign);
    00816
    00817         return true;
    00818 }
    00819
    00821
    00822 // leaves it invalid, really:
    00823 void
    00824 BFIGImplicant::clear(bool noConflict)
    00825 {
    00826         eliminateSiblings();
    00827         assignments.clear();
    00828 #ifdef IMPLICANT_ENABLE_UNSORTED
    00829         assignmentsUnsorted.clear();
    00830 #endif
    00831         unentailedConflicts.clear();
    00832         essentialConflict = noConflict;
    00833 }
    00834
    00836
    00837 bool
    00838 BFIGImplicant::operator==(BFIGImplicant const * i)  const
    00839 {
    00840         if (!i)
    00841                 return false;
    00842         return (*this) == (*i);
    00843 }
    00844
    00846
    00847 bool
    00848 BFIGImplicant::operator==(BFIGImplicant const & i)  const
    00849 {
    00851         if (assignments.size() != i.assignments.size())
    00852                 return false;
    00853         if (essentialConflict != i.essentialConflict)
    00854                 return false;
    00855         /*# hack, for speed. Very distasteful...: */
    00856         double diff = getBestCost() - i.getBestCost();
    00857         if (diff < 0.0)  diff = -diff;
    00858         if (diff > 0.0000001)  //# ugly... even if both best costs are right...
    00859                 return false;
    00860
    00861         // assignments are sorted:
    00862         vector<BFIGAssignment const *>::const_iterator a1Iter;
    00863         vector<BFIGAssignment const *>::const_iterator a2Iter;
    00864         for (a1Iter = assignments.begin(), a2Iter = i.assignments.begin();
    00865              a1Iter != assignments.end(); a1Iter++, a2Iter++)
    00866         {
    00867                 //if (!( (*(*a1Iter)) == (*(*a2Iter)) ))
    00868                 if (!( (*a1Iter) == (*a2Iter) ))  // just use pointer comparison
    00869                         return false;
    00870         }
    00871
    00872         return true;
    00873 }
    00874
    00876
    00877 bool
    00878 BFIGImplicant::operator <(BFIGImplicant const &other)  const
    00879 {
    00880         double cost = getBestCost();
    00881         double otherCost = other.getBestCost();
    00882         if(cost < otherCost)
    00883                 return true;
    00884         if(cost > otherCost)
    00885                 return false;
    00886
    00887         bool entailsAll = entailsAllConflicts();
    00888         bool otherEntailsAll = other.entailsAllConflicts();
    00889         if (entailsAll && !otherEntailsAll)
    00890                 return true;
    00891
    00892         return false;
    00893 }
    00894
    00896
    00897 bool
    00898 BFIGImplicant::operator >(BFIGImplicant const &other)  const
    00899 {
    00900         double cost = getBestCost();
    00901         double otherCost = other.getBestCost();
    00902         if(cost > otherCost)
    00903                 return true;
    00904         if(cost < otherCost)
    00905                 return false;
    00906
    00907         bool entailsAll = entailsAllConflicts();
    00908         bool otherEntailsAll = other.entailsAllConflicts();
    00909         if (!entailsAll && otherEntailsAll)
    00910                 return true;
    00911
    00912         return false;
    00913 }
    00914
    00916
    00917 namespace Mers {
    00918         namespace Generators {
    00919                 namespace BFIG {
    00920                         ostream&
    00921                         operator<<(ostream& os, BFIGImplicant const & in)
    00922                         {
    00923                                 os << "[" ;
    00924                                 if (!in.terse)
    00925                                         os << in.getBestCost() << ": " ;
    00926
    00927                                 vector<BFIGAssignment const *> assigns = in.assignments;
    00928                                 {
    00929                                         ListManipulator<BFIGAssignment const *> lm;
    00930                                         lm.sort(assigns, assignment_less);
    00931                                 }
    00932                                 bool first = true;
    00933                                 vector<BFIGAssignment const *>::const_iterator assignmentIter;
    00934                                 for (assignmentIter = assigns.begin();
    00935                                                  assignmentIter != assigns.end(); assignmentIter++)
    00936                                 {
    00937                                         if (first)
    00938                                                 first = false;
    00939                                         else
    00940                                                 if (in.terse)
    00941                                                         os << " ";
    00942                                                 else
    00943                                                         os << ", ";
    00944                                         os << *(*assignmentIter) ;
    00945                                 }
    00946                                 if (in.essentialConflict)
    00947                                         os << " X";
    00948                                 if(!in.terse) {
    00949                                         if(!in.entailsAllConflicts())
    00950                                                 os << " C";
    00951                                 }
    00952                                 os << "]";
    00953                                 return os;
    00954                         }
    00955                 }
    00956         }
    00957 }
    00958
    00960