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 #ifndef __IMPLICANT__ 00015 #define __IMPLICANT__ 00016 00017 #include <cstdlib> 00018 #include <iostream> 00019 #include <vector> 00020 00021 #include <Mers/Utils/Logging/logger.h> 00022 00023 // reduce the unentailed conflicts for each node to a minimal set - a time 00024 // tradeoff. 00025 #define CONFLICT_CHECK_STRICT 00026 // Do dynamic programming implicitly in the implicant expansion 00027 //#define IMPLICANT_BASED_DP 00028 // allow unsorted list to be stored too? 00030 // allow the very inefficient expansion to all variable assignments when 00031 // no conflicts remain? (makes the DissentGenerator correct, but normally 00032 // failing on all choices for a single variable would be enough to indicate failure). 00033 //#define IMPLICANT_EXTEND_ALL 00034 00035 00036 namespace Mers { 00037 namespace Generators { 00038 namespace BFIG { 00039 00040 class BFIGVariable; 00041 class BFIGAssignment; 00042 class BFIGConstraint; 00043 class BFIGObjectiveFunction; 00044 00058 class BFIGImplicant 00059 { 00060 00061 public: 00062 //---------------------------------------------------- 00063 // TYPE DEFINITIONS & OVERLOADED OPERATORS 00064 //---------------------------------------------------- 00065 bool operator ==(BFIGImplicant const * i) const; 00066 bool operator ==(BFIGImplicant const & i) const; 00067 bool operator <(BFIGImplicant const &other) const; 00068 bool operator >(BFIGImplicant const &other) const; 00069 00070 //----------------------------------------------- 00071 // CONSTRUCTOR 00072 //----------------------------------------------- 00073 00074 BFIGImplicant(const BFIGImplicant & i); 00075 BFIGImplicant(std::vector<BFIGAssignment const *> const & assignments_pList); 00076 BFIGImplicant(std::vector<BFIGConstraint const *> const & unentailedConflictsList, 00077 BFIGObjectiveFunction const * of = NULL); 00078 BFIGImplicant(std::vector<BFIGAssignment const *> const & assignments_pList, 00079 std::vector<BFIGConstraint const *> const & unentailedConflictsList); 00080 00084 BFIGImplicant(bool noConflicts); 00085 virtual ~BFIGImplicant(); 00086 00087 //----------------------------------------------- 00088 // PUBLIC METHODS 00089 //----------------------------------------------- 00090 00091 std::vector<BFIGAssignment const *> getAssignments() const; 00092 std::vector<BFIGAssignment const *> getAssignmentsUnsorted() const; 00093 virtual void addAssignment(BFIGAssignment const * a); 00094 00095 virtual double getBestCost() const; 00096 virtual double getTrueCost() const; 00097 00098 // note that this is *not* cheap, and checks each remaining conflict. 00099 // however, it is more accurate, and will remove unneeded conflicts 00100 // for future use. 00101 bool entailsAllConflicts() const; 00102 00114 virtual std::vector<BFIGImplicant *> 00115 generateChildren(std::vector<BFIGVariable *> const * varSet = NULL); 00116 00123 virtual BFIGImplicant * generateSibling(); 00124 00134 BFIGImplicant * extendByAssignment(BFIGAssignment const * a) const; 00135 00136 bool isEmpty() const; 00137 unsigned int getLength() const; 00138 void clear(bool noConflict = false); 00139 00140 void addUnentailedConflict(BFIGConstraint const * c); 00141 void addUnentailedConflicts(std::vector<BFIGConstraint const *> const & cs); 00142 00143 virtual void updateBestCost(); 00144 00145 bool contains(BFIGAssignment const * a) const; 00146 bool contains(BFIGVariable const * v) const; 00147 bool compatible(BFIGAssignment const * a) const; 00148 bool compatible(BFIGImplicant const & i) const; 00149 std::vector<BFIGConstraint const *> getConstraints() const; 00150 00151 void markFeasible(); 00152 bool isMarkedFeasible() const; 00153 void eliminateSiblings(); 00154 bool hasSiblings() const; 00155 // returns false if no more siblings... 00156 bool removeCurrentSibling(); 00157 00158 static bool terse; 00159 00160 friend std::ostream& operator<<(std::ostream&, BFIGImplicant const &); 00161 00162 protected: 00163 00164 BFIGImplicant(); // Not implemented 00165 BFIGImplicant(BFIGImplicant const * i, 00166 BFIGAssignment const * extraAssignment); 00167 BFIGImplicant(BFIGImplicant * i, BFIGAssignment const * extraAssignment, 00168 std::vector<BFIGAssignment const *> siblingAssigns); 00169 00170 bool entailsAllConflictsCheck(); 00171 00172 //----------------------------------------------- 00173 // PRIVATE DATA MEMBERS 00174 //----------------------------------------------- 00175 00177 std::vector<BFIGAssignment const *> assignments; 00178 00183 BFIGObjectiveFunction const * objectiveFunction; 00184 00185 #ifdef IMPLICANT_ENABLE_UNSORTED 00187 std::vector<BFIGAssignment const *> assignmentsUnsorted; 00188 #endif 00189 00190 std::vector<BFIGConstraint const *> unentailedConflicts; 00191 00193 double bestCost; 00194 00195 00196 bool essentialConflict; 00197 00198 bool markedFeasible; 00199 std::vector<BFIGAssignment const *> siblingAssignments; 00200 BFIGImplicant * siblingParent; 00201 00203 static Logger mLogger; 00204 }; 00205 } 00206 } 00207 } 00208 00209 #endif //ndef __IMPLICANT__ 00210
1.5.0