Basic ZDD Operations

Basic set operations. More...

Functions
__zdd	adiar::zdd_binop (const zdd &A, const zdd &B, const predicate< bool, bool > &op)
	Apply a binary operator between the sets of two families.
__zdd	adiar::zdd_union (const zdd &A, const zdd &B)
	The union of two families of sets.
__zdd	adiar::operator| (const zdd &lhs, const zdd &rhs)
zdd	adiar::operator+ (const zdd &A)
__zdd	adiar::operator+ (const zdd &lhs, const zdd &rhs)
__zdd	adiar::zdd_intsec (const zdd &A, const zdd &B)
	The intersection of two families of sets.
__zdd	adiar::operator& (const zdd &lhs, const zdd &rhs)
__zdd	adiar::operator* (const zdd &lhs, const zdd &rhs)
__zdd	adiar::zdd_diff (const zdd &A, const zdd &B)
	The set difference of two families of sets.
__zdd	adiar::operator- (const zdd &A)
__zdd	adiar::operator- (const zdd &lhs, const zdd &rhs)
__zdd	adiar::zdd_change (const zdd &A, const generator< zdd::label_type > &vars)
	The symmetric difference between each set in the family and the given set of variables.
template<typename ForwardIt >
__zdd	adiar::zdd_change (const zdd &A, ForwardIt begin, ForwardIt end)
	The symmetric difference between each set in the family and the given set of variables.
__zdd	adiar::zdd_complement (const zdd &A, const generator< zdd::label_type > &dom)
	Complement of A within the given domain.
template<typename ForwardIt >
__zdd	adiar::zdd_complement (const zdd &A, ForwardIt begin, ForwardIt end)
	Complement of A within the given domain.
__zdd	adiar::zdd_complement (const zdd &A)
	Complement of A within the global Variable Domain.
__zdd	adiar::operator~ (const zdd &A)
__zdd	adiar::zdd_expand (const zdd &A, const generator< zdd::label_type > &vars)
	Expands the domain of the given ZDD to also include the given set of labels.
template<typename ForwardIt >
__zdd	adiar::zdd_expand (const zdd &A, ForwardIt begin, ForwardIt end)
	Expands the domain of the given ZDD to also include the given set of labels.
__zdd	adiar::zdd_offset (const zdd &A, zdd::label_type var)
	Subset that do not include the given element.
__zdd	adiar::zdd_offset (const zdd &A)
	Subset that do not include the top variable.
__zdd	adiar::zdd_offset (const zdd &A, const generator< zdd::label_type > &vars)
	Subset that do not include the given set of variables.
template<typename ForwardIt >
__zdd	adiar::zdd_offset (const zdd &A, ForwardIt begin, ForwardIt end)
	Subset that do not include the given set of variables.
__zdd	adiar::zdd_onset (const zdd &A, zdd::label_type var)
	Subset that do include the given element.
__zdd	adiar::zdd_onset (const zdd &A)
	Subset that do include the top variable.
__zdd	adiar::zdd_onset (const zdd &A, const generator< zdd::label_type > &vars)
	Subset that do include the given set of variables.
template<typename ForwardIt >
__zdd	adiar::zdd_onset (const zdd &A, ForwardIt begin, ForwardIt end)
	Subset that do include the given set of variables.
__zdd	adiar::zdd_project (const zdd &A, const predicate< zdd::label_type > &dom)
	Project family of sets onto a domain, i.e. remove from every set all variables not within the domain.
__zdd	adiar::zdd_project (const zdd &A, const generator< zdd::label_type > &dom)
	Project family of sets onto a domain, i.e. remove from every set all variables not within the domain.
template<typename ForwardIt >
__zdd	adiar::zdd_project (const zdd &A, ForwardIt begin, ForwardIt end)
	Project family of sets onto a domain, i.e. remove from every set all variables not within the domain.

Detailed Description

Basic set operations.

Function Documentation

operator&()

__zdd adiar::operator&	(	const zdd &	lhs,
		const zdd &	rhs
	)

See also

zdd_intsec

operator*()

__zdd adiar::operator*	(	const zdd &	lhs,
		const zdd &	rhs
	)

See also

zdd_intsec

operator+() [1/2]

zdd adiar::operator+

(

const zdd &

A

)

See also

zdd_union

operator+() [2/2]

__zdd adiar::operator+	(	const zdd &	lhs,
		const zdd &	rhs
	)

See also

zdd_union

operator-() [1/2]

__zdd adiar::operator-

(

const zdd &

A

)

Remarks

Unary difference subtracts from universe over all variables in th global Variable Domain , making its equivalent to its complement.

See also

zdd_diff, zdd_complement

operator-() [2/2]

__zdd adiar::operator-	(	const zdd &	lhs,
		const zdd &	rhs
	)

See also

zdd_diff

operator|()

__zdd adiar::operator|	(	const zdd &	lhs,
		const zdd &	rhs
	)

See also

zdd_union

operator~()

__zdd adiar::operator~

(

const zdd &

A

)

See also

zdd_complement

zdd_binop()

__zdd adiar::zdd_binop	(	const zdd &	A,
		const zdd &	B,
		const predicate< bool, bool > &	op
	)

Apply a binary operator between the sets of two families.

Parameters

A	ZDD for the left-hand-side of the operator
B	ZDD for the right-hand-side of the operator
op	Binary predicate to combine the two families.

Returns

Product construction of the two that represents the boolean operator applied to the two family of sets.

zdd_change() [1/2]

__zdd adiar::zdd_change	(	const zdd &	A,
		const generator< zdd::label_type > &	vars
	)

The symmetric difference between each set in the family and the given set of variables.

Parameters

A	ZDD to apply with the other.
vars	Generator function of labels to flip in ascending order. These values may not exceed zdd::max_label.

Returns

\( \{ \mathit{vars} \Delta a \mid a \in A \} \)

zdd_change() [2/2]

template<typename ForwardIt >

__zdd adiar::zdd_change	(	const zdd &	A,
		ForwardIt	begin,
		ForwardIt	end
	)

The symmetric difference between each set in the family and the given set of variables.

Parameters

A	ZDD to apply with the other.
begin	Single-pass forward iterator that provides the to-be flipped variables in ascending order. These values may not exceed zdd::max_label.
end	Marks the end for begin.

Returns

\( \{ \mathit{vars} \Delta a \mid a \in A \} \)

zdd_complement() [1/3]

__zdd adiar::zdd_complement

(

const zdd &

A

)

Complement of A within the global Variable Domain.

Parameters

A	family of sets to complement

Precondition

The global Variable Domain is set to a set of variables that is equals to or a superset of the variables in A.

Returns

\( 2^{\mathit{dom}} \setminus A \)

See also

domain_set domain_isset

zdd_complement() [2/3]

__zdd adiar::zdd_complement	(	const zdd &	A,
		const generator< zdd::label_type > &	dom
	)

Complement of A within the given domain.

Parameters

A	family of sets to complement
dom	Labels of the domain in ascending order

Returns

\( 2^{\mathit{dom}} \setminus A \)

zdd_complement() [3/3]

template<typename ForwardIt >

__zdd adiar::zdd_complement	(	const zdd &	A,
		ForwardIt	begin,
		ForwardIt	end
	)

Complement of A within the given domain.

Parameters

A	family of sets to complement
begin	Single-pass forward iterator that provides the domain's variables in ascending order. These values may not exceed zdd::max_label.
end	Marks the end for begin.

Returns

\( 2^{\mathit{dom}} \setminus A \)

zdd_diff()

__zdd adiar::zdd_diff	(	const zdd &	A,
		const zdd &	B
	)

The set difference of two families of sets.

Returns

\( A \setminus B \)

zdd_expand() [1/2]

__zdd adiar::zdd_expand	(	const zdd &	A,
		const generator< zdd::label_type > &	vars
	)

Expands the domain of the given ZDD to also include the given set of labels.

Adds don't care nodes on each levels in vars. That is, this essentially is the inverse of the zdd_project and lifts the set of sets unprojects to a larger domain.

Parameters

A	Family of set to expand.
vars	Generator function of labels to unproject in ascending order. No variables it generates may already exist in A or exceed zdd::max_label.

Returns

\( \bigcup_{a \in A, i \in 2^{vars}} (a \cup i) \)

zdd_expand() [2/2]

template<typename ForwardIt >

__zdd adiar::zdd_expand	(	const zdd &	A,
		ForwardIt	begin,
		ForwardIt	end
	)

Expands the domain of the given ZDD to also include the given set of labels.

Adds don't care nodes on each levels in vars. That is, this essentially is the inverse of the zdd_project and lifts the set of sets unprojects to a larger domain.

Parameters

A	Family of set to expand.
begin	Single-pass forward iterator that provides the to-be unprojected variables in ascending order. These may not be present in A or exceed zdd::max_label.
end	Marks the end for begin.

Returns

\( \bigcup_{a \in A, i \in 2^{vars}} (a \cup i) \)

See also

zdd_project

zdd_intsec()

__zdd adiar::zdd_intsec	(	const zdd &	A,
		const zdd &	B
	)

The intersection of two families of sets.

Returns

\( A \cap B \)

zdd_offset() [1/4]

__zdd adiar::zdd_offset

(

const zdd &

A

)

Subset that do not include the top variable.

Parameters

A	Family of set

Remarks

In other BDD packages, this function is good for traversing a ZDD. But, here this is not a constant-time operation but constructs an entire new ZDD of up-to linear size.

Exceptions

invalid_argument

If A is a terminal.

zdd_offset() [2/4]

__zdd adiar::zdd_offset	(	const zdd &	A,
		const generator< zdd::label_type > &	vars
	)

Subset that do not include the given set of variables.

Parameters

A	Family of set
vars	Generator function of the variable labels to filter on in ascending order. The values generated should not exceed zdd::max_label.

Returns

\( \{ a \in A \mid \forall i \in \mathit{vars} : i \not\in a \} \)

zdd_offset() [3/4]

template<typename ForwardIt >

__zdd adiar::zdd_offset	(	const zdd &	A,
		ForwardIt	begin,
		ForwardIt	end
	)

Subset that do not include the given set of variables.

Parameters

A	Family of set
begin	Single-pass forward iterator that provides the variables to filter out in ascending order. These values may not exceed zdd::max_label.
end	Marks the end for begin.

Returns

\( \{ a \in A \mid \forall i \in \mathit{vars} : i \not\in a \} \)

zdd_offset() [4/4]

__zdd adiar::zdd_offset	(	const zdd &	A,
		zdd::label_type	var
	)

Subset that do not include the given element.

Parameters

A	Family of set
var	Variable to include.

Returns

\( \{ a \in A \mid \mathit{var} \not\in a \} \)

zdd_onset() [1/4]

__zdd adiar::zdd_onset

(

const zdd &

A

)

Subset that do include the top variable.

Parameters

A	Family of set

Remarks

In other BDD packages, this function is good for traversing a ZDD. But, here this is not a constant-time operation but constructs an entire new ZDD of up-to linear size.

Exceptions

invalid_argument

If A is a terminal.

zdd_onset() [2/4]

__zdd adiar::zdd_onset	(	const zdd &	A,
		const generator< zdd::label_type > &	vars
	)

Subset that do include the given set of variables.

Parameters

A	Family of set
vars	Generator function of the variable labels to filter on in ascending order. The values generated may not exceed zdd::max_label

Returns

\( \{ a \in A \mid \forall i \in \mathit{vars} : i \in a \} \)

zdd_onset() [3/4]

template<typename ForwardIt >

__zdd adiar::zdd_onset	(	const zdd &	A,
		ForwardIt	begin,
		ForwardIt	end
	)

Subset that do include the given set of variables.

Parameters

A	Family of set
begin	Single-pass forward iterator that provides the variables to filter out in ascending order. These values may not exceed zdd::max_label
end	Marks the end for begin.

Returns

\( \{ a \in A \mid \forall i \in \mathit{vars} : i \in a \} \)

zdd_onset() [4/4]

__zdd adiar::zdd_onset	(	const zdd &	A,
		zdd::label_type	var
	)

Subset that do include the given element.

Parameters

A	Family of set
var	Variable to include.

Returns

\( \{ a \in A \mid \mathit{var} \in a \} \)

zdd_project() [1/3]

__zdd adiar::zdd_project	(	const zdd &	A,
		const generator< zdd::label_type > &	dom
	)

Project family of sets onto a domain, i.e. remove from every set all variables not within the domain.

Parameters

A	Family of sets to project
dom	Generator function, that produces the variables of the domain in descending order. They should not exceed zdd::max_label.

Returns

\( \prod_{\mathit{dom}}(A) = \{ a \setminus \mathit{dom}^c \mid a \in A \} \)

See also

zdd_expand

zdd_project() [2/3]

__zdd adiar::zdd_project	(	const zdd &	A,
		const predicate< zdd::label_type > &	dom
	)

Project family of sets onto a domain, i.e. remove from every set all variables not within the domain.

Parameters

A	Family of sets to project
dom	Predicate function that defines the domain.

Returns

\( \prod_{\mathit{dom}}(A) = \{ a \setminus \mathit{dom}^c \mid a \in A \} \)

See also

zdd_expand

zdd_project() [3/3]

template<typename ForwardIt >

__zdd adiar::zdd_project	(	const zdd &	A,
		ForwardIt	begin,
		ForwardIt	end
	)

Project family of sets onto a domain, i.e. remove from every set all variables not within the domain.

Parameters

A	Family of sets to project
begin	Single-pass forward iterator that provides the domain in descending order. Its values should not exceed zdd::max_label
end	Marks the end for begin.

Returns

\( \prod_{\mathit{dom}}(A) = \{ a \setminus \mathit{dom}^c \mid a \in A \} \)

See also

zdd_expand

zdd_union()

__zdd adiar::zdd_union	(	const zdd &	A,
		const zdd &	B
	)

The union of two families of sets.

Returns

\( A \cup B \)