Standard pools without constraint duplication. More...

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

Inheritance diagram for abacus::NonDuplPool< BaseType, CoType >:

Public Member Functions
	NonDuplPool (Master *master, int size, bool autoRealloc=false)
	Creates an empty pool.

virtual	~NonDuplPool ()
	The destructor.

virtual void	increase (int size)
	Enlarges the pool to store up to size items.

virtual PoolSlot< BaseType, CoType > *	insert (BaseType *cv)
	Insert constraint/variable cv in the pool.

virtual PoolSlot< BaseType, CoType > *	present (BaseType *cv)
	Checks if constraint/variables cv is already contained in the pool.

virtual const PoolSlot< BaseType, CoType > *	present (const BaseType *cv) const
	Checks if constraint/variables cv is already contained in the pool.

void	statistics (int &nDuplications, int &nCollisions) const
	Returns some statistic information in nDuplicates and nCollisions.

Public Member Functions inherited from abacus::StandardPool< BaseType, CoType >
	StandardPool (Master *master, int size, bool autoRealloc=false)
	Creates an empty pool.

virtual	~StandardPool ()
	The destructor.

int	cleanup ()
	Cleans-up 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.

Private Member Functions
	NonDuplPool (const NonDuplPool &rhs)

virtual void	hardDeleteConVar (PoolSlot< BaseType, CoType > *slot)
	Has to be redefined because the pool slot has to be removed from the hash table.

const NonDuplPool &	operator= (const NonDuplPool &rhs)

virtual int	softDeleteConVar (PoolSlot< BaseType, CoType > *slot)
	Has to be redefined because the slot has to be removed from the hash table if the constraint/variable can be deleted.

Private Attributes
AbaHash< unsigned, PoolSlot< BaseType, CoType > * >	hash_
	A hash table for a fast access to the pool slot storing a constraint/variable.

int	nDuplications_
	The number of insertions of constraints/variables that were rejected since the constraint/variable is stored already in the pool.

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

Protected Member Functions inherited from abacus::StandardPool< BaseType, CoType >
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 Attributes inherited from abacus::StandardPool< BaseType, CoType >
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.

Detailed Description

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

Standard pools without constraint duplication.

The class NonDuplPool provides an StandardPool with the additional feature that the same constraint is at most stored once in the pool. For constraints and variables inserted in this pool the virtual member functions name(), hashKey(), and equal() of the base class ConVar have to be defined. Using these three functions, we check at insertation time if a constraint or variable is already stored in the pool.

The implementation is unsafe in the sense that the data structure for registering a constraint is corrupted if a constraint is removed directly from the pool slot without using a function of this class.

Definition at line 58 of file nonduplpool.h.

Constructor & Destructor Documentation

◆ NonDuplPool() [1/2]

template<class BaseType , class CoType >

abacus::NonDuplPool< BaseType, CoType >::NonDuplPool	(	Master *	master,
		int	size,
		bool	autoRealloc = `false`
	)

inline

Creates an empty pool.

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.

Definition at line 69 of file nonduplpool.h.

◆ ~NonDuplPool()

template<class BaseType , class CoType >

virtual abacus::NonDuplPool< BaseType, CoType >::~NonDuplPool ( )

inlinevirtual

The destructor.

Definition at line 74 of file nonduplpool.h.

◆ NonDuplPool() [2/2]

template<class BaseType , class CoType >

abacus::NonDuplPool< BaseType, CoType >::NonDuplPool ( const NonDuplPool< BaseType, CoType > & rhs )

private

Member Function Documentation

◆ hardDeleteConVar()

template<class BaseType , class CoType >

virtual void abacus::NonDuplPool< BaseType, CoType >::hardDeleteConVar ( PoolSlot< BaseType, CoType > * slot )

privatevirtual

Has to be redefined because the pool slot has to be removed from the hash table.

Parameters

slot	A pointer to the pool slot from wich the constraint/variable should be deleted.

Reimplemented from abacus::Pool< BaseType, CoType >.

◆ increase()

template<class BaseType , class CoType >

virtual void abacus::NonDuplPool< BaseType, CoType >::increase ( int size )

inlinevirtual

Enlarges the pool to store up to size items.

To avoid fatal errors we do not allow decreasing the size of the pool. This function redefines the virtual function of the base class StandardPool because we have to reallocate the hash table.

Parameters

size	The new size of the pool.

Reimplemented from abacus::StandardPool< BaseType, CoType >.

Definition at line 125 of file nonduplpool.h.

◆ insert()

template<class BaseType , class CoType >

virtual PoolSlot< BaseType, CoType > * abacus::NonDuplPool< BaseType, CoType >::insert ( BaseType * cv )

virtual

Insert constraint/variable cv in the pool.

Before the function insert() tries to insert a constraint/variable in the pool, it checks if the constraint/variable is already contained in the pool. If the constraint/variable cv is contained in the pool, it is deleted.

Parameters

cv	The constraint/variable being inserted.

Returns: A pointer to the pool slot where the item has been inserted, or a pointer to the pool slot if the item is already contained in the pool, or 0 if the insertion failed.

Reimplemented from abacus::StandardPool< BaseType, CoType >.

◆ operator=()

template<class BaseType , class CoType >

const NonDuplPool & abacus::NonDuplPool< BaseType, CoType >::operator= ( const NonDuplPool< BaseType, CoType > & rhs )

private

◆ present() [1/2]

template<class BaseType , class CoType >

virtual PoolSlot< BaseType, CoType > * abacus::NonDuplPool< BaseType, CoType >::present ( BaseType * cv )

virtual

Checks if constraint/variables cv is already contained in the pool.

Parameters

cv	A pointer to a constraint/variable for which it should be checked if an equivalent item is already contained in the pool.

Returns: A pointer to the pool slot storing a constraint/variable that is equivalent to cv according to the function ConVar::equal(). If there is no such constraint/variable 0 is returned.

◆ present() [2/2]

template<class BaseType , class CoType >

virtual const PoolSlot< BaseType, CoType > * abacus::NonDuplPool< BaseType, CoType >::present ( const BaseType * cv ) const

virtual

Checks if constraint/variables cv is already contained in the pool.

Parameters

cv	A (const) pointer to a constraint/variable for which it should be checked if an equivalent item is already contained in the pool.

Returns: A const pointer to the pool slot storing a constraint/variable that is equivalent to cv according to the function ConVar::equal(). If there is no such constraint/variable 0 is returned.

◆ softDeleteConVar()

template<class BaseType , class CoType >

virtual int abacus::NonDuplPool< BaseType, CoType >::softDeleteConVar ( PoolSlot< BaseType, CoType > * slot )

privatevirtual

Has to be redefined because the slot has to be removed from the hash table if the constraint/variable can be deleted.

Returns: 0 If the constraint/variable could be deleted, 1 otherwise.

Parameters

slot	A pointer to the pool slot from wich the constraint/variable should be deleted.

Reimplemented from abacus::Pool< BaseType, CoType >.

◆ statistics()

template<class BaseType , class CoType >

void abacus::NonDuplPool< BaseType, CoType >::statistics	(	int &	nDuplications,
		int &	nCollisions
	)		const

inline

Returns some statistic information in nDuplicates and nCollisions.

Determines the number of constraints that have not been inserted into the pool, because an equivalent was already present.

Also the number of collisions in the hash table is computed. If this number is high, it might indicate that your hash function is not chosen very well.

Parameters

nDuplications	The number of constraints that have not been inserted into the pool because an equivalent one was already present.
nCollisions	The number of collisions in the hash table.

Definition at line 144 of file nonduplpool.h.

Member Data Documentation

◆ hash_

template<class BaseType , class CoType >

AbaHash<unsigned, PoolSlot<BaseType, CoType>*> abacus::NonDuplPool< BaseType, CoType >::hash_

private

A hash table for a fast access to the pool slot storing a constraint/variable.

Definition at line 171 of file nonduplpool.h.

◆ nDuplications_

template<class BaseType , class CoType >

int abacus::NonDuplPool< BaseType, CoType >::nDuplications_

private

The number of insertions of constraints/variables that were rejected since the constraint/variable is stored already in the pool.

Definition at line 175 of file nonduplpool.h.

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

include/ogdf/lib/abacus/nonduplpool.h

OpenGraph DrawingFramework

Public Member Functions

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ NonDuplPool() [1/2]

◆ ~NonDuplPool()

◆ NonDuplPool() [2/2]

Member Function Documentation

◆ hardDeleteConVar()

◆ increase()

◆ insert()

◆ operator=()

◆ present() [1/2]

◆ present() [2/2]

◆ softDeleteConVar()

◆ statistics()

Member Data Documentation

◆ hash_

◆ nDuplications_

Open
Graph Drawing
Framework