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

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

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

`#include <BFIGGenerator.h>`

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

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

[legend]
List of all members.

## Public Types
typedef Mers::Utils::Containers::DynamicArrayTemplate< Mers::Models::Base::BaseModelSentence const > | GuardArray
## Public Member Functions
| BFIGGenerator (BFIGFactory &bfigFactory, Mers::Models::Base::BaseModelVariableArray const &variableSet, Mers::Generators::BFIG::BFIGObjectiveFunction const *ocspObjectiveFunction, Mers::Models::Base::BaseModelVariableArray const &allVariables, double cutoffCost)
| BFIGGenerator (BFIGFactory &bfigFactory, Mers::Models::Base::BaseModelVariableArray const &variableSet, Mers::Models::Base::BaseModelVariableArray const &allVariables, Mers::Utils::Containers::IntegerArray const &valueMap, std::vector< double > const &probabilities, double cutoffCost, bool useProb=true)
| BFIGGenerator (BFIGFactory &bfigFactory, Mers::Models::Base::BaseModelVariableArray const &variableSet, Mers::Models::Base::BaseModelVariableArray const &allVariables, Mers::Utils::Containers::IntegerArray const &valueMap, std::vector< double > const &probabilities, bool useProb=true)
virtual | ~BFIGGenerator ()
virtual void | addConflict (Mers::Models::Base::BaseModelAssignmentArray const *newConflict)
virtual void | addConflict (Mers::Models::Base::BaseModelAssignmentArray const &newConflict)
virtual void | addConflicts (Mers::Models::Base::BaseModelClauseArray const &newConflicts)
void | addConflict (BFIGConstraint const *newConflict)
void | addConflict (BFIGConstraint const &newConflict)
void | addConflicts (std::vector< BFIGConstraint const * >const &newConflicts)
Mers::Models::Base::BaseModelAssignmentArray const * | generateBestImplicant (long maximumVisitedStateCount, long maxSize, bool expand=true)
void | markBestFeasible ()
virtual void | printStatistics (bool verbose=false) const
virtual void | restart ()
virtual void | reset ()
virtual void | setDebug (unsigned int state)
int | updateProbability (unsigned int variableUID, unsigned int valueUID, double prob)
int | updateProbabilities (unsigned int variableUID, double probs[])
int | updateAllProbabilities (Mers::Models::Base::BaseModelVariableArray const &decisionVars, Mers::Utils::Containers::IntegerArray const &valueMap, std::vector< double > const &allProbabilities)
int | updateCost (unsigned int variableUID, unsigned int valueUID, double cost)
int | updateCosts (unsigned int variableUID, double costs[])
virtual unsigned int | getFullAssignmentSize ()
unsigned int | getNumberOfConflicts ()
unsigned int | getLargestQueueSinceReset ()
unsigned int | getTotalNumberNodesExpanded ()
unsigned int | getNumberCandidatesSinceReset ()
virtual double | getNumberOfSteps () const
## Protected Member Functions
BFIGVariable * | variableToVariable (unsigned int bfigVarIndex, Mers::Models::Base::BaseModelVariable const *varIn, std::vector< double > &costs, bool useProb) const
void | sortBMVariables (Mers::Models::Base::BaseModelVariableArray const &unsortedArray, Mers::Models::Base::BaseModelVariableArray &sortedArray)
unsigned int | bfindBMVariable (Mers::Models::Base::BaseModelVariableArray &sortedVars, unsigned int uid)
unsigned int | getBFIGVariable (unsigned int bmVarUID, BFIGVariable *&bfigVar)

## Detailed Description

BFIG Assignment Generator

Author:
  John Van Eepoel

  Robert Ragno

  Paul H. Elliott

Date:
  6.19.01

Definition at line 69 of file BFIGGenerator.h.

## Constructor & Destructor Documentation

BFIGGenerator::BFIGGenerator | ( | BFIGFactory & | bfigFactory,
|  | Mers::Models::Base::BaseModelVariableArray const & | variableSet,
|  | Mers::Generators::BFIG::BFIGObjectiveFunction const * | ocspObjectiveFunction,
|  | Mers::Models::Base::BaseModelVariableArray const & | allVariables,
|  | double | cutoffCost |
| ) |  |  |

Creates a new BFIG Generator using a specified BFIGObjectiveFunction This contructor removes the application specific objective function from being hard-coded in the BFIGImplicants so that different cost functions can be provided. If a BFIGObjectiveFunction is not provided, the default is to use the previous method of assigning a value to each assignment in every BFIGVariable. BFIGVariable will eventually need to be changed as BFIG is cleaned up to more generally use the BFIGObjectiveFunction. This constructor should NOT be used unless a valid BFIGObjectiveFunction is provided, otherwise all values in all variables will be set to zero.

Parameters:

  | bfigFactory | The factory used to create the BFIG instance used by this generator interface.
  | variableSet | The set of variables being enumerated over. BFIG will generate all of its candidates from these variables.
  | ocspObjectiveFunction | the OCSP objective function to be used with BFIG to enumerate the solutions to the OCSP in best-first order.
  | allVariables | The set of all variables in the model, needed to express some conflicts.
  | cutoffCost | the cost of the most expensive item that can be returned

Definition at line 57 of file BFIGGenerator.cpp.

References bfindBMVariable(), Mers::Generators::BFIG::BFIGFactory::create(), Mers::Generators::AssignmentGeneratorInterface::debug, Mers::Utils::Containers::DynamicArray::getLength(), and sortBMVariables().

Here is the call graph for this function:

Mers::Generators::BFIG::BFIGGenerator::BFIGGenerator | ( | BFIGFactory & | bfigFactory,
|  | Mers::Models::Base::BaseModelVariableArray const & | variableSet,
|  | Mers::Models::Base::BaseModelVariableArray const & | allVariables,
|  | Mers::Utils::Containers::IntegerArray const & | valueMap,
|  | std::vector< double > const & | probabilities,
|  | double | cutoffCost,
|  | bool | useProb = `true` |
| ) |  |  |

Creates a new BFIG Generator using raw probability data.

Parameters:

  | bfigFactory | The factory used to create the BFIG instance used by this generator interface.
  | variableSet | The set of variables being enumerated over. BFIG will generate all of its candidates from these variables.
  | allVariables | The set of all variables in the model, needed to express some conflicts.
  | valueMap | A set of indexes that indicate where the probability information begins for each variable. The index of the variable in the variable array is the same as the index in the valueMap. This value in the valueMap is * the starting index of the probabilities values in allProbabilities. valueMap[index] -> start index of first value in allProbabilities. Note that this procedure assumes the indices are stored linearly, so valueMap[index + 1] - valueMap[index] = # values in probabilites[valueMap[index]]. ValueMap[0] is the base index into the probabilites.
  | probabilities | The probabilities of the assignments or transitions. If this vector has the same length as the set of values, it provides a probability per assignment. Otherwise, if it has a length that is the square of the length of the set of values, then it provides a probability mapping between every pair of assignments.
  | cutoffCost | the cost of the most expensive item that can be returned
  | useProb | If this is true, BFIG will treat the values given in the probabilities argument as probabilities (it will take the negative log of each value and will multiply them to combine them). Otherwise BFIG will just treat the values in the probability argument as additive costs.

Mers::Generators::BFIG::BFIGGenerator::BFIGGenerator | ( | BFIGFactory & | bfigFactory,
|  | Mers::Models::Base::BaseModelVariableArray const & | variableSet,
|  | Mers::Models::Base::BaseModelVariableArray const & | allVariables,
|  | Mers::Utils::Containers::IntegerArray const & | valueMap,
|  | std::vector< double > const & | probabilities,
|  | bool | useProb = `true` |
| ) |  |  |

Creates a new BFIG Generator using raw probability data.

Parameters:

  | bfigFactory | The factory used to create the BFIG instance used by this generator interface.
  | variableSet | The set of variables being enumerated over. BFIG will generate all of its candidates from these variables.
  | allVariables | The set of all variables in the model, needed to express some conflicts.
  | valueMap | A set of indexes that indicate where the probability information begins for each variable. The index of the variable in the variable array is the same as the index in the valueMap. This value in the valueMap is * the starting index of the probabilities values in allProbabilities. valueMap[index] -> start index of first value in allProbabilities. Note that this procedure assumes the indices are stored linearly, so valueMap[index + 1] - valueMap[index] = # values in probabilites[valueMap[index]]. ValueMap[0] is the base index into the probabilites.
  | probabilities | The probabilities of the assignments or transitions. If this vector has the same length as the set of values, it provides a probability per assignment. Otherwise, if it has a length that is the square of the length of the set of values, then it provides a probability mapping between every pair of assignments.
  | useProb | If this is true, BFIG will treat the values given in the probabilities argument as probabilities (it will take the negative log of each value and will multiply them to combine them). Otherwise BFIG will just treat the values in the probability argument as additive costs.

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

Destroys this object

Definition at line 177 of file BFIGGenerator.cpp.

## Member Function Documentation

void BFIGGenerator::addConflict | ( | Mers::Models::Base::BaseModelAssignmentArray const * | newConflict | ) | `[virtual]`

adds a conflict to this generator, preventing the generation of supersets of the conflict

Parameters:

  | newConflict | the new conflict being added

Implements Mers::Generators::AssignmentGeneratorInterface.

Definition at line 199 of file BFIGGenerator.cpp.

References Mers::Generators::BFIG::BFIG::addConflict(), Mers::Generators::BFIG::BFIGVariable::getAssignmentByValue(), getBFIGVariable(), Mers::Utils::Containers::DynamicArray::getLength(), Mers::Models::Base::BaseModelValue::getUID(), and Mers::Models::Base::BaseModelVariable::getUID().

Referenced by addConflict(), addConflicts(), and tut::BFIGGeneratorTester::testBFIG().

Here is the call graph for this function:

void BFIGGenerator::addConflict | ( | Mers::Models::Base::BaseModelAssignmentArray const & | newConflict | ) | `[virtual]`

adds a conflict to this generator, preventing the generation of supersets of the conflict

Parameters:

  | newConflict | the new conflict being added

Implements Mers::Generators::AssignmentGeneratorInterface.

Definition at line 225 of file BFIGGenerator.cpp.

References addConflict().

Here is the call graph for this function:

void BFIGGenerator::addConflicts | ( | Mers::Models::Base::BaseModelClauseArray const & | newConflicts | ) | `[virtual]`

adds a list of conflicts to this generator, preventing the generation of supersets of any of the conflicts

Parameters:

  | newConflicts | the new conflicts being added

Implements Mers::Generators::AssignmentGeneratorInterface.

Definition at line 233 of file BFIGGenerator.cpp.

References addConflict(), and Mers::Utils::Containers::DynamicArray::getLength().

Here is the call graph for this function:

BaseModelAssignmentArray const * BFIGGenerator::generateBestImplicant | ( | long | maximumVisitedStateCount,
|  | long | maxSize,
|  | bool | expand = `true` |
| ) |  |  | `[virtual]`

generates the next best implicant to be tested by the SAT engine.

Parameters:

  | maximumVisitedStateCount | the maximum number of nodes that can be searched before giving up
  | maxSize | Maximum space (search elements) that can be stored at once (memory usage restriction)
  | expand | true if the generated state should be expanded to a full set of assignments or false if it can be returned as a partial list.

Returns:
  NULL if no implicant could be generated or the next (progressively) best implicant as compared to the one returned previously.

Implements Mers::Generators::AssignmentGeneratorInterface.

Definition at line 272 of file BFIGGenerator.cpp.

References Mers::Generators::AssignmentGeneratorInterface::debug, Mers::Generators::BFIG::BFIGImplicant::getAssignments(), Mers::Generators::BFIG::BFIG::getBestImplicant(), Mers::Models::Base::BaseModelVariable::getValue(), Mers::Utils::Containers::DynamicArray::makeEmpty(), and Mers::Models::Base::BaseModelAssignmentArray::pushBack().

Referenced by tut::BFIGGeneratorTester::testBFIG().

Here is the call graph for this function:

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

when called, sets the last returned implicant as a feasible solution to the problem being solved. No supersets of this implicant will be returned.

Implements Mers::Generators::AssignmentGeneratorInterface.

Definition at line 307 of file BFIGGenerator.cpp.

References Mers::Generators::BFIG::BFIG::markBestFeasible().

Referenced by tut::BFIGGeneratorTester::testBFIG().

Here is the call graph for this function:

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

Prints out the performance statistics of the assignment generator

Parameters:

  | verbose | true if detailed statistics should be printed, otherwise only a summary is printed.

Implements Mers::Generators::AssignmentGeneratorInterface.

Definition at line 315 of file BFIGGenerator.cpp.

References Mers::Generators::BFIG::BFIG::printStatistics().

Here is the call graph for this function:

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

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

Implements Mers::Generators::AssignmentGeneratorInterface.

Definition at line 322 of file BFIGGenerator.cpp.

References Mers::Generators::BFIG::BFIG::restart().

Here is the call graph for this function:

void BFIGGenerator::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.

Implements Mers::Generators::AssignmentGeneratorInterface.

Definition at line 329 of file BFIGGenerator.cpp.

References Mers::Generators::BFIG::BFIG::reset().

Here is the call graph for this function:

void BFIGGenerator::setDebug | ( | unsigned int | state | ) | `[virtual]`

sets the debug state of this generator

Parameters:

  | state | the new debug state of the generator

Reimplemented from Mers::Generators::AssignmentGeneratorInterface.

Definition at line 337 of file BFIGGenerator.cpp.

References Mers::Generators::BFIG::BFIG::setDebug(), and Mers::Generators::AssignmentGeneratorInterface::setDebug().

Here is the call graph for this function:

int BFIGGenerator::updateProbability | ( | unsigned int | variableUID,
|  | unsigned int | valueUID,
|  | double | prob |
| ) |  |  |

Updates the cost of the particular assignment to a new value.

Parameters:

  | variableUID | The UID of the variable being updated.
  | valueUID | The UID of value of the current state for this variable.
  | prob | The new probability.

Returns:
  0 on success or a positive value if the variable was not found.

Definition at line 360 of file BFIGGenerator.cpp.

References getBFIGVariable(), Mers::Generators::BFIG::BFIGVariable::probToCost(), and Mers::Generators::BFIG::BFIGVariable::setCost().

Here is the call graph for this function:

int BFIGGenerator::updateProbabilities | ( | unsigned int | variableUID,
|  | double | probs[] |
| ) |  |  |

Updates all of the costs of the particular variable for each assignent.

Parameters:

  | variableUID | The UID of the variable being updated.
  | probs | The new probabilities for all the values of this variable.

Returns:
  0 on success or a positive value if the variable was not found.

Definition at line 373 of file BFIGGenerator.cpp.

References getBFIGVariable(), Mers::Generators::BFIG::BFIGVariable::getDomainTotalSize(), Mers::Generators::BFIG::BFIGVariable::probToCost(), and Mers::Generators::BFIG::BFIGVariable::setCosts().

Here is the call graph for this function:

int Mers::Generators::BFIG::BFIGGenerator::updateAllProbabilities | ( | Mers::Models::Base::BaseModelVariableArray const & | decisionVars,
|  | Mers::Utils::Containers::IntegerArray const & | valueMap,
|  | std::vector< double > const & | allProbabilities |
| ) |  |  |

Updates all of the costs of the all decision variables for each assignent.

Parameters:

  | decisionVars | The decision variables whos probabilities are to be changed
  | valueMap | A set of indexes that indicate where the probability information begins for each variable. The index of the variable in the variable array is the same as the index in the valueMap. This value in the valueMap is * the starting index of the probabilities values in allProbabilities. valueMap[index] -> start index of first value in allProbabilities. Note that this procedure assumes the indices are stored linearly, so valueMap[index + 1] - valueMap[index] = # values in probabilites[valueMap[index]]
  | allProbabilities | The new probabilities for all the values of all the decision variables

Returns:
  0 on success or a positive value if the variable was not found.

int BFIGGenerator::updateCost | ( | unsigned int | variableUID,
|  | unsigned int | valueUID,
|  | double | cost |
| ) |  |  |

Updates the cost of the particular assignment to a new value.

Parameters:

  | variableUID | The UID of the variable being updated.
  | valueUID | The UID of value of the current state for this variable.
  | cost | The new cost.

Returns:
  0 on success or a positive value if the variable was not found.

Definition at line 414 of file BFIGGenerator.cpp.

References getBFIGVariable(), and Mers::Generators::BFIG::BFIGVariable::setCost().

Here is the call graph for this function:

int BFIGGenerator::updateCosts | ( | unsigned int | variableUID,
|  | double | costs[] |
| ) |  |  |

Updates all of the costs of the particular variable for each assignent.

Parameters:

  | variableUID | The UID of the variable being updated.
  | valueUID | The UID of value of the current state for this variable.
  | costs | The new costs for all the values of this variable.

Returns:
  0 on success or a positive value if the variable was not found.

Definition at line 426 of file BFIGGenerator.cpp.

References getBFIGVariable(), and Mers::Generators::BFIG::BFIGVariable::setCosts().

Referenced by Mers::Solvers::Entailment::GI::GoalInterpreter::updateReachableStates().

Here is the call graph for this function:

unsigned int BFIGGenerator::getFullAssignmentSize | ( |  | ) | `[virtual]`

Returns the size of a candidate that represents a full assignment.

Returns:
  the number of assignments required to have a full assignment.

Implements Mers::Generators::AssignmentGeneratorInterface.

Definition at line 437 of file BFIGGenerator.cpp.

Referenced by tut::BFIGGeneratorTester::testBFIG().

unsigned int Mers::Generators::BFIG::BFIGGenerator::getNumberOfConflicts | ( |  | ) | `[inline]`

Returns the number of conflicts generated thus far.

Returns:
  The number of conflicts in BFIG.

Definition at line 410 of file BFIGGenerator.h.

References Mers::Generators::BFIG::BFIG::getNumberOfConflicts().

Here is the call graph for this function:

unsigned int Mers::Generators::BFIG::BFIGGenerator::getLargestQueueSinceReset | ( |  | ) | `[inline]`

Returns the largest number of elements in the BFIG queue between resets

Returns:
  The largest number of elements in the BFIG queue.

Definition at line 420 of file BFIGGenerator.h.

References Mers::Generators::BFIG::BFIG::getLargestQueueSinceReset().

Here is the call graph for this function:

unsigned int Mers::Generators::BFIG::BFIGGenerator::getTotalNumberNodesExpanded | ( |  | ) | `[inline]`

Returns the total number of elements expanded by BFIG since it was instantiated

Returns:
  The total number of elements expanded by BFIG.

Definition at line 430 of file BFIGGenerator.h.

References Mers::Generators::BFIG::BFIG::getNodesExpanded().

Here is the call graph for this function:

unsigned int Mers::Generators::BFIG::BFIGGenerator::getNumberCandidatesSinceReset | ( |  | ) | `[inline]`

Returns the total number of elements expanded by BFIG since it was instantiated

Returns:
  The total number of elements expanded by BFIG.

Definition at line 440 of file BFIGGenerator.h.

References Mers::Generators::BFIG::BFIG::getNumberCandidatesSinceReset().

Here is the call graph for this function:

virtual double Mers::Generators::BFIG::BFIGGenerator::getNumberOfSteps | ( |  | ) | const`[inline, virtual]`

Returns the number of steps taken by this interface towards solving the problem.

Implements Mers::Generators::AssignmentGeneratorInterface.

Definition at line 448 of file BFIGGenerator.h.

References Mers::Generators::BFIG::BFIG::getNodesExpanded().

Here is the call graph for this function:

BFIGVariable* Mers::Generators::BFIG::BFIGGenerator::variableToVariable | ( | unsigned int | bfigVarIndex,
|  | Mers::Models::Base::BaseModelVariable const * | varIn,
|  | std::vector< double > & | costs,
|  | bool | useProb |
| ) |  |  | const`[protected]`

Creates a BFIG Variable given a BM Variable

Parameters:

  | bfigVarIndex | The index that should be assigned to the BFIG variable.
  | varIn | Base Model Variable to convert to a BFIG Variable.
  | cost | The costs associated with this variable, one for each value.
  | useProb | Whether or not to treat the cost as a probability.

Returns:
  the created Variable

void BFIGGenerator::sortBMVariables | ( | Mers::Models::Base::BaseModelVariableArray const & | unsortedArray,
|  | Mers::Models::Base::BaseModelVariableArray & | sortedArray |
| ) |  |  | `[protected]`

Sorts the first array of variables by UID and stores the sorted array in the second array.

Parameters:

  | unsortedArray | The set of unsorted variables.
  | sortedArray | The sorted variables are returned here.

Definition at line 455 of file BFIGGenerator.cpp.

References bfindBMVariable(), Mers::Utils::Containers::DynamicArray::getLength(), Mers::Utils::Containers::DynamicArray::makeEmpty(), Mers::Models::Base::BaseModelVariableArray::pushBack(), and Mers::Utils::Containers::DynamicArray::resize().

Referenced by BFIGGenerator().

Here is the call graph for this function:

unsigned int BFIGGenerator::bfindBMVariable | ( | Mers::Models::Base::BaseModelVariableArray & | sortedVars,
|  | unsigned int | uid |
| ) |  |  | `[protected]`

Retrieves a BM Variable based on its UID from the sorted list of BM Variables.

Parameters:

  | sortedVars | The sorted list of variables.
  | uid | The UID we wish to find.

Returns:
  The index of the variable with the desired UID or the index where the UID would be inserted (so the index of the first variable that has a larger UID). It returns the length of the array if the UID is larger than any present variables.

Definition at line 509 of file BFIGGenerator.cpp.

References Mers::Utils::Containers::DynamicArray::getLength().

Referenced by BFIGGenerator(), getBFIGVariable(), and sortBMVariables().

Here is the call graph for this function:

unsigned int BFIGGenerator::getBFIGVariable | ( | unsigned int | bmVarUID,
|  | BFIGVariable *& | bfigVar |
| ) |  |  | `[protected]`

Retrieves the BFIG variable that corresponds to the BMVariable with the corresponding UID.

Parameters:

  | bmVarUID | The UID of the BM Variable for which we're trying to find the corresponding BFIG Variable.
  | bfigVar | The BFIG Variable is returned here, if found.

Returns:
  0 on success or a positive value if the variable could not be found.

Definition at line 531 of file BFIGGenerator.cpp.

References bfindBMVariable(), and Mers::Utils::Containers::DynamicArray::getLength().

Referenced by addConflict(), updateCost(), updateCosts(), updateProbabilities(), and updateProbability().

Here is the call graph for this function:

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

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