Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

abacus::StandardPool< BaseType, CoType > Class Template Reference

Standard pools. More...

#include <ogdf/lib/abacus/convar.h>

+ Inheritance diagram for abacus::StandardPool< BaseType, CoType >:

Public Member Functions

 StandardPool (Master *master, int size, bool autoRealloc=false)
 Creates an empty pool. More...
 
virtual ~StandardPool ()
 The destructor. More...
 
int cleanup ()
 Cleans-up the pool. More...
 
virtual void increase (int size)
 Enlarges the pool to store up to size items. More...
 
virtual PoolSlot< BaseType, CoType > * insert (BaseType *cv)
 Tries to insert a constraint/variable in the pool. More...
 
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. More...
 
int size () const
 Return the maximal number of constraints/variables that can be inserted in the pool. More...
 
PoolSlot< BaseType, CoType > * slot (int i)
 Returns a pointer to the i-th slot in the pool. More...
 

Protected Member Functions

virtual PoolSlot< BaseType, CoType > * getSlot ()
 Returns a free slot, or 0 if no free slot is available. More...
 
virtual void putSlot (PoolSlot< BaseType, CoType > *slot)
 Inserts the slot in the list of free slots. More...
 
int removeNonActive (int maxRemove)
 Tries to remove at most maxRemove inactive items from the pool. More...
 

Protected Attributes

bool autoRealloc_
 If the pool becomes full and this member is true, then an automatic reallocation is performed. More...
 
ogdf::SListPure< PoolSlot< BaseType, CoType > * > freeSlots_
 The linked lists of unused slots. More...
 
Array< PoolSlot< BaseType, CoType > * > pool_
 The array with the pool slots. More...
 

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. More...
 

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 44 of file convar.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()

template<class BaseType , class CoType >
virtual abacus::StandardPool< BaseType, CoType >::~StandardPool ( )
virtual

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()

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

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()

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

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.

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

◆ operator=()

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

◆ 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.

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.

◆ 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()

template<class BaseType , class CoType >
PoolSlot<BaseType,CoType>* abacus::StandardPool< BaseType, CoType >::slot ( int  i)
inline

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 Function 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_

template<class BaseType , class CoType >
ogdf::SListPure<PoolSlot<BaseType,CoType> *> abacus::StandardPool< BaseType, CoType >::freeSlots_
protected

The linked lists of unused slots.

Definition at line 199 of file standardpool.h.

◆ pool_

template<class BaseType , class CoType >
Array<PoolSlot<BaseType,CoType> *> abacus::StandardPool< BaseType, CoType >::pool_
protected

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: