sdd

Class Vtree

java.lang.Object

buffer.CanonicalWatched

sdd.Vtree

Direct Known Subclasses:

VtreeLeaf, VtreeNode

public abstract class Vtree
extends CanonicalWatched

A Vtree, i.e., a vtree, is a binary (sub)tree that supports a SDD. A vtree is defined as a binary (ordered) tree whose leaves are decorated with variables, and such that a variable appears at most once. There are two vtree implementations: VtreeLeaf and VtreeNode.

Constructor Summary

Constructors

Constructor and Description
Vtree()

Method Summary

Methods

Modifier and Type	Method and Description
abstract boolean	addVariables(java.util.Set<Variable> s) Adds the variables in this vtree to the specified set.
abstract boolean	contains(Vtree vt) Indicates whether this vtree contains the specified vtree.
abstract boolean	findPathTo(Vtree vt, java.util.List<VtreeNode> path) Stores in the specified list the ``path'' from this vtree to the specified vtree (excluded).
abstract int	getDepth() Returns the depth of this vtree.
abstract java.util.Set<Variable>	getVariables() Returns the collection of variables that decorate the leaves of this vtree.
abstract boolean	isLeaf() Indicates whether this vtree is a leaf.

Methods inherited from class buffer.CanonicalWatched

destroy, equals, equivalent, getBuffer, getCanonical, hashCode, print, unwatch, unwatchAll, verifyValidity, watch

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

Vtree

public Vtree()

Method Detail

getVariables

public abstract java.util.Set<Variable> getVariables()

Returns the collection of variables that decorate the leaves of this vtree. Incidentally, this method also tests whether this vtree is correct, i.e., whether a variable appears twice in the tree.

Returns:

the variables that this vtree is defined on.

Throws:

java.lang.IllegalStateException - if a variable is present twice in this vtree.

isLeaf

public abstract boolean isLeaf()

Indicates whether this vtree is a leaf.

Returns:

true if this vtree is a VtreeLeaf, false is this vtree is a VtreeNode.

addVariables

public abstract boolean addVariables(java.util.Set<Variable> s)

Adds the variables in this vtree to the specified set.

Parameters:

s - the set where the variables in this vtree should be inserted.

Returns:

true if all variables could be inserted, false if one of the variables of this vtree is inserted twice or was already in s.

getDepth

public abstract int getDepth()

Returns the depth of this vtree. The depth is defined as the maximal distance between the root of this vtree and one of its leaves. The depth provides some insight about the content of the tree (whether it's worth checking something in its subtree for instance).

Returns:

the depth of this vtree.

contains

public abstract boolean contains(Vtree vt)

Indicates whether this vtree contains the specified vtree.

Parameters:

vt - the vtree that is looked for.

Returns:

true if vt is part of this.

findPathTo

public abstract boolean findPathTo(Vtree vt,
                 java.util.List<VtreeNode> path)

Stores in the specified list the ``path'' from this vtree to the specified vtree (excluded). A path is sequence of vtrees that are children (the left of the right element) of the next element in the sequence.

Parameters:

vt - the vtree to which a path is requested.

path - the list where the path is recorded.

Returns:

true if a path is found.