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 StandardPool &	operator= (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

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.

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

size	The 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

cv	The 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

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.

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

i	The 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

out	The output stream.
rhs	The 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:

include/ogdf/lib/abacus/convar.h
include/ogdf/lib/abacus/standardpool.h

OpenGraph DrawingFramework

Public Member Functions

Protected Member Functions

Protected Attributes

Private Member Functions

Friends

Detailed Description

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

Constructor & Destructor Documentation

◆ StandardPool() [1/2]

◆ ~StandardPool()

◆ StandardPool() [2/2]

Member Function Documentation

◆ cleanup()

◆ getSlot()

◆ increase()

◆ insert()

◆ operator=()

◆ putSlot()

◆ removeNonActive()

◆ separate()

◆ size()

◆ slot()

Friends And Related Function Documentation

◆ operator<<

Member Data Documentation

◆ autoRealloc_

◆ freeSlots_

◆ pool_

Open
Graph Drawing
Framework

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