|
|||
|
|
|
|||
|
|
Standard pools. More...
#include <ogdf/lib/abacus/standardpool.h>
Inheritance diagram for abacus::StandardPool< BaseType, CoType >:Public Member Functions | |
| StandardPool (Master *master, int size, bool autoRealloc=false) | |
| Creates an empty pool. | |
| virtual | ~StandardPool () |
| The destructor. | |
| int | cleanup () |
| Cleans-up the pool. | |
| virtual void | increase (int size) |
| Enlarges the pool to store up to size items. | |
| virtual PoolSlot< BaseType, CoType > * | insert (BaseType *cv) |
| Tries to insert a constraint/variable in the pool. | |
| virtual int | separate (double *x, Active< CoType, BaseType > *active, Sub *sub, CutBuffer< BaseType, CoType > *cutBuffer, double minAbsViolation=0.001, int ranking=0) |
| Checks if a pair of a vector and an active constraint/variable set violates any item in the pool. | |
| int | size () const |
| Return the maximal number of constraints/variables that can be inserted in the pool. | |
| PoolSlot< BaseType, CoType > * | slot (int i) |
| Returns a pointer to the i-th slot in the pool. | |
| Public Member Functions inherited from abacus::Pool< BaseType, CoType > | |
| Pool (Master *master) | |
| Initializes an empty pool. | |
| virtual | ~Pool () |
| int | number () const |
| Returns the current number of items in the pool. | |
| void | removeConVar (PoolSlot< BaseType, CoType > *slot) |
| Removes the constraint/variable stored in a pool slot and adds the slot to the list of free slots. | |
| Public Member Functions inherited from abacus::AbacusRoot | |
| virtual | ~AbacusRoot () |
| The destructor. | |
Protected Member Functions | |
| virtual PoolSlot< BaseType, CoType > * | getSlot () |
| Returns a free slot, or 0 if no free slot is available. | |
| virtual void | putSlot (PoolSlot< BaseType, CoType > *slot) |
| Inserts the slot in the list of free slots. | |
| int | removeNonActive (int maxRemove) |
| Tries to remove at most maxRemove inactive items from the pool. | |
| Protected Member Functions inherited from abacus::Pool< BaseType, CoType > | |
| virtual void | hardDeleteConVar (PoolSlot< BaseType, CoType > *slot) |
| Removes a constraint/variable from the pool and adds the slot to the set of free slots. | |
| virtual int | softDeleteConVar (PoolSlot< BaseType, CoType > *slot) |
| Removes the constraint/variable stored in slot from the pool if it can be deleted. | |
Protected Attributes | |
| bool | autoRealloc_ |
| If the pool becomes full and this member is true, then an automatic reallocation is performed. | |
| ogdf::SListPure< PoolSlot< BaseType, CoType > * > | freeSlots_ |
| The linked lists of unused slots. | |
| Array< PoolSlot< BaseType, CoType > * > | pool_ |
| The array with the pool slots. | |
| Protected Attributes inherited from abacus::Pool< BaseType, CoType > | |
| Master * | master_ |
| A pointer to the corresponding master of the optimization. | |
| int | number_ |
| The current number of constraints in the pool. | |
Private Member Functions | |
| StandardPool (const StandardPool &rhs) | |
| const StandardPool & | operator= (const StandardPool &rhs) |
Friends | |
| std::ostream & | operator<< (std::ostream &out, const StandardPool &rhs) |
| Output operator for standard pools. | |
Additional Inherited Members | |
| Public Types inherited from abacus::Pool< BaseType, CoType > | |
| enum | RANKING { NO_RANK , RANK , ABS_RANK } |
| Determines how th rank of a constraint/variable is computed. More... | |
| Static Public Member Functions inherited from abacus::AbacusRoot | |
| static bool | ascii2bool (const string &str) |
| Converts the string str to a boolean value. | |
| static bool | endsWith (const string &str, const string &end) |
| Returns true if str ends with end, false otherwise. | |
| static double | fracPart (double x) |
| Returns the absolute value of the fractional part of x. | |
| static const char * | onOff (bool value) |
| Converts a boolean variable to the strings "on" and "off". | |
Standard pools.
This class is derived from the class Pool and provides a very simple implementation of a pool which is sufficient for a large class of applications. The pool slots are stored in an array and the set of free slots is managed by a linear list.
A standard pool can be static or dynamic. A static standard pool has a fixed size, whereas a dynamic standard pool is automatically enlarged by ten percent if it is full and an item is inserted.
Definition at line 57 of file standardpool.h.
| abacus::StandardPool< BaseType, CoType >::StandardPool | ( | Master * | master, |
| int | size, | ||
| bool | autoRealloc = false |
||
| ) |
Creates an empty pool.
All slots are inserted in the linked list of free slots.
| master | A pointer to the corresponding master of the optimization. |
| size | The maximal number of items which can be inserted in the pool without reallocation. |
| autoRealloc | If this argument is true an automatic reallocation is performed if the pool is full. |
|
virtual |
The destructor.
Deletes all slots. The destructor of a pool slot deletes then also the respective constraint or variable.
|
private |
Cleans-up the pool.
Scans the pool, removes all deletable items, i.e., those items without having references, and adds the corresponding slots to the list of free slots.
|
inlineprotectedvirtual |
Returns a free slot, or 0 if no free slot is available.
A returned slot is removed from the list of free slots.
This function defines the pure virtual function of the base class Pool.
Implements abacus::Pool< BaseType, CoType >.
Definition at line 180 of file standardpool.h.
Enlarges the pool to store up to size items.
To avoid fatal errors we do not allow decreasing the size of the pool.
| size | The new size of the pool. |
Reimplemented in abacus::NonDuplPool< BaseType, CoType >, and abacus::NonDuplPool< abacus::Constraint, abacus::Variable >.
|
virtual |
Tries to insert a constraint/variable in the pool.
If there is no free slot available, we try to generate free slots by removing redundant items, i.e., items which have no reference to them. If this fails, we either perform an automatic reallocation of the pool or remove non-active items.
| cv | The constraint/variable being inserted. |
Implements abacus::Pool< BaseType, CoType >.
Reimplemented in abacus::NonDuplPool< BaseType, CoType >.
|
private |
|
inlineprotectedvirtual |
Inserts the slot in the list of free slots.
It is an error to insert a slot which is not empty.
This function defines the pure virtual function of the base class Pool.
Implements abacus::Pool< BaseType, CoType >.
Definition at line 190 of file standardpool.h.
|
protected |
Tries to remove at most maxRemove inactive items from the pool.
A minimum heap of the items with the reference counter as key is built up and items are removed in this order.
|
virtual |
Checks if a pair of a vector and an active constraint/variable set violates any item in the pool.
If the pool is a constraint pool, then the vector is an LP-solution and the active set the set of active variables. Otherwise, if the pool is a variable pool, then the vector stores the values of the dual variables and the active set the associated active constraints.
Before a constraint or variable is generated we check if it is valid for the subproblem sub.
The function defines the pure virtual function of the base class Pool.
This is a very simple version of the pool separation. Future versions might scan a priority queue of the available constraints until a limited number of constraints is tested or separated.
| x | The vector for which violation is checked. |
| active | The constraint/variable set associated with z. |
| sub | The subproblem for which validity of the violated item is required. |
| cutBuffer | The violated constraints/variables are added to this buffer. |
| minAbsViolation | A violated constraint/variable is only added to the cutBuffer if the absolute value of its violation is at least minAbsViolation. The default value is 0.001. |
| ranking | If 1, the violation is associated with a rank of item in the buffer, if 2 the absolute violation is used, if 3 the function ConVar::rank() is used, if 0 no rank is associated with the item. |
Implements abacus::Pool< BaseType, CoType >.
|
inline |
Return the maximal number of constraints/variables that can be inserted in the pool.
Definition at line 121 of file standardpool.h.
Returns a pointer to the i-th slot in the pool.
| i | The number of the slot being accessed. |
Definition at line 127 of file standardpool.h.
|
friend |
Output operator for standard pools.
The output operator calls the output operator of each item of a non-void pool slot.
| out | The output stream. |
| rhs | The pool being output. |
|
protected |
If the pool becomes full and this member is true, then an automatic reallocation is performed.
Definition at line 204 of file standardpool.h.
|
protected |
The linked lists of unused slots.
Definition at line 199 of file standardpool.h.
The array with the pool slots.
Definition at line 198 of file standardpool.h.
