COMPUTE TREE
Computes the binary search tree associated to the polytopic partition
Contents
Method of pwag object.
Description
This method computes the binary search tree corresponding to the polytopic partition. The binary search tree can be used to evaluate the pwag function in a more efficient way and it is necessary for the circuit implementation. Each node of the tree corresponds to an edge, each leaf to a region. The binary search tree is saved as a property (tree) of the pwag object, for this reason the pwag object must be returned as output. tree is a structure with the following fields:
- numberOfNodes: number of the nodes of the tree
- minDepth: minimum depth of the tree
- meanDepth: mean depth of the tree
- maxDepth: maximum depth of the tree
- balance: the lower is this value the more the tree is balanced
- nodes: array of structures each of which defines a node of the tree
The structure nodes has the following fields:
- edge_index: index of the edge used by the parent node to split the domain in two parts
- region_index: indexes of the polytopes which can be found by exploring the tree starting from the current node
- edge_set: set of the edges which can still be chosen
- children: index of the elements of the nodes structure which correspond to the sons of the current node
- leaf: flag indicating whether the current node is a leaf or not
- depth: depth of the current node. The root node has depth = 0
Syntax
object = computeTree(object)
Computes the bynary search tree with the default settings (see below).
object = computeTree(object,mode)
Computes the binary search tree by defining a mode which can be either 'regions' (default) or 'functions'. In the first case the domain is splitted based on the polytopes, in the second case the domain is splitted based on the affine functions to be evaluated. This means that if there are only two regions on a side of an edge and in these two regions the affine functions to be computed are the same, the two regions are considered as only one region.
object = computeTree(object,balance)
Computes the binary search tree by specifying a value which determines the balance of the tree itself. balance is a number between 0 and 1 which indicates if you prefer to have a more balanced tree (balance -> 1) but with a greater number of nodes or a less balanced tree (balance -> 0) with less nodes. Default value 0.5.
object = computeTree(object,mode,balance)
Computes the binary search tree by specifying both mode and balance.
Acknowledgements
Contributors:
- Alberto Oliveri (alberto.oliveri@unige.it)
- Tomaso Poggi (tpoggi@essbilbao.org)
Copyright is with:
- Copyright (C) 2010-2011 University of Genoa, Italy.