Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

abacus::ConVar Class Reference

Common base class for constraints (Constraint) and variables (Variable). More...

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

+ Inheritance diagram for abacus::ConVar:

Public Member Functions

 ConVar (Master *master, const Sub *sub, bool dynamic, bool local)
 Creates an instance of type ConVar. More...
 
virtual ~ConVar ()
 
bool active () const
 Checks if the constraint/variable is active in at least one active subproblem. More...
 
virtual bool dynamic () const
 Return true if the constraint/variable is dynamic. More...
 
bool global () const
 Returns true if the constraint/variable is globally valid, false otherwise. More...
 
bool local () const
 Returns true if the constraint/variable is only locally valid, false otherwise. More...
 
- Public Member Functions inherited from abacus::AbacusRoot
virtual ~AbacusRoot ()
 The destructor. More...
 

Private Member Functions

Locking

If a constraint/variable has just been separated and added to the buffer of currently separated constraints/variables, then this item should not be removed before the buffer is emptied at the beginning of the next iteration.

Hence, we provide a locking mechanism for constraints/variables by the following three functions.

bool locked () const
 Returns true if at least one lock is set on the constraint/variable, false otherwise. More...
 
void lock ()
 Adds an additional lock to the constraint/variable. More...
 
void unlock ()
 Removes one lock from the constraint/variable. More...
 

Friends

class CutBuffer< Constraint, Variable >
 
class CutBuffer< Variable, Constraint >
 
class PoolSlot< Constraint, Variable >
 
class PoolSlot< Variable, Constraint >
 
class PoolSlotRef< Constraint, Variable >
 
class PoolSlotRef< Variable, Constraint >
 
class StandardPool< Constraint, Variable >
 
class StandardPool< Variable, Constraint >
 
class Sub
 

Expand and Compress

Constraints/Variables often have to be stored in a format different from the format used in the linear program.

One reason is to save memory and the other reason is that if constraints and/or variable sets are dynamic, then we require a format to compute the coefficients of later activated variables/constraints.

The disadvantage of such a constraint format is that the computation of a single constraint coefficient can be very time consuming. Often it cannot be done in constant time. Hence we provide a mechanism which converts a constraint/variable to a format enabling efficient computation of coefficients. The following functions provide this feature.

Mastermaster_
 A pointer to the corresponding master of the optimization. More...
 
const Subsub_
 A pointer to the subproblem associated with the constraint/variable. More...
 
bool expanded_
 true, if expanded version of constraint/variables available. More...
 
int nReferences_
 The number of references to the pool slot the constraint is stored in. More...
 
bool dynamic_
 If this member is true then the constraint/variable can be also removed from the active formulation after it is added the first time. More...
 
int nActive_
 The number of active subproblems of which the constraint/variable belongs to the set of active constraints/variables. More...
 
int nLocks_
 The number of locks which have been set on the constraint/variable. More...
 
bool local_
 true if the constraint/variable is only locally valid More...
 
bool expanded () const
 Returns true if the expanded format of a constraint/variable is available, false otherwise. More...
 
virtual void expand () const
 Expands a constraint/variable. More...
 
virtual void compress () const
 Compresses a constraint/variable. More...
 
virtual bool deletable () const
 Returns true if the constraint/variable can be destructed. More...
 
virtual void print (std::ostream &out) const
 Writes the constraint/variable to the output stream out. More...
 
const Subsub () const
 Returns a const pointer to the subproblem associated with the constraint/variable. More...
 
void sub (Sub *sub)
 Associates a new subproblem with the constraint/variable. More...
 
virtual unsigned hashKey () const
 Should provide a key for the constraint/variable that can be used to insert it into a hash table. More...
 
virtual const char * name () const
 Should return the name of the constraint/variable. More...
 
virtual bool equal (const ConVar *cv) const
 Should compare if the constraint/variable is identical (in a mathematical sense) with the constraint/variable cv. More...
 
virtual double rank () const
 The function should return a rank associated with the constraint/variable. More...
 
void _expand () const
 Tries to generate the expanded format of the constraint/variable. More...
 
void _compress () const
 Removes the expanded format of the constraint/variable. More...
 
void activate ()
 Must be called if the constraint/variable is added to the active formulation of an active subproblem. More...
 
void deactivate ()
 Counterpart of activate(). More...
 
int nReferences () const
 Returns the number of references to the pool slot PoolSlotRef storing this constraint/variable. More...
 
void addReference ()
 Indicates that there is a new reference to the pool slot storing this constraint/variable. More...
 
void removeReference ()
 Is the counterpart of the function addReference() and indicates the removal of a reference to this constraint. More...
 

Additional Inherited Members

- Static Public Member Functions inherited from abacus::AbacusRoot
static bool ascii2bool (const string &str)
 Converts the string str to a boolean value. More...
 
static bool endsWith (const string &str, const string &end)
 Returns true if str ends with end, false otherwise. More...
 
static double fracPart (double x)
 Returns the absolute value of the fractional part of x. More...
 
static const char * onOff (bool value)
 Converts a boolean variable to the strings "on" and "off". More...
 

Detailed Description

Common base class for constraints (Constraint) and variables (Variable).

ConVar is the common base class for constraints and variables, which are implemented in the derived classes Constraint and Variable, respectively. It might seem a bit strange to implement a common base class for these two objects. Besides several technical reasons, there is linear programming duality which motivates this point of view. E.g., the separation problem for the primal problem is equivalent to the pricing problem for the dual problem.

ConVar is not the base class for constraints and variables as they are used in the interface to the linear programming solver. There are the classes Row and Column for this purpose. ConVar is the father of a class hierarchy for abstract constraints and variables which are used in the branch-and-bound algorithm.

Definition at line 65 of file convar.h.

Constructor & Destructor Documentation

◆ ConVar()

abacus::ConVar::ConVar ( Master master,
const Sub sub,
bool  dynamic,
bool  local 
)
inline

Creates an instance of type ConVar.

Parameters
masterA pointer to the corresponding master of the optimization.
subA pointer the subproblem the constraint/variable is associated with. If the item is not associated with any subproblem, then this can also be the 0-pointer.
dynamicIf this paramument is true, then the constraint/variable can also be removed again from the set of active constraints/variables after it is added once.
localIf local is true, then the constraint/variable is only locally valid.

Definition at line 91 of file convar.h.

◆ ~ConVar()

abacus::ConVar::~ConVar ( )
inlinevirtual

Definition at line 393 of file convar.h.

Member Function Documentation

◆ _compress()

void abacus::ConVar::_compress ( ) const
private

Removes the expanded format of the constraint/variable.

This will be only possible if the virtual function compress() is redefined for the specific constraint/variable.

◆ _expand()

void abacus::ConVar::_expand ( ) const
private

Tries to generate the expanded format of the constraint/variable.

This will be only possible if the virtual function expand() is redefined for the specific constraint/variable.

◆ activate()

void abacus::ConVar::activate ( )
inlineprivate

Must be called if the constraint/variable is added to the active formulation of an active subproblem.

This function is only called within member functions of the class Sub.

Definition at line 335 of file convar.h.

◆ active()

bool abacus::ConVar::active ( ) const
inline

Checks if the constraint/variable is active in at least one active subproblem.

Returns
true if the constraint/variable is active, false otherwise.

Definition at line 109 of file convar.h.

◆ addReference()

void abacus::ConVar::addReference ( )
inlineprivate

Indicates that there is a new reference to the pool slot storing this constraint/variable.

The function is only called from members of the class PoolSlotRef.

Definition at line 358 of file convar.h.

◆ compress()

virtual void abacus::ConVar::compress ( ) const
inlinevirtual

Compresses a constraint/variable.

The default implementation does nothing. It should be redefined in derived classes. Attention: Data that is compacted/compressed needs to be marked as mutable, as this function is supposed to be applicable for const objects! Compressing/expanding is NOT expected to change the "outer" status of this class, and compression/expansion is done automatically on the fly on an as-needed basis.

Definition at line 167 of file convar.h.

◆ deactivate()

void abacus::ConVar::deactivate ( )
inlineprivate

Counterpart of activate().

Is also called within members of the class Sub to indicate that the constraint/variable does not belong any more to the active formulation of an active subproblem.

Definition at line 412 of file convar.h.

◆ deletable()

virtual bool abacus::ConVar::deletable ( ) const
inlinevirtual

Returns true if the constraint/variable can be destructed.

This is per default only possible if the reference counter is 0 and no lock is set. The function is declared virtual such that problem specific implementations are possible.

Definition at line 174 of file convar.h.

◆ dynamic()

virtual bool abacus::ConVar::dynamic ( ) const
inlinevirtual

Return true if the constraint/variable is dynamic.

Returns
true if the constraint/variable can be also removed from the set of active constraints/variables after it has been activated, false otherwise.

Definition at line 124 of file convar.h.

◆ equal()

virtual bool abacus::ConVar::equal ( const ConVar cv) const
virtual

Should compare if the constraint/variable is identical (in a mathematical sense) with the constraint/variable cv.

Using RTTI or its emulation provided by the function name() it is sufficient to implement this functions for constraints/variables of the same type.

This function is required if the constraint/variable is stored in a pool of the class NonDuplPool.

The default implementation shows a warning and throws an exception. This function is not a pure virtual function because in the default version of ABACUS it is not required.

Parameters
cvThe constraint/variable that should be compared with this object.
Returns
true If the constraint/variable represented by this object represents the same item as the constraint/variable cv, false otherwise.

◆ expand()

virtual void abacus::ConVar::expand ( ) const
inlinevirtual

Expands a constraint/variable.

The default implementation does nothing. It should be redefined in derived classes. Attention: Data that is compacted/compressed needs to be marked as mutable, as this function is supposed to be applicable for const objects! Compressing/expanding is NOT expected to change the "outer" status of this class, and compression/expansion is done automatically on the fly on an as-needed basis.

Definition at line 157 of file convar.h.

◆ expanded()

bool abacus::ConVar::expanded ( ) const
inline

Returns true if the expanded format of a constraint/variable is available, false otherwise.

Definition at line 146 of file convar.h.

◆ global()

bool abacus::ConVar::global ( ) const
inline

Returns true if the constraint/variable is globally valid, false otherwise.

Definition at line 116 of file convar.h.

◆ hashKey()

virtual unsigned abacus::ConVar::hashKey ( ) const
virtual

Should provide a key for the constraint/variable that can be used to insert it into a hash table.

As usual for hashing, it is not required that any two items have different keys.

This function is required if the constraint/variable is stored in a pool of the class NonDuplPool.

The default implementation just throws an exception. This function is not a pure virtual function because in the default version of ABACUS it is not required.

We do not use double as result type because typical problems in floating point arithmetic might give slightly different hash keys for two constraints that are equal from a mathematical point of view.

Returns
An integer providing a hash key for the constraint/variable.

Reimplemented in ogdf::MinSteinerTreeDirectedCut< T >::DirectedCutConstraint.

◆ local()

bool abacus::ConVar::local ( ) const
inline

Returns true if the constraint/variable is only locally valid, false otherwise.

Definition at line 113 of file convar.h.

◆ lock()

void abacus::ConVar::lock ( )
inlineprivate

Adds an additional lock to the constraint/variable.

Definition at line 383 of file convar.h.

◆ locked()

bool abacus::ConVar::locked ( ) const
inlineprivate

Returns true if at least one lock is set on the constraint/variable, false otherwise.

Definition at line 379 of file convar.h.

◆ name()

virtual const char* abacus::ConVar::name ( ) const
virtual

Should return the name of the constraint/variable.

This function is required to emulate a simple run time type information (RTTI) that is still missing in g++. This function will be removed as soon as RTTI is supported sufficiently.

A user must take care that for each redefined version of this function in a derived class a unique name is returned. Otherwise fatal run time errors can occur. Therefore, we recommend to return always the name of the class.

This function is required if the constraint/variable is stored in a pool of the class NonDuplPool.

The default implementation shows a warning and throws an exception. This function is not a pure virtual function because in the default version of ABACUS it is not required.

Returns
The name of the constraint/variable.

Reimplemented in ogdf::MinSteinerTreeDirectedCut< T >::DirectedCutConstraint.

◆ nReferences()

int abacus::ConVar::nReferences ( ) const
inlineprivate

Returns the number of references to the pool slot PoolSlotRef storing this constraint/variable.

We require the bookkeeping of the references in order to determine if a constraint/variable can be deleted without causing any harm.

Definition at line 351 of file convar.h.

◆ print()

virtual void abacus::ConVar::print ( std::ostream &  out) const
virtual

Writes the constraint/variable to the output stream out.

This function is used since the output operator cannot be declared virtual. The default implementation only writes "ConVar::print() is only a dummy.". We do not declare this function pure virtual since it is not really required, mainly only for debugging. In this case a constraint/variable specific redefinition is strongly recommended.

Normally, the implementation out << *this should be sufficient.

Parameters
outThe output stream.

Reimplemented in abacus::RowCon, abacus::ColVar, and abacus::NumCon.

◆ rank()

virtual double abacus::ConVar::rank ( ) const
inlinevirtual

The function should return a rank associated with the constraint/variable.

The default implementation returns 0.

Returns
The rank of the constraint/variable.

Definition at line 279 of file convar.h.

◆ removeReference()

void abacus::ConVar::removeReference ( )
inlineprivate

Is the counterpart of the function addReference() and indicates the removal of a reference to this constraint.

It is only called from members of the class PoolSlotRef.

Definition at line 419 of file convar.h.

◆ sub() [1/2]

const Sub* abacus::ConVar::sub ( ) const
inline

Returns a const pointer to the subproblem associated with the constraint/variable.

Note, this can also be the 0-pointer.

Definition at line 199 of file convar.h.

◆ sub() [2/2]

void abacus::ConVar::sub ( Sub sub)
inline

Associates a new subproblem with the constraint/variable.

Parameters
subThe new subproblem associated with the constraint/variable.

Definition at line 206 of file convar.h.

◆ unlock()

void abacus::ConVar::unlock ( )
inlineprivate

Removes one lock from the constraint/variable.

Definition at line 428 of file convar.h.

Friends And Related Function Documentation

◆ CutBuffer< Constraint, Variable >

friend class CutBuffer< Constraint, Variable >
friend

Definition at line 73 of file convar.h.

◆ CutBuffer< Variable, Constraint >

friend class CutBuffer< Variable, Constraint >
friend

Definition at line 74 of file convar.h.

◆ PoolSlot< Constraint, Variable >

friend class PoolSlot< Constraint, Variable >
friend

Definition at line 67 of file convar.h.

◆ PoolSlot< Variable, Constraint >

friend class PoolSlot< Variable, Constraint >
friend

Definition at line 68 of file convar.h.

◆ PoolSlotRef< Constraint, Variable >

friend class PoolSlotRef< Constraint, Variable >
friend

Definition at line 69 of file convar.h.

◆ PoolSlotRef< Variable, Constraint >

friend class PoolSlotRef< Variable, Constraint >
friend

Definition at line 70 of file convar.h.

◆ StandardPool< Constraint, Variable >

friend class StandardPool< Constraint, Variable >
friend

Definition at line 71 of file convar.h.

◆ StandardPool< Variable, Constraint >

friend class StandardPool< Variable, Constraint >
friend

Definition at line 72 of file convar.h.

◆ Sub

friend class Sub
friend

Definition at line 75 of file convar.h.

Member Data Documentation

◆ dynamic_

bool abacus::ConVar::dynamic_
protected

If this member is true then the constraint/variable can be also removed from the active formulation after it is added the first time.

For constraints/variables which should be never removed from the active formulation this member should be set to false.

Definition at line 300 of file convar.h.

◆ expanded_

bool abacus::ConVar::expanded_
mutableprotected

true, if expanded version of constraint/variables available.

[mutable in const-objects to allow compress/expand on const]

Definition at line 291 of file convar.h.

◆ local_

bool abacus::ConVar::local_
protected

true if the constraint/variable is only locally valid

Definition at line 312 of file convar.h.

◆ master_

Master* abacus::ConVar::master_
protected

A pointer to the corresponding master of the optimization.

Definition at line 283 of file convar.h.

◆ nActive_

int abacus::ConVar::nActive_
protected

The number of active subproblems of which the constraint/variable belongs to the set of active constraints/variables.

This value is always 0 after construction and has to be set and reset during the subproblem optimization. This member is mainly used to accelerate pool separation and to control that the same variable is not multiply included into a set of active variables.

Definition at line 308 of file convar.h.

◆ nLocks_

int abacus::ConVar::nLocks_
protected

The number of locks which have been set on the constraint/variable.

Definition at line 310 of file convar.h.

◆ nReferences_

int abacus::ConVar::nReferences_
protected

The number of references to the pool slot the constraint is stored in.

Definition at line 293 of file convar.h.

◆ sub_

const Sub* abacus::ConVar::sub_
protected

A pointer to the subproblem associated with the constraint/variable.

This may be also the 0-pointer.

Definition at line 289 of file convar.h.


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