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

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

    00001
    00002 //
    00003 // Copyright (c) 2005           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 "BFIGImplicantNoMPI.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::BFIGImplicantNoMPI;
    00030 using Mers::Generators::BFIG::BFIGVariable;
    00031 using Mers::Generators::BFIG::BFIGAssignment;
    00032 using Mers::Generators::BFIG::BFIGConstraint;
    00033 using Mers::Generators::BFIG::ListManipulator;
    00034 using Mers::Generators::BFIG::BFIGObjectiveFunction;
    00035
    00037 //      CONSTRUCTOR
    00039
    00040 BFIGImplicantNoMPI::BFIGImplicantNoMPI(vector<BFIGConstraint const *> const & unentailedConflictsList,
    00041                 BFIGObjectiveFunction const * of)
    00042 : BFIGImplicant(unentailedConflictsList, of)
    00043 {
    00044         if(objectiveFunction != NULL)
    00045                 bestCost = objectiveFunction->getCost(assignments);
    00046 }
    00047
    00049
    00050 BFIGImplicantNoMPI::BFIGImplicantNoMPI(const BFIGImplicant & i)
    00051 : BFIGImplicant(i)
    00052 {
    00053         if(objectiveFunction != NULL)
    00054                 bestCost = objectiveFunction->getCost(assignments);
    00055 }
    00056
    00058
    00059 BFIGImplicantNoMPI::~BFIGImplicantNoMPI()
    00060 {
    00061 }
    00062
    00064
    00065 // protected
    00066 // does not preserve the siblings of the source implicant!! Intentional.
    00067 BFIGImplicantNoMPI::BFIGImplicantNoMPI(BFIGImplicant const * parent,
    00068         BFIGAssignment const * extraAssign)
    00069 : BFIGImplicant(parent, extraAssign)
    00070 {
    00071         LOG4CPLUS_DEBUG(mLogger, "Created BFIGImplicantNoMPI");
    00072
    00073         if(objectiveFunction != NULL)
    00074                 bestCost = objectiveFunction->getCost(assignments);
    00075 }
    00076
    00078
    00079 BFIGImplicantNoMPI::BFIGImplicantNoMPI(BFIGImplicant * parent,
    00080         BFIGAssignment const * extraAssign,
    00081         vector<BFIGAssignment const *> siblingAssigns)
    00082 : BFIGImplicant(parent, extraAssign, siblingAssigns)
    00083 {
    00084         LOG4CPLUS_DEBUG(mLogger, "Created BFIGImplicantNoMPI");
    00085
    00086         if(objectiveFunction != NULL)
    00087                 bestCost = objectiveFunction->getCost(assignments);
    00088 }
    00089
    00091 //      PUBLIC METHODS
    00093
    00094 /*
    00095 void
    00096 BFIGImplicantNoMPI::addAssignment(BFIGAssignment const * a)
    00097 {
    00098         // I don't know why the assignments in the implicant have to be sorted by
    00099         // variable uid but I'll leave it that way for now
    00100 #ifdef IMPLICANT_ENABLE_UNSORTED
    00101         assignmentsUnsorted.push_back(a);
    00102 #endif
    00103         vector<BFIGAssignment const *>::iterator aIter;
    00104         for (aIter = assignments.begin(); aIter != assignments.end(); aIter++)
    00105         {
    00106                 if ( (*a) < (*(*aIter)) )
    00107                 {
    00108                         assignments.insert(aIter, a);
    00109                         break;
    00110                 }
    00111         }
    00112         if (aIter == assignments.end())
    00113         {
    00114                 assignments.push_back(a);
    00115         }
    00116
    00117         LOG4CPLUS_DEBUG(mLogger, "Adding assignment");
    00118         if(objectiveFunction != NULL)
    00119                 bestCost = objectiveFunction->getCost(assignments);
    00120         else
    00121                 bestCost += a->getCost();
    00122 }
    00123 */
    00124
    00126
    00127 double
    00128 BFIGImplicantNoMPI::getBestCost() const
    00129 {
    00130         return bestCost;
    00131 }
    00132
    00134
    00135 double
    00136 BFIGImplicantNoMPI::getTrueCost() const
    00137 {
    00138         return bestCost;
    00139 }
    00140
    00142
    00143 void
    00144 BFIGImplicantNoMPI::updateBestCost()
    00145 {
    00146         cerr << "<BFIGImplicantNoMPI> ERROR: Should be updating costs through Objective Function!" << endl;
    00147 }
    00148
    00150
    00151 vector<BFIGImplicant *>
    00152 BFIGImplicantNoMPI::generateChildren(vector<BFIGVariable *> const * varSet)
    00153 {
    00154         vector<BFIGImplicant *> ext;
    00155
    00156         // No need to have a pointer to the parent anymore
    00157         delete siblingParent;
    00158         siblingParent = NULL;
    00159
    00160         // expand to children
    00161         list<BFIGAssignment const *> supports;
    00162         if (entailsAllConflictsCheck())
    00163         {
    00164                 // No conflict needs to be covered, so...
    00165                 if (varSet)
    00166                 {
    00167                         // extend to unspecified assignments - no particular order...
    00168                         vector<BFIGVariable *>::const_iterator vIter;
    00169                         for (vIter = varSet->begin(); vIter != varSet->end(); vIter++)
    00170                         {
    00171                                 if(*vIter == NULL)
    00172                                         continue;
    00173                                 if (!contains(*vIter))
    00174                                 {
    00175 // #ifdef IMPLICANT_EXTEND_ALL  // Not sure what this definition is.... removing for now
    00176 //                                      vector<BFIGAssignment const *> newSupports = (*vIter)->getAssignmentsSorted();
    00177 // #ifdef _MSC_VER
    00178 //                                      ListManipulator<BFIGAssignment const *> lm;
    00179 //                                      lm.merge(supports, newSupports, assignment_cost_less);
    00180 // #else
    00181 //                                      supports.merge<assignment_comp_func>(newSupports, assignment_cost_less);
    00182 // #endif
    00183 // #else
    00184                                         // this one is free...
    00185                                         vector<BFIGAssignment const *> vSupports = (*vIter)->getAssignments();  // Don't care if they're sorted
    00186                                         for(unsigned int v = 0; v < vSupports.size(); v++){
    00187                                                 supports.push_back(vSupports[v]);
    00188                                         }
    00189                                         break;
    00190 // #endif
    00191                                 }
    00192                         }
    00193                 } else
    00194                 {
    00195                         // can't extend to non-conflict-resolving assigns without knowing the variables.
    00196                 }
    00197         } else
    00198         {
    00199                 // we will cover another conflict
    00200                 BFIGConstraint const * firstConflict = unentailedConflicts.front();
    00201                 supports = firstConflict->getPrimeImplicants();         // This could be more efficient if we could
    00202                                                                         // prevent the prime implicants from being sorted
    00203         }
    00204
    00205         // place all the compatible supports in the queue
    00206         BFIGAssignment const * bestExtension = NULL;
    00207         list<BFIGAssignment const *>::iterator sIter = supports.begin();
    00208         while(sIter != supports.end())
    00209         {
    00210                 bestExtension = *sIter;
    00211                 sIter = supports.erase(sIter);
    00212                 if (bestExtension->compatible(assignments))
    00213                 {
    00214                         if(ext.empty())
    00215                                 ext.push_back(new BFIGImplicantNoMPI(this, bestExtension));
    00216                         else
    00217                         {
    00218                                 BFIGImplicant * newParent = new BFIGImplicantNoMPI(*this);
    00219                                 ext.push_back(new BFIGImplicantNoMPI(newParent, bestExtension));
    00220                         }
    00221                 }
    00222         }
    00223
    00224         return ext;
    00225 }
    00226
    00228
    00229 BFIGImplicant * BFIGImplicantNoMPI::generateSibling()
    00230 {
    00231         BFIGImplicant * sibimp = NULL;
    00232 //--------------------------------------------------------------------
    00233 // All siblings should already be place on the queue if the problem
    00234 // is MPI. Return NULL.
    00235 //--------------------------------------------------------------------
    00236 //
    00237 //      // this one has been expanded before...
    00238 //      if (siblingParent != NULL)
    00239 //      {
    00240 //              BFIGAssignment const * nextSiblingAssign = NULL;
    00241 //              unsigned int x = 0;
    00242 //
    00243 //              while (x < siblingAssignments.size())
    00244 //              {
    00245 //                      nextSiblingAssign = siblingAssignments[x++];
    00246 //                      if (nextSiblingAssign->compatible(siblingParent->getAssignments()))
    00247 //                              break;
    00248 //                      else
    00249 //                              nextSiblingAssign = NULL;
    00250 //              }
    00251 //
    00252 //              siblingAssignments.erase(siblingAssignments.begin(),
    00253 //                      siblingAssignments.begin() + x);
    00254 //
    00255 //              if (nextSiblingAssign == NULL)
    00256 //              {
    00257 //                      // all done with siblings
    00258 //                      // let it go...
    00259 //                      delete siblingParent;
    00260 //              } else {
    00261 //                      if (!siblingAssignments.empty())
    00262 //                      {
    00263 //                              sibimp = new BFIGImplicantNoMPI(siblingParent, nextSiblingAssign,
    00264 //                                      siblingAssignments);
    00265 //                              // sibimp now owns siblingParent memory...
    00266 //                      } else {
    00267 //                              sibimp = new BFIGImplicantNoMPI(siblingParent, nextSiblingAssign);
    00268 //                              delete siblingParent;
    00269 //                      }
    00270 //              }
    00271 //
    00272 //              siblingParent = NULL;
    00273 //              siblingAssignments.clear();
    00274 //      }
    00275
    00276         return sibimp;
    00277 }
    00278
    00280
    00281 namespace Mers {
    00282         namespace Generators {
    00283                 namespace BFIG {
    00284                         ostream&
    00285                         operator<<(ostream& os, BFIGImplicantNoMPI const & in)
    00286                         {
    00287                                 os << "NonMPI[" ;
    00288                                 if (!in.terse)
    00289                                         os << in.getBestCost() << ": " ;
    00290
    00291                                 vector<BFIGAssignment const *> assigns = in.assignments;
    00292                                 bool first = true;
    00293                                 vector<BFIGAssignment const *>::const_iterator assignmentIter;
    00294                                 for (assignmentIter = assigns.begin();
    00295                                                  assignmentIter != assigns.end(); assignmentIter++)
    00296                                 {
    00297                                         if (first)
    00298                                                 first = false;
    00299                                         else
    00300                                                 if (in.terse)
    00301                                                         os << " ";
    00302                                                 else
    00303                                                         os << ", ";
    00304                                         os << *(*assignmentIter) ;
    00305                                 }
    00306                                 if (in.essentialConflict)
    00307                                         os << " X";
    00308                                 if(!in.terse) {
    00309                                         if(!in.entailsAllConflicts())
    00310                                                 os << " C";
    00311                                 }
    00312                                 os << "]";
    00313                                 return os;
    00314                         }
    00315                 }
    00316         }
    00317 }
    00318
    00320