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

- Alphabetical List
- Class List
- Class Hierarchy
- Class Members

# Mers::Generators::BFIG::BFIG Class Reference

`#include <BFIG.h>`

Inheritance diagram for Mers::Generators::BFIG::BFIG:

[legend]
Collaboration diagram for Mers::Generators::BFIG::BFIG:

[legend]
List of all members.

## Public Member Functions
| BFIG (std::vector< BFIGVariable * > const &variableSet, double cutoffCost, BFIGObjectiveFunction const *of)
| BFIG (std::vector< BFIGVariable * > const &variableSet, double cutoffCost)
| BFIG (std::vector< BFIGVariable * > const &variableSet)
virtual | ~BFIG ()
virtual Mers::Utils::Lang::String const | getName () const
virtual BFIGVariable * | getVariableByName (unsigned int variableName)
virtual BFIGVariable * | getVariableByName (Mers::Utils::Lang::String variableName)
virtual std::vector< BFIGVariable * > | getVariables () const
virtual void | setDebug (unsigned int debugState)
virtual void | addConflict (BFIGConstraint const *newConflict)
virtual void | addConflicts (std::vector< BFIGConstraint const * > const &newConflicts)
virtual BFIGImplicant const * | getBestImplicant (long maximumVisitedStateCount, long maxQueueSize)
virtual void | markBestFeasible ()
virtual unsigned int | getLargestQueue () const
virtual unsigned int | getLargestQueueSinceReset () const
virtual unsigned int | getNodesExpanded () const
virtual unsigned int | getNumberCandidatesSinceReset () const
virtual void | printStatistics (bool verbose=false) const
virtual void | printStatistics (log4cplus::Logger logger, bool verbose=false, log4cplus::LogLevel logLevel=log4cplus::DEBUG_LOG_LEVEL) const
virtual void | printQueue (bool verbose=false) const
virtual void | printQueue (log4cplus::Logger logger, bool verbose=false, log4cplus::LogLevel logLevel=log4cplus::DEBUG_LOG_LEVEL) const
virtual void | restart ()
virtual void | reset ()
virtual unsigned int | getNumberOfConflicts ()
## Protected Member Functions
virtual BFIGImplicant * | createNewImplicant (std::vector< BFIGConstraint const * > &con)
virtual void | searchForImplicant (long maxExpansionCount, long maxQueueSize)=0
virtual void | enqueueImplicants (std::vector< BFIGImplicant * > const &newImplicants)
virtual void | enqueueImplicant (BFIGImplicant *newUnexploredImplicant)
virtual void | insertSiblings (BFIGImplicant *sibling)
virtual void | insertChildren (BFIGImplicant *parent)
virtual void | insertExtensions (BFIGImplicant *node)
## Protected Attributes
Mers::Utils::Lang::String | mName
| The name of the Search Problem.
std::vector< BFIGVariable * > | mVariables
| A list of variables for the Search Problem.
BFIGObjectiveFunction const * | mObjectiveFunction
| The objective function Used by BFIGImplicant to decide how to determine the cost of the implicant and informs BFIG if the cost function is MPI. If mObjectiveFunction = NULL, the implicant will use the heritage approach of just adding the new assignment cost.
std::vector< BFIGConstraint const * > | mConflicts
BFIGImplicantHeap | mImplicantQueue
BFIGImplicant * | mCandidate
| The present candidate.
unsigned int | mNodesExpanded
unsigned int | mLargestQueue
unsigned int | mLargestQueueSinceReset
unsigned int | mDebug
unsigned int | mNumSolutions
| The number of solutions thus far generated.
unsigned int | mNumCandidatesSinceReset
## Static Protected Attributes
static log4cplus::Logger | mLogger
| The logger used to log all BFIG messages.

## Detailed Description

This class defines the Best First Implicant Generator (BFIG). It is this implicant generator that puts the "O" in "OpSAT", by producing assignments to design variables in best-first order.

Definition at line 40 of file BFIG.h.

## Constructor & Destructor Documentation

BFIG::BFIG | ( | std::vector< BFIGVariable * > const & | variableSet,
|  | double | cutoffCost,
|  | BFIGObjectiveFunction const * | of |
| ) |  |  |

Creates a new BFIG object.

Parameters:

  | variableSet | The set of variables over which BFIG is searching.
  | cutoffCost | The cost above which all candidates are pruned.
  | of | the objective function to be used with this BFIG. States whether the function is MPI and the cost/utility associated with each implicant.

Definition at line 56 of file BFIG.cpp.

References setDebug().

Here is the call graph for this function:

Mers::Generators::BFIG::BFIG::BFIG | ( | std::vector< BFIGVariable * > const & | variableSet,
|  | double | cutoffCost |
| ) |  |  |

Creates a new BFIG object.

Parameters:

  | variableSet | The set of variables over which BFIG is searching.
  | cutoffCost | The cost above which all candidates are pruned.

Mers::Generators::BFIG::BFIG::BFIG | ( | std::vector< BFIGVariable * > const & | variableSet | ) |

Creates a new BFIG object.

Parameters:

  | variableSet | The set of variables over which BFIG is searching.

BFIG::~BFIG | ( |  | ) | `[virtual]`

Destroys this object.

Definition at line 93 of file BFIG.cpp.

References Mers::Utils::Containers::DynamicArray::makeEmpty(), mCandidate, mConflicts, and mImplicantQueue.

Here is the call graph for this function:

## Member Function Documentation

String const BFIG::getName | ( |  | ) | const`[virtual]`

This method has been retained primarily for historical reasons, and can safely be ignored for now.

Definition at line 116 of file BFIG.cpp.

References mName.

Mers::Generators::BFIG::BFIGVariable * BFIG::getVariableByName | ( | unsigned int | variableName | ) | `[virtual]`

Retrieves a variable pointer, given the variable's id number.

NOTE: Variables are maintained internally to BFIG, rather than OpSAT. OpSAT will pass requests for variables to BFIG.

Parameters:

  | variableName | The variable's unique numeric identifier

Definition at line 141 of file BFIG.cpp.

References mVariables.

Mers::Generators::BFIG::BFIGVariable * BFIG::getVariableByName | ( | Mers::Utils::Lang::String | variableName | ) | `[virtual]`

Retrieves a variable pointer, given the variable's string name.

Parameters:

  | variableName | The variable's unique string identifier

Definition at line 124 of file BFIG.cpp.

References mVariables.

vector< Mers::Generators::BFIG::BFIGVariable * > BFIG::getVariables | ( |  | ) | const`[virtual]`

Retrieves a list of all current variables.

Definition at line 158 of file BFIG.cpp.

References mVariables.

void BFIG::setDebug | ( | unsigned int | debugState | ) | `[virtual]`

Sets the new debug verbosity mode. This effects the verbosity of the debug output. A value of 0 disables debug printing.

Parameters:

  | debugState | The new debug level.

Definition at line 416 of file BFIG.cpp.

References mDebug, and mLogger.

Referenced by BFIG(), and Mers::Generators::BFIG::BFIGGenerator::setDebug().

void BFIG::addConflict | ( | BFIGConstraint const * | newConflict | ) | `[virtual]`

Adds a new conflict which will be used to prune the candidates generated.

Parameters:

  | newConflict | A new conflict for BFIG to use to prune candidates. Note that BFIG assumes ownership of this object.

Definition at line 166 of file BFIG.cpp.

References Mers::Generators::BFIG::BFIGImplicant::addUnentailedConflict(), createNewImplicant(), Mers::Utils::Containers::DynamicArray::getLength(), Mers::Generators::BFIG::BFIGImplicantHeap::insert(), Mers::Utils::Containers::DynamicArray::isEmpty(), mCandidate, mConflicts, mImplicantQueue, and mLogger.

Referenced by Mers::Generators::BFIG::BFIGGenerator::addConflict().

Here is the call graph for this function:

virtual void Mers::Generators::BFIG::BFIG::addConflicts | ( | std::vector< BFIGConstraint const * > const & | newConflicts | ) | `[virtual]`

Adds a set of new conflicts which will be used to prune the candidates generated.

Parameters:

  | newConflicts | A set of new conflicts for BFIG to use to prune candidates. Note that BFIG assumes ownership of these objects.

Mers::Generators::BFIG::BFIGImplicant const * BFIG::getBestImplicant | ( | long | maximumVisitedStateCount,
|  | long | maxQueueSize |
| ) |  |  | `[virtual]`

Returns the next best candidate.

Parameters:

  | maximumVisitedStateCount | The maximum states to examine before giving up.
  | maxQueueSize | The largest number of states to keep in the queue.

Definition at line 229 of file BFIG.cpp.

References Mers::Generators::BFIG::BFIGImplicant::entailsAllConflicts(), insertExtensions(), Mers::Utils::Containers::DynamicArray::isEmpty(), mCandidate, mConflicts, mImplicantQueue, mLogger, and mNumCandidatesSinceReset.

Referenced by Mers::Generators::BFIG::BFIGGenerator::generateBestImplicant().

Here is the call graph for this function:

void BFIG::markBestFeasible | ( |  | ) | `[virtual]`

This method is used to "mark" the current best implicant as feasible. It really only applies when multiple, sequential calls will be made to search for implicants (e.g. multiple candidates are desired).

Definition at line 271 of file BFIG.cpp.

References insertSiblings(), mCandidate, and mNumSolutions.

Referenced by Mers::Generators::BFIG::BFIGGenerator::markBestFeasible().

Here is the call graph for this function:

unsigned int BFIG::getLargestQueue | ( |  | ) | const`[virtual]`

Returns the largest queue size since BFIG was instantiated

Definition at line 384 of file BFIG.cpp.

References mLargestQueue.

unsigned int BFIG::getLargestQueueSinceReset | ( |  | ) | const`[virtual]`

Returns the largest queue size since BFIG was instantiated or reset

Definition at line 392 of file BFIG.cpp.

References mLargestQueueSinceReset.

Referenced by Mers::Generators::BFIG::BFIGGenerator::getLargestQueueSinceReset().

unsigned int BFIG::getNodesExpanded | ( |  | ) | const`[virtual]`

Returns the number of nodes expanded so far.

Definition at line 400 of file BFIG.cpp.

References mNodesExpanded.

Referenced by Mers::Generators::BFIG::BFIGGenerator::getNumberOfSteps(), and Mers::Generators::BFIG::BFIGGenerator::getTotalNumberNodesExpanded().

unsigned int BFIG::getNumberCandidatesSinceReset | ( |  | ) | const`[virtual]`

Returns the number of candidates (solutions) generated since BFIG was reset

Definition at line 408 of file BFIG.cpp.

References mNumCandidatesSinceReset.

Referenced by Mers::Generators::BFIG::BFIGGenerator::getNumberCandidatesSinceReset().

void BFIG::printStatistics | ( | bool | verbose = `false` | ) | const`[virtual]`

Prints the statistics of the current search.

Parameters:

  | verbose | True for verbose output, in which case all statistics are printed. False for abbreviated statistics.

Reimplemented in Mers::Generators::BFIG::CDBFIG::CDBFIG.

Definition at line 425 of file BFIG.cpp.

References mLogger.

Referenced by Mers::Generators::BFIG::BFIGGenerator::printStatistics().

virtual void Mers::Generators::BFIG::BFIG::printStatistics | ( | log4cplus::Logger | logger,
|  | bool | verbose = `false`,
|  | log4cplus::LogLevel | logLevel = `log4cplus::DEBUG_LOG_LEVEL` |
| ) |  |  | const`[virtual]`

Prints the statistics of the current search.

Parameters:

  | logger | The logger to which the statistics are printed.
  | verbose | True for verbose output, in which case all statistics are printed. False for abbreviated statistics.
  | logLevel | The log level at which the logger should post messages.

Reimplemented in Mers::Generators::BFIG::CDBFIG::CDBFIG.

void BFIG::printQueue | ( | bool | verbose = `false` | ) | const`[virtual]`

Prints the contents of the queue.

Parameters:

  | verbose | True for verbose output, in which case the whole queue is printed. False causes only the first few (fixed number) elements to be printed.

Reimplemented in Mers::Generators::BFIG::CDBFIG::CDBFIG.

Definition at line 467 of file BFIG.cpp.

References mLogger.

virtual void Mers::Generators::BFIG::BFIG::printQueue | ( | log4cplus::Logger | logger,
|  | bool | verbose = `false`,
|  | log4cplus::LogLevel | logLevel = `log4cplus::DEBUG_LOG_LEVEL` |
| ) |  |  | const`[virtual]`

Prints the contents of the queue.

Parameters:

  | logger | The logger to which the queue is printed.
  | verbose | True for verbose output, in which case the whole queue is printed. False causes only the first few (fixed number) elements to be printed.
  | logLevel | The log level at which the logger should post messages.

Reimplemented in Mers::Generators::BFIG::CDBFIG::CDBFIG.

void BFIG::restart | ( |  | ) | `[virtual]`

Resets the generation process back to the beginning while keeping all conflict and prune items.

Definition at line 284 of file BFIG.cpp.

References createNewImplicant(), Mers::Generators::BFIG::BFIGImplicantHeap::insert(), Mers::Utils::Containers::DynamicArray::makeEmpty(), mCandidate, mConflicts, mImplicantQueue, and mLogger.

Referenced by reset(), and Mers::Generators::BFIG::BFIGGenerator::restart().

Here is the call graph for this function:

void BFIG::reset | ( |  | ) | `[virtual]`

Restarts the generator, eliminating all conflict and prune data. This is effectively like recreating the generator on the same data, and is somewhat more efficient than deleting the generator and creating it again.

Definition at line 298 of file BFIG.cpp.

References mConflicts, mLargestQueueSinceReset, mLogger, mNumCandidatesSinceReset, and restart().

Referenced by Mers::Generators::BFIG::BFIGGenerator::reset().

Here is the call graph for this function:

unsigned int BFIG::getNumberOfConflicts | ( |  | ) | `[virtual]`

Returns the number of conflicts generated thus far.

Returns:
  The number of conflicts in BFIG.

Definition at line 316 of file BFIG.cpp.

References mConflicts.

Referenced by Mers::Generators::BFIG::BFIGGenerator::getNumberOfConflicts().

BFIGImplicant * BFIG::createNewImplicant | ( | std::vector< BFIGConstraint const * > & | con | ) | `[protected, virtual]`

Creates a new Implicant depending on whether the objective is MPI

Definition at line 325 of file BFIG.cpp.

References Mers::Generators::BFIG::BFIGObjectiveFunction::isMPI(), and mObjectiveFunction.

Referenced by addConflict(), and restart().

Here is the call graph for this function:

void BFIG::insertSiblings | ( | BFIGImplicant * | sibling | ) | `[protected, virtual]`

Inserts the siblings of the implicant into the queue. Siblings all have the same parent in the search tree.

Parameters:

  | sibling | The sibling who's next siblings are entered into the queue.

Definition at line 508 of file BFIG.cpp.

References enqueueImplicant(), Mers::Generators::BFIG::BFIGImplicant::generateSibling(), mDebug, and mLogger.

Referenced by insertExtensions(), and markBestFeasible().

Here is the call graph for this function:

void BFIG::insertChildren | ( | BFIGImplicant * | parent | ) | `[protected, virtual]`

Inserts the children of the implicant into the queue. Children all share the common parent.

Parameters:

  | parent | The parent of all the new children being inserted.

Definition at line 530 of file BFIG.cpp.

References Mers::Generators::BFIG::BFIGImplicant::generateChildren(), mDebug, mLogger, and mVariables.

Referenced by insertExtensions().

Here is the call graph for this function:

void BFIG::insertExtensions | ( | BFIGImplicant * | node | ) | `[protected, virtual]`

Inserts the children and siblings of this node.

Parameters:

  | node | The node who's children and siblings are being added to the queue.

Definition at line 559 of file BFIG.cpp.

References insertChildren(), and insertSiblings().

Referenced by getBestImplicant().

Here is the call graph for this function:

## Member Data Documentation

std::vector<BFIGConstraint const *> Mers::Generators::BFIG::BFIG::mConflicts`[protected]`

The current set of conflicts in the Search Problem, maintained in increasing order by the number of assignments.

Definition at line 321 of file BFIG.h.

Referenced by addConflict(), getBestImplicant(), getNumberOfConflicts(), reset(), restart(), and ~BFIG().

BFIGImplicantHeap Mers::Generators::BFIG::BFIG::mImplicantQueue`[protected]`

A queue of unexplored implicant search tree nodes, sorted in best first order according to the binary cost function.

Definition at line 325 of file BFIG.h.

Referenced by addConflict(), enqueueImplicant(), getBestImplicant(), restart(), and ~BFIG().

unsigned int Mers::Generators::BFIG::BFIG::mNodesExpanded`[protected]`

The total number of nodes thus far expanded by this object.

Definition at line 332 of file BFIG.h.

Referenced by getNodesExpanded().

unsigned int Mers::Generators::BFIG::BFIG::mLargestQueue`[protected]`

The largest number of elements on the queue since the creation of this object.

Definition at line 336 of file BFIG.h.

Referenced by enqueueImplicant(), and getLargestQueue().

unsigned int Mers::Generators::BFIG::BFIG::mLargestQueueSinceReset`[protected]`

The largest number of elements on the queue since the last reset or the creation of the object, which ever is more recent.

Definition at line 341 of file BFIG.h.

Referenced by enqueueImplicant(), getLargestQueueSinceReset(), and reset().

unsigned int Mers::Generators::BFIG::BFIG::mDebug`[protected]`

When 0, debug printing is disabled. Larger values increase the verbosity of the debug output.

Definition at line 345 of file BFIG.h.

Referenced by insertChildren(), insertSiblings(), and setDebug().

unsigned int Mers::Generators::BFIG::BFIG::mNumCandidatesSinceReset`[protected]`

The number of candidates generated since reset. Only counts candidates that are fully developed (full assignment to mode variables w/o exhausting the search tree) and satisfy all known conflicts

Definition at line 353 of file BFIG.h.

Referenced by getBestImplicant(), getNumberCandidatesSinceReset(), and reset().

The documentation for this class was generated from the following files:

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