Main Page | Namespace List | Class Hierarchy | Class List | File List | Namespace Members | Class Members | File Members

gbdd::BddRelation Class Reference

A relation implemented as BDD. More...

#include <bdd-relation.h>

Inheritance diagram for gbdd::BddRelation:

gbdd::SpecializedRelation< Bdd, BddRelation, BddSet > gbdd::StructureRelation gbdd::StructureBinaryView< Bdd, BddRelation, BddSet > gbdd::StructureSetView< Bdd, BddRelation, BddSet > gbdd::BddSet List of all members.

Public Types

typedef SpecializedRelation<
Bdd, BddRelation, BddSet
SpecT

Public Member Functions

 BddRelation ()
 Uninitialized constructor.

 BddRelation (const StructureRelation &r)
 Copy constructor.

 BddRelation (const Bdd::FiniteVars &vs, bool value=false)
 Constructor for empty relation.

 BddRelation (const Bdd::FiniteVars &vs, Bdd rel_bdd)
 Constructor.

 BddRelation (const Domains &ds, Bdd rel_bdd)
 Constructor.

 BddRelation (const Domains &ds, const BddRelation &r)
 Adapt domains with automatic renaming.

const Bddget_bdd () const
 Get BDD of relation.

 BddRelation (Space *space, unsigned int arity)
 Create empty relation.

Spaceget_space () const
 Get space of relation.

bool is_false () const
 Test for false.

bool is_true () const
 Test for true.

void insert (const vector< unsigned int > &vals)
 Inserts an element into the relation.

void insert (unsigned int v1, unsigned int v2)

Static Public Member Functions

BddRelation enumeration (vector< BddSet > &sets)
 Creates a membership relation for a vector of sets.

BddRelation enumeration (vector< BddSet > &sets, Domain dom_enum)
 Creates a membership relation for a vector of sets.

vector< BddRelationcolor (unsigned int domain_index, Domain color_domain, vector< BddRelation > rels)
 Color a vector of relations.


Friends

ostream & operator<< (ostream &out, const BddRelation &r)
 Print relation.


Detailed Description

A relation implemented as BDD.

A relation is a BDD with a vector of variables stating what variables in the BDD are used to implement what domain. The number of domains is equal to the arity of the relation.

The following code illustrates the class. It creates three relations. The relation rel1 is the set {(0,10),(2,10),(5,10)}, the relation rel2 the set {(0,10),(1,10),(2,10)}, and mapper the set {(0,0),(2,1),(5,2)}. Finally it checks that rel1 composed with mapper in the first component of rel1 gives rel2 as a result. Note also that mapper uses other variables than rel1 and rel2, the compose method takes care of the renaming for us.

Space *space = Space::create_default(); Domains domains1(2); domains1[0] = Domain(0, 5); domains1[1] = Domain(5, 5); Domains domains2(2); domains2[0] = Domain(3, 5); domains2[1] = Domain(9, 5); BddRelation rel1 = BddRelation(domains1, (Bdd::value(space, domains1[0], 0) | Bdd::value(space, domains1[0], 2) | Bdd::value(space, domains1[0], 5)) & Bdd::value(space, domains1[1], 10)); BddRelation rel2 = BddRelation(domains1, (Bdd::value(space, domains1[0], 0) | Bdd::value(space, domains1[0], 1) | Bdd::value(space, domains1[0], 2)) & Bdd::value(space, domains1[1], 10)); BddRelation mapper = BddRelation(domains2, (Bdd::value(space, domains2[0], 0) & Bdd::value(space, domains2[1], 0)) | (Bdd::value(space, domains2[0], 2) & Bdd::value(space, domains2[1], 1)) | (Bdd::value(space, domains2[0], 5) & Bdd::value(space, domains2[1], 2))); BddRelation composed_rel1 = rel1.compose(0, mapper); return (composed_rel1 == rel2);


Member Typedef Documentation

typedef SpecializedRelation<Bdd, BddRelation, BddSet> gbdd::BddRelation::SpecT
 


Constructor & Destructor Documentation

gbdd::BddRelation::BddRelation  )  [inline]
 

Uninitialized constructor.

gbdd::BddRelation::BddRelation const StructureRelation r  )  [inline]
 

Copy constructor.

Parameters:
r Relation to copy

gbdd::BddRelation::BddRelation const Bdd::FiniteVars vs,
bool  value = false
[inline]
 

Constructor for empty relation.

Parameters:
vs Variables to represent the relation with
value value=true gives universal relation, value=false gives empty

gbdd::BddRelation::BddRelation const Bdd::FiniteVars vs,
Bdd  rel_bdd
[inline]
 

Constructor.

Parameters:
vs Variables for relation
rel_bdd Bdd over vs describing relation

gbdd::BddRelation::BddRelation const Domains ds,
Bdd  rel_bdd
[inline]
 

Constructor.

Parameters:
ds Domains of relation
rel_bdd Bdd representing the relation

gbdd::BddRelation::BddRelation const Domains ds,
const BddRelation r
[inline]
 

Adapt domains with automatic renaming.

Parameters:
ds New domains
r Relation to adapt

gbdd::BddRelation::BddRelation Space space,
unsigned int  arity
[inline]
 

Create empty relation.

This can be used to create an empty relation which can be populated with the insert method, which automatically extends the domains

Parameters:
Space to implemented BDD relation
arity Arity of relation


Member Function Documentation

vector< BddRelation > gbdd::BddRelation::color unsigned int  domain_index,
Domain  color_domain,
vector< BddRelation rels
[static]
 

Color a vector of relations.

Colors rels by extending domain with index domain_index in each relation by color_domain. For each relation rels [i], the resulting returned relation have the variables in color_domain set to the value i.

Parameters:
domain_index Domain to color
color_domain Domain to use for colors
rels Relations to color
Returns:
The colored relations, in the same order as rels

BddRelation gbdd::BddRelation::enumeration vector< BddSet > &  sets,
Domain  dom_enum
[static]
 

Creates a membership relation for a vector of sets.

The domains of each set must be the same

Parameters:
sets Sets to enumerate
dom_enum Domain to use for enumeration
Returns:
A relation R defined such that R(x, i) iff x is in sets[i]

BddRelation gbdd::BddRelation::enumeration vector< BddSet > &  sets  )  [static]
 

Creates a membership relation for a vector of sets.

The domains of each set must be the same

Parameters:
sets Sets to enumerate
Returns:
A relation R defined such that R(x, i) iff x is in sets[i]

const Bdd & gbdd::BddRelation::get_bdd  )  const
 

Get BDD of relation.

Returns:
The BDD of this relation

Space* gbdd::BddRelation::get_space  )  const [inline]
 

Get space of relation.

Returns:
The BDD space used to implement relation

void gbdd::BddRelation::insert unsigned int  v1,
unsigned int  v2
 

void gbdd::BddRelation::insert const vector< unsigned int > &  vals  ) 
 

Inserts an element into the relation.

The domains of the relation are extended if necessary

Parameters:
vals Element to insert

bool gbdd::BddRelation::is_false  )  const
 

Test for false.

Returns:
Whether this relation is empty

bool gbdd::BddRelation::is_true  )  const
 

Test for true.

Returns:
Whether this relation is universal


Friends And Related Function Documentation

ostream& operator<< ostream &  out,
const BddRelation r
[friend]
 

Print relation.

Parameters:
out Stream to print on
r Relation to print


The documentation for this class was generated from the following files:
Generated on Thu Aug 12 13:21:42 2004 for gbdd by doxygen 1.3.6