Ordered n-ary decision diagram structure. More...

#include <DdStructure.hpp>

Collaboration diagram for tdzdd::DdStructure< ARITY >:

Classes
class	const_iterator
	Iterator on a set of integer vectors represented by a DD. More...

Public Member Functions
	DdStructure ()
	Default constructor.

	DdStructure (int n, bool useMP=false)
	Universal ZDD constructor. More...

template<typename SPEC >
	DdStructure (DdSpecBase< SPEC, ARITY > const &spec, bool useMP=false)
	DD construction. More...

template<typename SPEC >
void	zddSubset (DdSpecBase< SPEC, ARITY > const &spec)
	ZDD subsetting. More...

bool	useMultiProcessors (bool flag=true)
	Enables or disables multiple processor algorithms. More...

NodeId &	root ()
	Gets the root node. More...

NodeId	root () const
	Gets the root node. More...

NodeId	child (NodeId f, int b) const
	Gets a child node. More...

NodeTableHandler< ARITY > &	getDiagram ()
	Gets the diagram. More...

NodeTableHandler< ARITY > const &	getDiagram () const
	Gets the diagram. More...

int	topLevel () const
	Gets the level of the root node. More...

size_t	size () const
	Gets the number of nonterminal nodes. More...

bool	empty () const
	Checks if DD is a 0-terminal only. More...

bool	operator== (DdStructure const &o) const
	Checks structural equivalence with another DD. More...

bool	operator!= (DdStructure const &o) const
	Checks structural inequivalence with another DD. More...

void	qddReduce ()
	QDD reduction. More...

void	bddReduce ()
	BDD reduction. More...

void	zddReduce ()
	ZDD reduction. More...

template<bool BDD, bool ZDD>
void	reduce ()
	BDD/ZDD reduction. More...

DdStructure	bdd2zdd (int numVars) const
	Transforms a BDD into a ZDD. More...

DdStructure	zdd2bdd (int numVars) const
	Transforms a ZDD into a BDD. More...

std::string	bddCardinality (int numVars) const
	Counts the number of minterms of the function represented by this BDD. More...

std::string	zddCardinality () const
	Counts the number of sets in the family of sets represented by this ZDD. More...

template<typename S , typename T , typename R >
R	evaluate (DdEval< S, T, R > const &evaluator) const
	Evaluates the DD from the bottom to the top. More...

const_iterator	begin () const
	Returns an iterator to the first instance, which is viewed as a collection of item numbers. More...

const_iterator	end () const
	Returns an iterator to the element following the last instance. More...

int	getRoot (NodeId &f) const
	Implements DdSpec.

int	getChild (NodeId &f, int level, int value) const
	Implements DdSpec.

size_t	hashCode (NodeId const &f) const
	Implements DdSpec.

void	dumpSapporo (std::ostream &os) const
	Dumps the node table in Sapporo ZDD format. More...

Public Member Functions inherited from tdzdd::DdSpecBase< DdStructure< ARITY >, AR >
std::vector< std::pair< int, int > >	findOneInstance () const
	Returns a random instance using simple depth-first search without caching. More...

void	dumpDot (std::ostream &os=std::cout, std::string title=typenameof< DdStructure< ARITY > >()) const
	Dumps the diagram in Graphviz (DOT) format. More...

std::string	dot (std::string title=typenameof< DdStructure< ARITY > >()) const
	Makes an input code for Graphviz. More...

Detailed Description

template<int ARITY>
class tdzdd::DdStructure< ARITY >

Ordered n-ary decision diagram structure.

Template Parameters

ARITY arity of the nodes.

Definition at line 56 of file DdStructure.hpp.

Constructor & Destructor Documentation

◆ DdStructure() [1/2]

template<int ARITY>

tdzdd::DdStructure< ARITY >::DdStructure	(	int	n,
		bool	useMP = `false`
	)

inline

Universal ZDD constructor.

Parameters

n	the number of variables.
useMP	use algorithms for multiple processors.

Definition at line 82 of file DdStructure.hpp.

◆ DdStructure() [2/2]

template<int ARITY>

template<typename SPEC >

tdzdd::DdStructure< ARITY >::DdStructure	(	DdSpecBase< SPEC, ARITY > const &	spec,
		bool	useMP = `false`
	)

inline

DD construction.

Parameters

spec	DD spec.
useMP	use algorithms for multiple processors.

Definition at line 105 of file DdStructure.hpp.

References tdzdd::DdBuilder< S >::construct(), tdzdd::DdBuilderMP< S >::construct(), tdzdd::DdBuilder< S >::initialize(), tdzdd::DdBuilderMP< S >::initialize(), and tdzdd::DdStructure< ARITY >::size().

Here is the call graph for this function:

Member Function Documentation

◆ bdd2zdd()

template<int ARITY>

DdStructure tdzdd::DdStructure< ARITY >::bdd2zdd ( int numVars ) const

inline

Transforms a BDD into a ZDD.

Parameters

numVars the number of variables.

Definition at line 416 of file DdStructure.hpp.

References tdzdd::DdStructure< ARITY >::DdStructure().

Here is the call graph for this function:

◆ bddCardinality()

template<int ARITY>

std::string tdzdd::DdStructure< ARITY >::bddCardinality ( int numVars ) const

inline

Counts the number of minterms of the function represented by this BDD.

Parameters

numVars the number of input variables of the function.

Returns: the number of itemsets.

Definition at line 437 of file DdStructure.hpp.

References tdzdd::DdStructure< ARITY >::evaluate().

Here is the call graph for this function:

◆ bddReduce()

template<int ARITY>

void tdzdd::DdStructure< ARITY >::bddReduce ( )

inline

BDD reduction.

The node of which two edges points to the identical node is deleted.

Definition at line 372 of file DdStructure.hpp.

◆ begin()

template<int ARITY>

const_iterator tdzdd::DdStructure< ARITY >::begin ( ) const

inline

Returns an iterator to the first instance, which is viewed as a collection of item numbers.

Supports binary ZDDs only.

Returns: iterator to the first instance.

Definition at line 661 of file DdStructure.hpp.

◆ child()

template<int ARITY>

NodeId tdzdd::DdStructure< ARITY >::child	(	NodeId	f,
		int	b
	)		const

inline

Gets a child node.

Parameters

f	parent node ID.
b	branch number.

Returns: child node ID.

Definition at line 260 of file DdStructure.hpp.

Referenced by tdzdd::DdStructure< ARITY >::getChild().

◆ dumpSapporo()

template<int ARITY>

void tdzdd::DdStructure< ARITY >::dumpSapporo ( std::ostream & os ) const

inline

Dumps the node table in Sapporo ZDD format.

Works only for binary DDs.

Parameters

os	the output stream.

Definition at line 704 of file DdStructure.hpp.

References tdzdd::DdStructure< ARITY >::size().

Here is the call graph for this function:

◆ empty()

template<int ARITY>

bool tdzdd::DdStructure< ARITY >::empty ( ) const

inline

Checks if DD is a 0-terminal only.

Returns: true if DD is a 0-terminal only.

Definition at line 300 of file DdStructure.hpp.

◆ end()

template<int ARITY>

const_iterator tdzdd::DdStructure< ARITY >::end ( ) const

inline

Returns an iterator to the element following the last instance.

Supports binary ZDDs only.

Returns: iterator to the instance following the last instance.

Definition at line 670 of file DdStructure.hpp.

◆ evaluate()

template<int ARITY>

template<typename S , typename T , typename R >

R tdzdd::DdStructure< ARITY >::evaluate ( DdEval< S, T, R > const & evaluator ) const

inline

Evaluates the DD from the bottom to the top.

Parameters

evaluator the driver class that implements DdEval interface.

Returns: value at the root.

Definition at line 455 of file DdStructure.hpp.

Referenced by tdzdd::DdStructure< ARITY >::bddCardinality(), and tdzdd::DdStructure< ARITY >::zddCardinality().

◆ getDiagram() [1/2]

template<int ARITY>

NodeTableHandler<ARITY>& tdzdd::DdStructure< ARITY >::getDiagram ( )

inline

Gets the diagram.

Returns: the node table handler.

Definition at line 268 of file DdStructure.hpp.

◆ getDiagram() [2/2]

template<int ARITY>

NodeTableHandler<ARITY> const& tdzdd::DdStructure< ARITY >::getDiagram ( ) const

inline

Gets the diagram.

Returns: the node table handler.

Definition at line 276 of file DdStructure.hpp.

◆ operator!=()

template<int ARITY>

bool tdzdd::DdStructure< ARITY >::operator!= ( DdStructure< ARITY > const & o ) const

inline

Checks structural inequivalence with another DD.

Returns: true if they have the different structure.

Definition at line 356 of file DdStructure.hpp.

References tdzdd::DdStructure< ARITY >::operator==().

Here is the call graph for this function:

◆ operator==()

template<int ARITY>

bool tdzdd::DdStructure< ARITY >::operator== ( DdStructure< ARITY > const & o ) const

inline

Checks structural equivalence with another DD.

Returns: true if they have the same structure.

Definition at line 308 of file DdStructure.hpp.

References tdzdd::MyHashMap< K, V, Hash, Equal >::getValue(), tdzdd::MyHashTable< MyHashMapEntry< K, V >, MyHashMapHashWrapper< K, V, Hash, Equal >, MyHashMapHashWrapper< K, V, Hash, Equal > >::initialize(), and tdzdd::DdStructure< ARITY >::size().

Referenced by tdzdd::DdStructure< ARITY >::operator!=().

Here is the call graph for this function:

◆ qddReduce()

template<int ARITY>

void tdzdd::DdStructure< ARITY >::qddReduce ( )

inline

QDD reduction.

No node deletion rule is applied.

Definition at line 364 of file DdStructure.hpp.

◆ reduce()

template<int ARITY>

template<bool BDD, bool ZDD>

void tdzdd::DdStructure< ARITY >::reduce ( )

inline

BDD/ZDD reduction.

Template Parameters

BDD	enable BDD reduction.
ZDD	enable ZDD reduction.

Definition at line 390 of file DdStructure.hpp.

References tdzdd::DdStructure< ARITY >::size().

Here is the call graph for this function:

◆ root() [1/2]

template<int ARITY>

NodeId& tdzdd::DdStructure< ARITY >::root ( )

inline

Gets the root node.

Returns: root node ID.

Definition at line 242 of file DdStructure.hpp.

◆ root() [2/2]

template<int ARITY>

NodeId tdzdd::DdStructure< ARITY >::root ( ) const

inline

Gets the root node.

Returns: root node ID.

Definition at line 250 of file DdStructure.hpp.

◆ size()

template<int ARITY>

size_t tdzdd::DdStructure< ARITY >::size ( ) const

inline

Gets the number of nonterminal nodes.

Returns: the number of nonterminal nodes.

Definition at line 292 of file DdStructure.hpp.

Referenced by tdzdd::DdStructure< ARITY >::DdStructure(), tdzdd::DdStructure< ARITY >::dumpSapporo(), tdzdd::DdStructure< ARITY >::operator==(), tdzdd::DdStructure< ARITY >::reduce(), and tdzdd::DdStructure< ARITY >::zddSubset().

◆ topLevel()

template<int ARITY>

int tdzdd::DdStructure< ARITY >::topLevel ( ) const

inline

Gets the level of the root node.

Returns: the level of root ZDD variable.

Definition at line 284 of file DdStructure.hpp.

◆ useMultiProcessors()

template<int ARITY>

bool tdzdd::DdStructure< ARITY >::useMultiProcessors ( bool flag = true )

inline

Enables or disables multiple processor algorithms.

Parameters

flag	true for using multiple processor algorithms.

Returns: old value of the flag.

Definition at line 232 of file DdStructure.hpp.

◆ zdd2bdd()

template<int ARITY>

DdStructure tdzdd::DdStructure< ARITY >::zdd2bdd ( int numVars ) const

inline

Transforms a ZDD into a BDD.

Parameters

numVars the number of variables.

Definition at line 426 of file DdStructure.hpp.

References tdzdd::DdStructure< ARITY >::DdStructure().

Here is the call graph for this function:

◆ zddCardinality()

template<int ARITY>

std::string tdzdd::DdStructure< ARITY >::zddCardinality ( ) const

inline

Counts the number of sets in the family of sets represented by this ZDD.

Returns: the number of itemsets.

Definition at line 445 of file DdStructure.hpp.

References tdzdd::DdStructure< ARITY >::evaluate().

Here is the call graph for this function:

◆ zddReduce()

template<int ARITY>

void tdzdd::DdStructure< ARITY >::zddReduce ( )

inline

ZDD reduction.

The node of which 1-edge points to the 0-terminal is deleted.

Definition at line 380 of file DdStructure.hpp.

◆ zddSubset()

template<int ARITY>

template<typename SPEC >

void tdzdd::DdStructure< ARITY >::zddSubset ( DdSpecBase< SPEC, ARITY > const & spec )

inline

ZDD subsetting.

Parameters

spec ZDD spec.

Definition at line 166 of file DdStructure.hpp.

References tdzdd::ZddSubsetter< S >::initialize(), tdzdd::ZddSubsetterMP< S >::initialize(), tdzdd::DdStructure< ARITY >::size(), tdzdd::ZddSubsetter< S >::subset(), and tdzdd::ZddSubsetterMP< S >::subset().

Here is the call graph for this function:

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

include/tdzdd/DdStructure.hpp

Classes

Public Member Functions

Detailed Description

template<int ARITY> class tdzdd::DdStructure< ARITY >

Constructor & Destructor Documentation

◆ DdStructure() [1/2]

◆ DdStructure() [2/2]

Member Function Documentation

◆ bdd2zdd()

◆ bddCardinality()

◆ bddReduce()

◆ begin()

◆ child()

◆ dumpSapporo()

◆ empty()

◆ end()

◆ evaluate()

◆ getDiagram() [1/2]

◆ getDiagram() [2/2]

◆ operator!=()

◆ operator==()

◆ qddReduce()

◆ reduce()

◆ root() [1/2]

◆ root() [2/2]

◆ size()

◆ topLevel()

◆ useMultiProcessors()

◆ zdd2bdd()

◆ zddCardinality()

◆ zddReduce()

◆ zddSubset()

template<int ARITY>
class tdzdd::DdStructure< ARITY >