GSDD Class Reference

This class is the base class representing a hierarchical Set Decision Diagram. More...

#include <SDD.h>

Inheritance diagram for GSDD:

Collaboration diagram for GSDD:

Public Member Functions
Public Constructors
	GSDD (int variable, Valuation value)
	Construct a GSDD with arguments given. More...
	GSDD ()
	Default constructor creates the empty set SDD. More...
	GSDD (int var, const DataSet &val, const GSDD &d=one)
	The most common way for the user of creating SDD. More...
	GSDD (int var, const GSDD &val, const GSDD &d=one)
	Another common way for the user to create SDD. More...
	GSDD (int var, const class SDD &val, const GSDD &d=one)
	GSDD (const _GSDD &_g)
	A should be private constructor used in internals, DO NOT USE THIS. More...
	GSDD (_GSDD *_g)
	UNIMPLEMENTED DELIBERATELY: see SHom.h for details. More...
	GSDD (const _GSDD *_g)
Comparisons for hash and map storage
bool	operator== (const GSDD &g) const
	Comparison between DDD. More...
bool	operator!= (const GSDD &g) const
	Comparison between DDD. More...
bool	operator< (const GSDD &g) const
	Total ordering function between DDD. More...
unsigned int	refCounter () const
	Returns current reference count of a node. More...
unsigned long int	size () const
	Returns the size in number of nodes of a SDD structure. More...
std::pair< unsigned long int, unsigned long int >	node_size () const
size_t	nbsons () const
	Returns the number of successors of a given node. This is the size of the arc array of the node. More...
long double	nbStates () const
	Returns the number of states or paths represented by a given node. More...
DataSet implementation interface
This is the implementation of the DataSet class interface used in SDD context. These functions allow to reference SDD from SDD arcs. IMPORTANT Remember to delete returned values after use. Note these functions are not resistant to incompatible DataSet types. When these functions have a parameter "b", it should be a reference to a SDD from proper behavior.
DataSet *	newcopy () const
	Return a new copy of a SDD. More...
DataSet *	set_intersect (const DataSet &b) const
	Compute intersection of two SDD. More...
DataSet *	set_union (const DataSet &b) const
	Compute union of two SDD. More...
DataSet *	set_minus (const DataSet &b) const
	Compute set difference of two SDD. More...
bool	empty () const
	Return true if this is the empty set. More...
DataSet *	empty_set () const
	Returns a pointer to GSDD::null. More...
bool	set_equal (const DataSet &b) const
	Compares to DataSet for equality. More...
bool	set_less_than (const DataSet &b) const
	Compares two sets with a total order. More...
long double	set_size () const
	Compares to DataSet for equality. More...
size_t	set_hash () const
	Returns a hash key for the SDD. More...
void	set_print (std::ostream &os) const
	Textual (human readable) output of a SDD. More...

Static Public Attributes
Terminal nodes defined as constants
static const GSDD	one
	The accepting terminal. This is the basic leaf for accepted sequences. More...
static const GSDD	null
	The non-accepting terminal. More...
static const GSDD	top
	The approximation terminal. More...

Private Member Functions
void	print (std::ostream &os, std::string s) const
	Internal function used in recursion for textual printing of GDDD. More...

Private Attributes
const _GSDD *	concret
	The real implementation class. More...

Friends
class	SDD
	Open access to concret for reference counting in DDD. More...
class	_GSDD
	open access to internal implementation class. More...
std::ostream &	operator<< (std::ostream &os, const GSDD &g)
	A textual output. More...

Public Accessors
typedef std::vector< std::pair< DataSet *, GSDD > >	Valuation
	To hide how arcs are actually stored. Use GSDD::Valuation to refer to arcs type. More...
typedef Valuation::const_iterator	const_iterator
	To hide how arcs are stored. More...
int	variable () const
	Returns a node's variable. More...
const_iterator	begin () const
	API for iterating over the arcs of a DDD manually. More...
const_iterator	end () const
	API for iterating over the arcs of a DDD manually. More...

Memory Management
Broken right now, dont use me or fixme first Returns the number of nodes that would be used to represent a SDD if no unicity table was used.
void	mark () const
	For garbage collection internals. More...
size_t	hash () const
	For storage in a hash table. More...
static unsigned int	statistics ()
	Returns unicity table current size. Gives the number of different nodes created and not yet destroyed. More...
static void	garbage ()
	For garbage collection, do not call this directly, use MemoryManager::garbage() instead. More...
static void	pstats (bool reinit=true)
	Prints some statistics to std::cout. More...
static size_t	peak ()
	Returns the peak size of the DDD unicity table. This value is maintained up to date upon GarbageCollection. More...

Detailed Description

This class is the base class representing a hierarchical Set Decision Diagram.

It is composed of a set of arcs labeled by sets of values (DataSet in fact) that point to successor GSDD nodes. This class does not implement reference counting : GSDD are destroyed on MemoryManager::Garbage unless they are also referenced as SDD. Note that this class is in fact a kind of smart pointer : operations are delegated on "concret" the true implementation class (of private hidden type _GSDD) that contains the data and has a single memory occurrence thanks to the unicity table.

Member Typedef Documentation

const_iterator

typedef Valuation::const_iterator GSDD::const_iterator

To hide how arcs are stored.

Also for more compact expressions : use GDDD::const_iterator to iterate over the arcs of a DDD

Valuation

typedef std::vector<std::pair<DataSet *,GSDD> > GSDD::Valuation

To hide how arcs are actually stored. Use GSDD::Valuation to refer to arcs type.

Constructor & Destructor Documentation

GSDD() [1/8]

GSDD::GSDD	(	int	variable,
		Valuation	value
	)

Construct a GSDD with arguments given.

Parameters

variable	the variable labeling the node
value	the outgoing arc of the node

References _GSDD, canonical, concret, and variable().

GSDD() [2/8]

GSDD::GSDD ( )

inline

Default constructor creates the empty set SDD.

Referenced by empty_set(), newcopy(), set_intersect(), set_minus(), and set_union().

GSDD() [3/8]

GSDD::GSDD	(	int	var,
		const DataSet &	val,
		const GSDD &	d = one
	)

The most common way for the user of creating SDD.

This constructor builds a node with a single arc of the form var-val->d. Usually a user will create these single path SDD, possibly by imbrication as in GSDD(var1, val1, GSDD( var2, val2 )). Then compose them using +, -, *, ^ ...

Parameters

var	the variable labeling the node
val	the value labeling the arc
d	the successor node or defaults to terminal GSDD::one if none provided

References _GSDD, canonical, concret, DataSet::empty(), DataSet::newcopy(), and _GSDD::valuation.

GSDD() [4/8]

GSDD::GSDD	(	int	var,
		const GSDD &	val,
		const GSDD &	d = one
	)

Another common way for the user to create SDD.

This constructor builds a node with a single arc of the form var-val->d. This adapted version is useful when the arc value is itself the result of Hom applications as the compiler needs the change from GSDD to SDD type to recognize a DataSet

Parameters

var	the variable labeling the node
val	the value labeling the arc
d	the successor node or defaults to terminal GSDD::one if none provided

References _GSDD, canonical, concret, empty(), newcopy(), and _GSDD::valuation.

GSDD() [5/8]

GSDD::GSDD	(	int	var,
		const class SDD &	val,
		const GSDD &	d = one
	)

GSDD() [6/8]

GSDD::GSDD

(

const _GSDD &

_g

)

A should be private constructor used in internals, DO NOT USE THIS.

Calls canonical to uniquify the pointer provided

GSDD() [7/8]

GSDD::GSDD

(

_GSDD *

_g

)

UNIMPLEMENTED DELIBERATELY: see SHom.h for details.

user should use version above const & or below const * into unique storage.

GSDD() [8/8]

GSDD::GSDD

(

const _GSDD *

_g

)

Parameters

_g	The pointer provided should point into the unicity table

Member Function Documentation

begin()

GSDD::const_iterator GSDD::begin

(

)

const

API for iterating over the arcs of a DDD manually.

i.e. not using a predefined evaluation mechanism such as StrongHom

for (GDDD::const_iterator it = a_gddd.begin() ; it != a_gddd.end() ; it++ ) { // do something }

returns the first arc

References concret, and _GSDD::valuation.

Referenced by dotExporter::collect(), hDotExporter::collect(), _SDED_Mult::eval(), _SDED_Minus::eval(), _SDED_Concat::eval(), StrongMLShom::eval(), StrongShom::eval(), sns::SApply2k::eval(), sns::Mult::eval(), sns::SDomExtract::eval(), sns::LocalApply::eval(), sns::SLocalApply::eval(), sns::RecFireSat::eval(), _GShom::eval_skip(), sns::LocalApply::has_image(), sns::SLocalApply::has_image(), StrongShom::has_image(), _GShom::has_image_skip(), sns::LocalApply::invert(), sns::SLocalApply::invert(), MySDDNbStates::nbStates(), print(), dotExporter::printColor(), and SddSize::sddsize().

empty()

bool GSDD::empty ( ) const

virtual

Return true if this is the empty set.

Implements DataSet.

References null.

Referenced by GSDD().

empty_set()

DataSet * GSDD::empty_set ( ) const

virtual

Returns a pointer to GSDD::null.

Implements DataSet.

References GSDD().

end()

GSDD::const_iterator GSDD::end

(

)

const

API for iterating over the arcs of a DDD manually.

i.e. not using a predefined evaluation mechanism such as StrongHom

for (GDDD::const_iterator it = a_gddd.begin() ; it != a_gddd.end() ; it++ ) { // do something }

returns a past the end iterator

References concret, and _GSDD::valuation.

Referenced by dotExporter::collect(), hDotExporter::collect(), _SDED_Mult::eval(), _SDED_Minus::eval(), _SDED_Concat::eval(), StrongMLShom::eval(), StrongShom::eval(), sns::SApply2k::eval(), sns::Mult::eval(), sns::SDomExtract::eval(), sns::LocalApply::eval(), sns::SLocalApply::eval(), sns::RecFireSat::eval(), _GShom::eval_skip(), sns::LocalApply::has_image(), sns::SLocalApply::has_image(), StrongShom::has_image(), _GShom::has_image_skip(), MySDDNbStates::nbStates(), print(), dotExporter::printColor(), and SddSize::sddsize().

garbage()

void GSDD::garbage ( )

static

For garbage collection, do not call this directly, use MemoryManager::garbage() instead.

Todo:

describe garbage collection algorithm(s) + mark usage homogeneously in one place.

References canonical, MySDDNbStates::clear(), Max_SDD, and _GSDD::set_mark().

Referenced by MemoryManager::garbage().

hash()

size_t GSDD::hash ( ) const

inline

For storage in a hash table.

References concret, and ddd::knuth32_hash().

Referenced by _SDED_Mult::create(), nsMLShom::LeftConcat::hash(), _SDED_Mult::hash(), _SDED_Minus::hash(), _SDED_Concat::hash(), sns::Constant::hash(), sns::SApply2k::hash(), sns::Mult::hash(), sns::LeftConcat::hash(), sns::RightConcat::hash(), and sns::Minus::hash().

mark()

void GSDD::mark ( ) const

virtual

For garbage collection internals.

Marks a GSDD as in use in garbage collection phase.

Implements DataSet.

References concret, and _GSDD::mark().

Referenced by sns::Fixpoint::eval(), sns::Constant::mark(), sns::SApply2k::mark(), sns::Mult::mark(), sns::LeftConcat::mark(), sns::RightConcat::mark(), and sns::Minus::mark().

nbsons()

size_t GSDD::nbsons

(

)

const

Returns the number of successors of a given node. This is the size of the arc array of the node.

References concret, and _GSDD::valuation.

Referenced by _GShom::eval_skip().

nbStates()

long double GSDD::nbStates

(

)

const

Returns the number of states or paths represented by a given node.

Referenced by Statistic::load(), and set_size().

newcopy()

DataSet* GSDD::newcopy ( ) const

inlinevirtual

Return a new copy of a SDD.

Implements DataSet.

References GSDD().

Referenced by GSDD().

node_size()

std::pair< unsigned long int, unsigned long int > GSDD::node_size

(

)

const

References SddSize::d3res, and SddSize::res.

Referenced by Statistic::load().

operator!=()

bool GSDD::operator!= ( const GSDD &  g ) const

inline

Comparison between DDD.

Note that comparison is based on "concret" address in unicity table.

Parameters

g	the node to compare to

Returns

true if the nodes are not equal.

References concret.

operator<()

bool GSDD::operator<

(

const GSDD &

g

)

const

Total ordering function between DDD.

Note that comparison is based on "concret" address in unicity table. This ordering is necessary for hash and map storage of GDDD.

Parameters

g	the node to compare to

Returns

true if argument g is greater than "this" node.

References concret.

operator==()

bool GSDD::operator== ( const GSDD &  g ) const

inline

Comparison between DDD.

Note that comparison is based on "concret" address in unicity table.

Parameters

g	the node to compare to

Returns

true if the nodes are equal.

peak()

size_t GSDD::peak ( )

static

Returns the peak size of the DDD unicity table. This value is maintained up to date upon GarbageCollection.

References canonical, and Max_SDD.

Referenced by Statistic::load(), and pstats().

print()

void GSDD::print ( std::ostream &  os, std::string  s  ) const

private

Internal function used in recursion for textual printing of GDDD.

References begin(), end(), one, top, and variable().

pstats()

void GSDD::pstats ( bool  reinit = true )

static

Prints some statistics to std::cout.

Mostly used in debug and development phase. See also MemoryManager::pstats().

Todo:

allow output in other place than cout. Clean up output.

References _GSDD, canonical, and peak().

Referenced by MemoryManager::pstats().

refCounter()

unsigned int GSDD::refCounter

(

)

const

Returns current reference count of a node.

Reference count corresponds to the number of SDD that use a given concrete node. No recursive reference counting is used : son nodes may have refCount=0 even if this node has a positive refCounter.

References concret, and _GSDD::refCounter().

Referenced by dotExporter::collect().

set_equal()

bool GSDD::set_equal ( const DataSet &  b ) const

virtual

Compares to DataSet for equality.

Implements DataSet.

set_hash()

size_t GSDD::set_hash ( ) const

virtual

Returns a hash key for the SDD.

Implements DataSet.

References concret.

set_intersect()

DataSet * GSDD::set_intersect ( const DataSet &  b ) const

virtual

Compute intersection of two SDD.

Implements DataSet.

References GSDD().

set_less_than()

bool GSDD::set_less_than ( const DataSet &  b ) const

virtual

Compares two sets with a total order.

Implements DataSet.

set_minus()

DataSet * GSDD::set_minus ( const DataSet &  b ) const

virtual

Compute set difference of two SDD.

Implements DataSet.

References GSDD().

set_print()

void GSDD::set_print ( std::ostream &  os ) const

inlinevirtual

Textual (human readable) output of a SDD.

Implements DataSet.

set_size()

long double GSDD::set_size ( ) const

virtual

Compares to DataSet for equality.

Implements DataSet.

References nbStates().

set_union()

DataSet * GSDD::set_union ( const DataSet &  b ) const

virtual

Compute union of two SDD.

Implements DataSet.

References GSDD().

size()

unsigned long int GSDD::size

(

)

const

Returns the size in number of nodes of a SDD structure.

statistics()

unsigned int GSDD::statistics ( )

static

Returns unicity table current size. Gives the number of different nodes created and not yet destroyed.

References canonical.

Referenced by MemoryManager::nbSDD().

variable()

int GSDD::variable

(

)

const

Returns a node's variable.

References concret, and _GSDD::variable.

Referenced by dotExporter::collect(), hDotExporter::collect(), _SDED_Add::create(), _SDED_Mult::create(), _SDED_Minus::create(), _SDED_Mult::eval(), _SDED_Minus::eval(), _SDED_Concat::eval(), StrongMLShom::eval(), StrongShom::eval(), sns::SApply2k::eval(), sns::Mult::eval(), sns::SDomExtract::eval(), sns::LocalApply::eval(), sns::SLocalApply::eval(), sns::And::eval(), sns::Add::eval(), sns::RecFireSat::eval(), sns::Fixpoint::eval(), _GShom::eval_skip(), GSDD(), sns::LocalApply::has_image(), sns::SLocalApply::has_image(), sns::And::has_image(), sns::Fixpoint::has_image(), StrongShom::has_image(), _GShom::has_image_skip(), print(), and sns::SApply2k::skip_variable().

Friends And Related Function Documentation

_GSDD

friend class _GSDD

friend

open access to internal implementation class.

Referenced by GSDD(), and pstats().

operator<<

std::ostream& operator<< ( std::ostream &  os, const GSDD &  g  )

friend

A textual output.

Don't use it with large number of paths as each element is printed on a different line

SDD

friend class SDD

friend

Open access to concret for reference counting in DDD.

Member Data Documentation

concret

const _GSDD* GSDD::concret

private

The real implementation class.

All true operations are delagated on this pointer. Construction/destruction take care of ensuring concret is only instantiated once in memory.

Referenced by begin(), end(), GSDD(), hash(), mark(), nbsons(), operator!=(), operator<(), SDD::operator=(), refCounter(), SDD::SDD(), set_hash(), variable(), and SDD::~SDD().

null

const GSDD GSDD::null

static

The non-accepting terminal.

As DDD are a zero-suppressed variant of decision diagrams, paths leading to null are suppressed. Only the empty set is represented by null.

Referenced by SDED::add(), apply2k(), _GShom::compose(), _SDED_Add::create(), _SDED_Mult::create(), _SDED_Minus::create(), _SDED_Concat::create(), empty(), _SDED_Add::eval(), _SDED_Mult::eval(), _SDED_Minus::eval(), _SDED_Concat::eval(), StrongMLShom::eval(), StrongShom::eval(), sns::Constant::eval(), sns::SApply2k::eval(), sns::Mult::eval(), sns::SDomExtract::eval(), sns::LocalApply::eval(), sns::SLocalApply::eval(), sns::SNotCond::eval(), sns::And::eval(), sns::Add::eval(), sns::RecFireSat::eval(), sns::Fixpoint::eval(), _GShom::eval_skip(), sns::Inter::has_image(), sns::LocalApply::has_image(), sns::SLocalApply::has_image(), sns::SNotCond::has_image(), sns::And::has_image(), sns::Add::has_image(), sns::Compose::has_image(), sns::Fixpoint::has_image(), GShom::has_image(), StrongShom::has_image(), _GShom::has_image_skip(), sns::Compose::invert(), sns::Constant::is_selector(), sns::SApply2k::is_selector(), iterateSDD(), MySDDNbStates::nbStates(), GShom::operator()(), and dotExporter::printLevels().

one

const GSDD GSDD::one

static

The accepting terminal. This is the basic leaf for accepted sequences.

Referenced by apply2k(), dotExporter::collect(), hDotExporter::collect(), _SDED_Add::create(), _SDED_Mult::create(), _SDED_Minus::create(), _SDED_Concat::create(), StrongMLShom::eval(), StrongShom::eval(), sns::SDomExtract::eval(), sns::LocalApply::eval(), sns::SLocalApply::eval(), sns::SNotCond::eval(), sns::And::eval(), sns::Add::eval(), sns::RecFireSat::eval(), sns::Fixpoint::eval(), _GShom::eval_skip(), sns::LocalApply::has_image(), sns::SLocalApply::has_image(), sns::And::has_image(), sns::Fixpoint::has_image(), StrongShom::has_image(), _GShom::has_image_skip(), iterateSDD(), MySDDNbStates::nbStates(), print(), and dotExporter::printLevels().

top

const GSDD GSDD::top

static

The approximation terminal.

This represents any finite set of assignment sequences. In a "normal" usage pattern, top terminals should not be produced. In fact the result may be incorrect if Top is encountered at any but the highest level.

Referenced by apply2k(), dotExporter::collect(), hDotExporter::collect(), _SDED_Add::create(), _SDED_Mult::create(), _SDED_Minus::create(), _SDED_Concat::create(), StrongMLShom::eval(), StrongShom::eval(), sns::SDomExtract::eval(), sns::LocalApply::eval(), sns::SLocalApply::eval(), sns::SNotCond::eval(), sns::And::eval(), sns::Add::eval(), sns::RecFireSat::eval(), sns::Fixpoint::eval(), _GShom::eval_skip(), sns::LocalApply::has_image(), sns::SLocalApply::has_image(), sns::And::has_image(), sns::Fixpoint::has_image(), StrongShom::has_image(), _GShom::has_image_skip(), iterateSDD(), MySDDNbStates::nbStates(), StrongShom::phiOne(), print(), and dotExporter::printLevels().

---

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

• SDD.h
• SDD.cpp