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

# /Users/fpy/titan-1-5-MBARI/Mers/Generators/BFIG/BFIGImplicant.h

    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