cs

Introduction

The Constraint System base class.

Discussion

Other derived constraint systems inherit the functionality of this class. It implements the entailment, meet, join and implication operators. It heavily relies on the boost graph implementation.

Member Functions

add_element

Adds an element to the CS where lower ⊑ elem ⊑ upper.

bound

Calculates either GLB( elems ) or LUB( elems ).

cs(const cs &)

Copy Constructor.

cs(ELEM_TYPE, ELEM_TYPE)

Constructor.

glb

Calculates GLB( elems )

imp

Calculates the element elem1 → elem2 in the CS.

is_distributive

Checks if the lattice is distributive.

leq

Tests if elem1 ⊑ elem2.

lub

Calculates LUB( elems )

p_getElementNum

Retrives the identifier of an element in the constraint system.

print_cons

Prints (on the standard output) the elements of the CS along with its identifier (in parenthesis).

print_relation

Prints (on the standard output) the ordering relation or its inverse.

~cs

Destructor.

add_element

Adds an element to the CS where lower ⊑ elem ⊑ upper.

public

void add_element(
    ELEM_TYPE elem,
    const std::vector<ELEM_TYPE>& lower = std::vector<ELEM_TYPE>(),
    const std::vector<ELEM_TYPE>& upper = std::vector<ELEM_TYPE>() ); 

Parameters

Discussion

This function adds an element to the constraint system where the set of elements lower is directly related to the element and the element itself is related to the set of elements upper. It performs a transitive closure on the ordering relation for complexity advantages in the operators of the CS.

Complexity

O(n³) where n is the number of elements in the CS.

bound

Calculates either GLB( elems ) or LUB( elems ).

protected

ELEM_TYPE bound(
    const std::set<t_elem>& elems,
    bool lower ); 

Parameters

Return Value

calculated bound.

Complexity

O(n²) where n is the number of elements of the CS.

cs(const cs &)

Copy Constructor.

public

cs (
    const cs<ELEM_TYPE>& CS ); 

Parameters

Complexity

Constant.

cs(ELEM_TYPE, ELEM_TYPE)

Constructor.

public

cs (
    ELEM_TYPE bottom,
    ELEM_TYPE top ); 

Parameters

Complexity

Constant.

glb

Calculates GLB( elems )

public

ELEM_TYPE glb(
    const std::vector<ELEM_TYPE>& elems = std::vector<ELEM_TYPE>() ); 

Parameters

Return Value

⨅(elems). If elems = ∅, the result is ⊥.

Complexity

Same as bound.

imp

Calculates the element elem1 → elem2 in the CS.

public

ELEM_TYPE imp(
    ELEM_TYPE elem1,
    ELEM_TYPE elem2 ); 

Parameters

Return Value

elem1 → elem2.

Discussion

The definition of implication used here is the Heyting implication defined as c → d = ⨅{ e | c ⨆ e ⊒ d }. If d = ⊤ the result of the implication is ~c.

Complexity

O(n³) where n is the number of elements of the CS.

is_distributive

Checks if the lattice is distributive.

public

bool is_distributive(
    void ); 

Return Value

true if the lattice is distributive and false otherwise.

Discussion

A lattice is distributive iff for all elements a, b and c the following holds; a ⨆ (b ⨅ c) = (a ⨆ b) ⨅ (a ⨆ c). Distributivity is necessary for modus ponens (i.e. c ⨆ (c → d) ⊒ d).

Complexity

O(n³) where n is the number of elements of the CS.

leq

Tests if elem1 ⊑ elem2.

public

bool leq(
    ELEM_TYPE elem1,
    ELEM_TYPE elem2 ); 

Parameters

Return Value

true if elem1 ⊑ elem2, false otherwise.

Complexity

Constant.

lub

Calculates LUB( elems )

public

ELEM_TYPE lub(
    const std::vector<ELEM_TYPE>& elems = std::vector<ELEM_TYPE>() ); 

Parameters

Return Value

⨆(elems). If elems = ∅, the result is ⊤.

Complexity

Same as bound.

p_getElementNum

Retrives the identifier of an element in the constraint system.

protected

int p_getElementNum(
    ELEM_TYPE elem ); 

Parameters

Return Value

element's identifier, negative if not found.

Complexity

O(n) where n is the number of elements of the CS.

print_cons

Prints (on the standard output) the elements of the CS along with its identifier (in parenthesis).

public

void print_cons(
    const std::function<void(
            ELEM_TYPE)>& printer ); 

Complexity

O(n) where n is the number of elements of the CS.

printer

a process that takes one element of the CS and prints it. it is mean to be passed as a parameter.

print_relation

Prints (on the standard output) the ordering relation or its inverse.

public

void print_relation(
    bool inverse = false ); 

Parameters

Complexity

O(n²) where n is the number of elements of the CS.

~cs

Destructor.

public

~cs (
    void ); 

Complexity

Constant.

Typedefs

t_elem

t_relation

t_elem

protected

typedef typename boost::graph_traits<t_relation>::vertex_descriptor t_elem; 

Discussion

Type for the identifiers of the elements in the constraint system. Currently, it is equivalent to int.

t_relation

protected

typedef typename boost::adjacency_list< boost::listS, boost::vecS, boost::bidirectionalS, boost::property<boost::vertex_name_t, ELEM_TYPE> > t_relation; 

Discussion

Type for the ordering relation. Basically it is a graph representing the ordering relation's transitive closure.

See Also

Member Data

m_cons

m_rel

m_cons

protected

std::deque<ELEM_TYPE>* m_cons; 

Discussion

Queue of the elements of the constraint system.

m_rel

protected

t_relation* m_rel; 

Discussion

Graph representing the ordering relation.