Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
abacus::StandardPool< BaseType, CoType > Class Template Reference

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 >
Mastermaster_
 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 StandardPooloperator= (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 charonOff (bool value)
 Converts a boolean variable to the strings "on" and "off".
 

Detailed Description

template<class BaseType, class CoType>
class abacus::StandardPool< BaseType, CoType >

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.

Constructor & Destructor Documentation

◆ StandardPool() [1/2]

template<class BaseType , class CoType >
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.

Parameters
masterA pointer to the corresponding master of the optimization.
sizeThe maximal number of items which can be inserted in the pool without reallocation.
autoReallocIf this argument is true an automatic reallocation is performed if the pool is full.

◆ ~StandardPool()

The destructor.

Deletes all slots. The destructor of a pool slot deletes then also the respective constraint or variable.

◆ StandardPool() [2/2]

template<class BaseType , class CoType >
abacus::StandardPool< BaseType, CoType >::StandardPool ( const StandardPool< BaseType, CoType > &  rhs)
private

Member Function Documentation

◆ cleanup()

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.

Returns
The number of "cleaned" slots.

◆ getSlot()

template<class BaseType , class CoType >
virtual PoolSlot< BaseType, CoType > * abacus::StandardPool< BaseType, CoType >::getSlot ( )
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.

◆ increase()

template<class BaseType , class CoType >
virtual void abacus::StandardPool< BaseType, CoType >::increase ( int  size)
virtual

Enlarges the pool to store up to size items.

To avoid fatal errors we do not allow decreasing the size of the pool.

Parameters
sizeThe new size of the pool.

Reimplemented in abacus::NonDuplPool< BaseType, CoType >, and abacus::NonDuplPool< abacus::Constraint, abacus::Variable >.

◆ insert()

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.

Parameters
cvThe constraint/variable being inserted.
Returns
A pointer to the pool slot where the item has been inserted, or 0 if the insertion failed.

Implements abacus::Pool< BaseType, CoType >.

Reimplemented in abacus::NonDuplPool< BaseType, CoType >.

◆ operator=()

◆ putSlot()

template<class BaseType , class CoType >
virtual void abacus::StandardPool< BaseType, CoType >::putSlot ( PoolSlot< BaseType, CoType > *  slot)
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.

◆ removeNonActive()

template<class BaseType , class CoType >
int abacus::StandardPool< BaseType, CoType >::removeNonActive ( int  maxRemove)
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.

◆ separate()

template<class BaseType , class CoType >
virtual int abacus::StandardPool< BaseType, CoType >::separate ( double x,
Active< CoType, BaseType > *  active,
Sub sub,
CutBuffer< BaseType, CoType > *  cutBuffer,
double  minAbsViolation = 0.001,
int  ranking = 0 
)
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.

Parameters
xThe vector for which violation is checked.
activeThe constraint/variable set associated with z.
subThe subproblem for which validity of the violated item is required.
cutBufferThe violated constraints/variables are added to this buffer.
minAbsViolationA 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.
rankingIf 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.
Returns
The number of violated items.

Implements abacus::Pool< BaseType, CoType >.

◆ size()

template<class BaseType , class CoType >
int abacus::StandardPool< BaseType, CoType >::size ( ) const
inline

Return the maximal number of constraints/variables that can be inserted in the pool.

Definition at line 121 of file standardpool.h.

◆ slot()

Returns a pointer to the i-th slot in the pool.

Parameters
iThe number of the slot being accessed.

Definition at line 127 of file standardpool.h.

Friends And Related Symbol Documentation

◆ operator<<

template<class BaseType , class CoType >
std::ostream & operator<< ( std::ostream &  out,
const StandardPool< BaseType, CoType > &  rhs 
)
friend

Output operator for standard pools.

The output operator calls the output operator of each item of a non-void pool slot.

Parameters
outThe output stream.
rhsThe pool being output.
Returns
A reference to the output stream.

Member Data Documentation

◆ autoRealloc_

template<class BaseType , class CoType >
bool abacus::StandardPool< BaseType, CoType >::autoRealloc_
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.

◆ freeSlots_

The linked lists of unused slots.

Definition at line 199 of file standardpool.h.

◆ pool_

The array with the pool slots.

Definition at line 198 of file standardpool.h.


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