Struct affinitree::pwl::afftree::AffTree
source · pub struct AffTree<const K: usize> {
pub tree: Tree<AffContent, K>,
pub in_dim: usize,
/* private fields */
}
Expand description
A corner stone of affinitree
that can represent any (continuous or non-continuous) piece-wise linear function.
This structure is based on an oblique decision tree:
- Its inner nodes form a decision structure that partitions the input space similar to a BSP tree into convex regions.
- Its terminal nodes associate with each such region a linear function.
Technically, each decision node divides the space into two halfspace which are separated by a hyperplane. The outgoing edges of decision nodes have labels that uniquely associate the edge with a halfspace. A path over multiple edges then corresponds to the intersection of the associated halfspaces of each edge.
To encode a given piece-wise linear function as an AffTree, one first has to derive the decision structure based on the regions of the function. That is, each path from root to a terminal corresponds to exactly one region of the function. Then, the terminal stores the respective linear function that is active in this region.
§Example
The piece-wise linear function f(x, y) = |max{x,y}| is represented as the AffTree
This tree is constructed in affinitree
as follows:
use affinitree::{aff, poly, pwl::afftree::AffTree, pwl::dot::dot_str, linalg::affine::PolyRepr};
// construct a new AffTree instance with the given inequality as its root.
let mut dd = AffTree::<2>::from_aff(poly!([[1, 1]] < [0]).convert_to(PolyRepr::MatrixBiasGeqZero)); // node index 0
// add two additional decision nodes from inequalities
dd.add_decision(0, 0, poly!([[-1, 1]] < [0]).convert_to(PolyRepr::MatrixBiasGeqZero)); // node index 1
dd.add_decision(0, 1, poly!([[-1, 1]] < [0]).convert_to(PolyRepr::MatrixBiasGeqZero)); // node index 2
// add the terminal nodes with the given functions
// first argument is the parent node, second the label (true / false), and third the affine function
dd.add_terminal(1, 0, aff!([[0, 1]] + [0]));
dd.add_terminal(1, 1, aff!([[1, 0]] + [0]));
dd.add_terminal(2, 0, aff!([[-1, 0]] + [0]));
dd.add_terminal(2, 1, aff!([[0, -1]] + [0]));
// export the tree into the DOT format of graphviz
let mut str = String::new();
dot_str(&mut str, &dd).unwrap();
println!("{}", str);
// digraph dd {
// bgcolor=transparent;
// concentrate=true;
// margin=0;
// n0 [label=" $0 1.00 +$1 1.00 <= 0.00", shape=box];
// n1 [label="−$0 1.00 +$1 1.00 <= 0.00", shape=box];
// n2 [label="−$0 1.00 +$1 1.00 <= 0.00", shape=box];
// n3 [label=" $0 0.00 +$1 1.00 + 0.00", shape=ellipse];
// n4 [label=" $0 1.00 +$1 0.00 + 0.00", shape=ellipse];
// n5 [label="−$0 1.00 +$1 0.00 + 0.00", shape=ellipse];
// n6 [label=" $0 0.00 −$1 1.00 + 0.00", shape=ellipse];
// n0 -> n1 [label=0, style=dashed];
// n0 -> n2 [label=1, style=solid];
// n1 -> n3 [label=0, style=dashed];
// n1 -> n4 [label=1, style=solid];
// n2 -> n5 [label=0, style=dashed];
// n2 -> n6 [label=1, style=solid];
// }
§Technical Overview
AffTree
s are implemented over an arena provided by the slab
crate.
They have a compile time branching factor K
(in most cases a binary tree is sufficient, i.e., K=2).
Elements of the tree have a unique index during their lifetime.
§Composition
AffTree
s allow a modular construction by composition. The semantics of composition
follow directly from the mathematical definition of function composition.
Roughly speaking, the composition of two AffTree instances corresponds to an sequential evaluation of the two trees, as demonstrated by the following example.
use affinitree::{aff, pwl::afftree::AffTree};
use ndarray::arr1;
let mut tree0 = AffTree::<2>::from_aff(aff!([[1., 0.]] + [2.]));
tree0.add_child_node(0, 0, aff!([[2, 0], [0, 2]] + [1, 0]));
tree0.add_child_node(0, 1, aff!([[2, 0], [0, 2]] + [0, 1]));
let mut tree1 = AffTree::<2>::from_aff(aff!([[-0.5, 0.]] + [-1.]));
tree1.add_child_node(0, 0, aff!([[3, 0], [0, 3]] + [5, 0]));
tree1.add_child_node(0, 1, aff!([[-3, 0], [0, -3]] + [0, 5]));
let mut comp = tree0.clone();
comp.compose::<false>(&tree1);
// the sequential evaluation of tree0 and tree1 on the input vector (2, -7)
// yields the same result as evaluating the composition tree
assert_eq!(
tree1.evaluate(&tree0.evaluate(&arr1(&[2., -7.])).unwrap()).unwrap(),
comp.evaluate(&arr1(&[2., -7.])).unwrap()
);
Fields§
§tree: Tree<AffContent, K>
§in_dim: usize
Implementations§
source§impl<const K: usize> AffTree<K>
impl<const K: usize> AffTree<K>
sourcepub fn new(dim: usize) -> AffTree<K>
pub fn new(dim: usize) -> AffTree<K>
Creates an AffTree instance which represents the identity function for the given dim
.
sourcepub fn with_capacity(dim: usize, capacity: usize) -> AffTree<K>
pub fn with_capacity(dim: usize, capacity: usize) -> AffTree<K>
Creates an AffTree instance which represents the identity function for the given dim
.
Allocates space for as many nodes as specified by capacity
(minimum 1).
sourcepub fn from_aff(func: AffFunc) -> AffTree<K>
pub fn from_aff(func: AffFunc) -> AffTree<K>
Creates an AffTree instance which represents the given affine func
.
sourcepub fn from_poly(poly: Polytope, func: AffFunc) -> AffTree<K>
pub fn from_poly(poly: Polytope, func: AffFunc) -> AffTree<K>
Crates an AffTree instance from the given polytope poly
.
The resulting AffTree is a partial function that only accepts inputs inside
the given poly
, for which it returns the input as is.
In this capacity it can be used as a precondition.
sourcepub fn from_slice(reference_point: &Array1<f64>) -> AffTree<K>
pub fn from_slice(reference_point: &Array1<f64>) -> AffTree<K>
Creates a new AffTree instance which corresponds to the affine AffFunc::slice
function.
sourcepub fn from_tree(tree: Tree<AffContent, K>, dim: usize) -> AffTree<K>
pub fn from_tree(tree: Tree<AffContent, K>, dim: usize) -> AffTree<K>
Creates a new AffTree instance from a raw tree whose decisions are affine predicates and terminals are affine functions.
pub fn len(&self) -> usize
sourcepub fn num_terminals(&self) -> usize
pub fn num_terminals(&self) -> usize
Returns the number of terminals in this tree.
sourcepub fn depth(&self) -> usize
pub fn depth(&self) -> usize
Returns the depth of this tree, that is, the length of its longest path.
Correspondingly, an empty tree has depth 0, and a tree with only a root node has depth 1.
sourcepub fn reserve(&mut self, additional: usize)
pub fn reserve(&mut self, additional: usize)
Reserve capacity for at least additional
more nodes to be stored.
See also Tree::reserve
.
sourcepub fn nodes(&self) -> impl Iterator<Item = &AffContent>
pub fn nodes(&self) -> impl Iterator<Item = &AffContent>
Returns an iterator over the nodes of this tree. Nodes are read in index order (continuous in memory) for increased efficiency.
sourcepub fn terminals(&self) -> impl Iterator<Item = &AffContent>
pub fn terminals(&self) -> impl Iterator<Item = &AffContent>
Returns an iterator over the terminal nodes of this tree. Nodes are read in index order (continuous in memory) for increased efficiency.
sourcepub fn decisions(&self) -> impl Iterator<Item = &AffContent>
pub fn decisions(&self) -> impl Iterator<Item = &AffContent>
Returns an iterator over the decision nodes of this tree. Nodes are read in index order (continuous in memory) for increased efficiency.
sourcepub fn polyhedra(&self) -> PolyhedraGen
pub fn polyhedra(&self) -> PolyhedraGen
Returns an iterator like object that performs a depth-first search over this tree. For each node in the tree four entries are returned:
- the current depth,
- the index of the current node,
- the number of siblings of the current node that have not been visited yet,
- the halfspaces of the path leading to the current node
In contrast to polyhedra_iter
this function allows mutual access to the tree during iteration.
§Examples
use affinitree::pwl::afftree::AffTree;
use affinitree::linalg::affine::{AffFunc, Polytope};
let aff_tree = AffTree::<2>::from_aff(AffFunc::identity(2));
let mut poly_iter = aff_tree.polyhedra();
while let Some((dfs_data, poly)) = poly_iter.next(&aff_tree.tree) {
println!("{}", Polytope::intersection_n(2, poly));
}
sourcepub fn polyhedra_iter(&self) -> PolyhedraIter<'_, K> ⓘ
pub fn polyhedra_iter(&self) -> PolyhedraIter<'_, K> ⓘ
Returns an iterator that performs a depth-first search over this tree. For each node in the tree four entries are returned:
- the current depth,
- the index of the current node,
- the number of siblings of the current node that have not been vistied yet,
- the halfspaces of the path leading to the current node
For mutual access during iteration see polyhedra_iter
.
sourcepub fn add_child_node(
&mut self,
node: TreeIndex,
label: Label,
aff: AffFunc
) -> TreeIndex
pub fn add_child_node( &mut self, node: TreeIndex, label: Label, aff: AffFunc ) -> TreeIndex
Adds a single node to the graph directly.
Use with caution: Caller is responsible to uphold invariants.
sourcepub fn add_terminal(
&mut self,
node: TreeIndex,
label: Label,
aff: AffFunc
) -> TreeIndex
pub fn add_terminal( &mut self, node: TreeIndex, label: Label, aff: AffFunc ) -> TreeIndex
Adds a single terminal to the graph directly.
Use with caution: Caller is responsible to uphold invariants.
sourcepub fn add_decision(
&mut self,
node: TreeIndex,
label: Label,
aff: AffFunc
) -> TreeIndex
pub fn add_decision( &mut self, node: TreeIndex, label: Label, aff: AffFunc ) -> TreeIndex
Adds a single decision to the graph directly.
Use with caution: Caller is responsible to uphold invariants.
sourcepub fn apply_func_at_node(&mut self, node: TreeIndex, aff: &AffFunc)
pub fn apply_func_at_node(&mut self, node: TreeIndex, aff: &AffFunc)
Applies given function to a single node of the graph. Updates the solution cache.
Use with caution: Caller is responsible to uphold invariants.
sourcepub fn update_node(&mut self, node: TreeIndex, aff: AffFunc) -> Option<AffFunc>
pub fn update_node(&mut self, node: TreeIndex, aff: AffFunc) -> Option<AffFunc>
Overwrite the currently stored function at node
to aff
and return the
previously stored function.
Does not reset the solution cache.
Use with caution: Caller is responsible to uphold invariants.
sourcepub fn replace_node(&mut self, node_idx: TreeIndex, aff: AffFunc) -> TreeIndex
pub fn replace_node(&mut self, node_idx: TreeIndex, aff: AffFunc) -> TreeIndex
Sets given function of a single node of the graph and removes all descendants of original node.
Use with caution: Caller is responsible to uphold invariants.
sourcepub fn apply_func(&mut self, aff_func: &AffFunc)
pub fn apply_func(&mut self, aff_func: &AffFunc)
Combines this tree with the specified aff_func
by composing aff_func
to the left of all terminal nodes of this tree.
This is semantically equivalent to first evaluating this tree and then applying aff_func
to the output.
pub fn apply_partial_relu_at_node(&mut self, node: TreeIndex, relu_dim: usize)
sourcepub fn evaluate(&self, input: &Array1<f64>) -> Option<Array1<f64>>
pub fn evaluate(&self, input: &Array1<f64>) -> Option<Array1<f64>>
Evaluates this AffTree instance under the given input
.
If a maximal iteration number is reached, this function returns None
.
§Panics
If the input does not evaluate to a terminal node of this tree.
sourcepub fn evaluate_to_terminal<'a>(
&'a self,
node: &'a AffNode<K>,
input: &Array1<f64>,
max_iter: i32
) -> Option<(&AffFunc, Vec<Label>)>
pub fn evaluate_to_terminal<'a>( &'a self, node: &'a AffNode<K>, input: &Array1<f64>, max_iter: i32 ) -> Option<(&AffFunc, Vec<Label>)>
Evaluates this AffTree instance under the given input
, returning the corresponding terminal node.
The evaluation is started at the given node
to a maximum depth of max_iter
.
§Panics
If the input does not evaluate to a terminal node of this tree.
pub fn evaluate_node(&self, node: &AffNode<K>, input: &Array1<f64>) -> Label
sourcepub fn remove_axes(&mut self, mask: &Array1<bool>)
pub fn remove_axes(&mut self, mask: &Array1<bool>)
Removes the specified axes from this afftree.
Keeps the input axes where mask
is True and removes all others in the whole tree.
Note: Marked axes are silently dropped, which alters the represented piece-wise linear function. Best used in combination with slicing.
sourcepub fn compose<const PRUNE: bool>(&mut self, other: &AffTree<K>)
pub fn compose<const PRUNE: bool>(&mut self, other: &AffTree<K>)
Extends self such that it represents the result of mathematical function composition of this tree and other.
§Example
use affinitree::{aff, pwl::afftree::AffTree};
use ndarray::arr1;
let mut tree0 = AffTree::<2>::from_aff(aff!([[1., 0.]] + [2.]));
tree0.add_child_node(0, 0, aff!([[2, 0], [0, 2]] + [1, 0]));
tree0.add_child_node(0, 1, aff!([[2, 0], [0, 2]] + [0, 1]));
let mut tree1 = AffTree::<2>::from_aff(aff!([[-0.5, 0.]] + [-1.]));
tree1.add_child_node(0, 0, aff!([[3, 0], [0, 3]] + [5, 0]));
tree1.add_child_node(0, 1, aff!([[-3, 0], [0, -3]] + [0, 5]));
let mut comp = tree0.clone();
comp.compose::<false>(&tree1);
assert_eq!(
tree1.evaluate(&tree0.evaluate(&arr1(&[2., -7.])).unwrap()).unwrap(),
comp.evaluate(&arr1(&[2., -7.])).unwrap()
);
pub fn compose_trees(lhs: &AffTree<K>, rhs: &mut AffTree<K>)
sourcepub fn lift_func<I, NFn, TFn, IFn>(
lhs: &AffTree<K>,
rhs: &mut AffTree<K>,
terminals: I,
nonterminal_func: NFn,
terminal_func: TFn,
is_feasible: IFn
)
pub fn lift_func<I, NFn, TFn, IFn>( lhs: &AffTree<K>, rhs: &mut AffTree<K>, terminals: I, nonterminal_func: NFn, terminal_func: TFn, is_feasible: IFn )
Apply the function f encoded by lhs to rhs. Technically, this is implemented by appending a copy of lhs to every terminal in rhs. Two callbacks are provided that can update nodes depending on the operation performed, thus allowing to encode a variety of functions.
Each inner node in lhs is updated with the callback nonterminal_func which receives the current inner node of lhs and the terminal node of rhs where this copy is appended. Each terminal node in lhs is updated with the callback terminal_func which receives the current terminal node of lhs and the terminal node of rhs where this copy is appended.
sourcepub fn mirror_points(
poly: &Polytope,
points: &Array2<f64>,
n_iterations: usize
) -> Option<Array2<f64>>
pub fn mirror_points( poly: &Polytope, points: &Array2<f64>, n_iterations: usize ) -> Option<Array2<f64>>
Tries to derive solutions for poly
based on the given points
.
This function iteratively maximizes the signed distance of each point to each of the
supporting hyperplanes of poly
. When all distances are positive, the point lies
inside the polytope and is thus a solution.
This is a heuristic that ignores the interaction between the hyperplanes for improved speed
at the cost of completeness.
If after n_iterations
no solution is found, None
is returned.
Otherwise, if at any point a valid solution is found, the function returns all valid solutions up to that point.
The first iteration corresponds to a simple containment check.
The columns of points
and of the return value represent the points.
pub fn merge_child_with_parent( &mut self, parent_idx: usize, label: Label ) -> Option<TreeNode<AffContent, K>>
sourcepub fn forward_if_redundant(
&mut self,
parent_idx: usize
) -> Option<TreeNode<AffContent, K>>
pub fn forward_if_redundant( &mut self, parent_idx: usize ) -> Option<TreeNode<AffContent, K>>
Skips over redundant predicates in the tree.
§Warning
This function can alter the semantics of tree by removing paths that would otherwise result in errors. It is up to the caller to ensure that this behavior is either impossible (e.g., when all such paths are infeasible) or that this is indeed the intended effect.
sourcepub fn infeasible_elimination(&mut self)
pub fn infeasible_elimination(&mut self)
Removes nodes from this tree that lie on infeasible paths.
In a decision structure a path is called infeasible when the conjunction of all decisions on that path is not satisfiable. As no input could ever take such a path, these can be safely removed from the decision structure without altering its semantics (i.e., without changing the represented piece-wise linear function).
sourcepub fn is_edge_feasible(&self, parent_idx: usize, node_idx: usize) -> bool
pub fn is_edge_feasible(&self, parent_idx: usize, node_idx: usize) -> bool
Test if the edge from parent_idx
to node_idx
is feasible.
Deprecated: use AffTree::infeasible_elimination
to prune infeasible paths instead.