Utility functions move and accumulates values along trees¶

Propagates parent values to children: for each node \(i\), if \(condition(i)\) then \(output(i) = node\_weights(tree.parent(i))\) otherwise \(output(i) = node\_weights(i)\). 

Sequentially propagates parent values to children: for each node \(i\) from the root to the leaves, if \(i\) is not the root and if \(condition(i)\) then \(output(i) = output(tree.parent(i))\) otherwise \(output(i) = node\_weights(i)\). 

Sequentially propagates parent values to children and accumulates with current value: for each node \(i\) from the root to the leaves, \(output(i) = accumulator(node\_weights(i), output(parent(i)))\). 

Accumulates values of the children of every node \(i\) in the \(node\_weights\) array and puts the result in output: \(output(i) = accumulator(node\_weights(children(i)))\) 

Sequential accumulation of node values from the leaves to the root. 

Accumulates node values from the leaves to the root and add the result with the input array. 

Accumulates node values from the leaves to the root and multiply the result with the input array. 

Accumulates node values from the leaves to the root and takes the maximum of result and the input array. 

Accumulates node values from the leaves to the root and takes the minimum of result and the input array. 

For each edge of the leaf graph, accumulates the weights of the nodes whose contour pass by this edge. 

propagate_parallel
(tree, node_weights, condition=None)[source]¶ Propagates parent values to children: for each node \(i\), if \(condition(i)\) then \(output(i) = node\_weights(tree.parent(i))\) otherwise \(output(i) = node\_weights(i)\).
The conditional parallel propagator pseudocode could be:
# input: a tree t # input: an attribute att on the nodes of t # input: a condition cond on the nodes of t output = copy(input) for each node n of t: if(cond(n)): output[n] = input[t.parent(n)] return output
 Parameters
tree – input tree
node_weights – Weights on the nodes of the tree
condition – Boolean array on the nodes of the tree
 Returns
returns new tree node weights

propagate_sequential
(tree, node_weights, condition)[source]¶ Sequentially propagates parent values to children: for each node \(i\) from the root to the leaves, if \(i\) is not the root and if \(condition(i)\) then \(output(i) = output(tree.parent(i))\) otherwise \(output(i) = node\_weights(i)\).
 Parameters
tree – input tree
node_weights – Weights on the nodes of the tree
condition – Boolean array on the nodes of the tree
 Returns
returns new tree node weights

propagate_sequential_and_accumulate
(tree, node_weights, accumulator)[source]¶ Sequentially propagates parent values to children and accumulates with current value: for each node \(i\) from the root to the leaves, \(output(i) = accumulator(node\_weights(i), output(parent(i)))\).
 Parameters
tree – input tree
node_weights – Weights on the nodes of the tree
accumulator – see
Accumulators
 Returns
returns new tree node weights

accumulate_parallel
(tree, node_weights, accumulator)[source]¶ Accumulates values of the children of every node \(i\) in the \(node\_weights\) array and puts the result in output: \(output(i) = accumulator(node\_weights(children(i)))\)
 Parameters
tree – input tree
node_weights – Weights on the nodes of the tree
accumulator – see
Accumulators
 Returns
returns new tree node weights

accumulate_sequential
(tree, leaf_data, accumulator, leaf_graph=None)[source]¶ Sequential accumulation of node values from the leaves to the root. For each leaf node \(i\), \(output(i) = leaf_data(i)\). For each node \(i\) from the leaves (excluded) to the root, \(output(i) = accumulator(output(children(i)))\)
 Parameters
tree – input tree (Concept
CptHierarchy
)leaf_data – array of weights on the leaves of the tree
accumulator – see
Accumulators
leaf_graph – graph of the tree leaves (optional, deduced from
CptHierarchy
)
 Returns
returns new tree node weights

accumulate_and_add_sequential
(tree, node_weights, leaf_data, accumulator, leaf_graph=None)[source]¶ Accumulates node values from the leaves to the root and add the result with the input array.
For each leaf node \(i\), output(i) = \(leaf\_data(i)\). For each node \(i\) from the leaves (excluded) to the root, \(output(i) = input(i) + accumulator(output(children(i)))\)
 Parameters
tree – input tree (Concept
CptHierarchy
)node_weights – Weights on the nodes of the tree
leaf_data – Weights on the leaves of the tree
accumulator – see
Accumulators
leaf_graph – graph of the tree leaves (optional, deduced from
CptHierarchy
)
 Returns
returns new tree node weights

accumulate_and_multiply_sequential
(tree, node_weights, leaf_data, accumulator, leaf_graph=None)[source]¶ Accumulates node values from the leaves to the root and multiply the result with the input array.
For each leaf node \(i\), \(output(i) = leaf_data(i)\). For each node \(i\) from the leaves (excluded) to the root, \(output(i) = input(i) + accumulator(output(children(i)))\)
 Parameters
tree – input tree (Concept
CptHierarchy
)node_weights – Weights on the nodes of the tree
leaf_data – Weights on the leaves of the tree
accumulator – see
Accumulators
leaf_graph – graph of the tree leaves (optional (optional, deduced from
CptHierarchy
))
 Returns
returns new tree node weights

accumulate_and_max_sequential
(tree, node_weights, leaf_data, accumulator, leaf_graph=None)[source]¶ Accumulates node values from the leaves to the root and takes the maximum of result and the input array.
For each leaf node \(i\), \(output(i) = leaf_data(i)\). For each node \(i\) from the leaves (excluded) to the root, \(output(i) = \max(input(i), accumulator(output(children(i)))\)
 Parameters
tree – input tree (Concept
CptHierarchy
)node_weights – Weights on the nodes of the tree
leaf_data – Weights on the leaves of the tree
accumulator – see
Accumulators
leaf_graph – graph of the tree leaves (optional, deduced from
CptHierarchy
)
 Returns
returns new tree node weights

accumulate_and_min_sequential
(tree, node_weights, leaf_data, accumulator, leaf_graph=None)[source]¶ Accumulates node values from the leaves to the root and takes the minimum of result and the input array.
For each leaf node \(i\), \(output(i) = leaf_data(i)\). For each node \(i\) from the leaves (excluded) to the root, \(output(i) = \min(input(i), accumulator(output(children(i)))\)
 Parameters
tree – input tree (Concept
CptHierarchy
)node_weights – Weights on the nodes of the tree
leaf_data – Weights on the leaves of the tree
accumulator – see
Accumulators
leaf_graph – graph of the tree leaves (optional, deduced from
CptHierarchy
)
 Returns
returns new tree node weights

accumulate_on_contours
(tree, node_weights, accumulator, leaf_graph)[source]¶ For each edge of the leaf graph, accumulates the weights of the nodes whose contour pass by this edge.
For any edge \(\{x,y\}\), let \(R_{\{x,y\}}\) be the set of regions of the input tree \(T\) having \(\{x,y\}\) in its contour:
\[R_{\{x,y\}} = \{n \in T \, \, \{x,y\} \cap n = 1 \}\]The output value for the edge \(\{x,y\}\) is then the accumulated weights of the nodes in \(R_{\{x,y\}}\).
 Runtime complexity
This algorithm runs in \(\mathcal{O}(n*k)\) with \(n\) the number of edges in the leaf graph and \(k\) the maximal depth of the tree (i.e. the number of edges on the longest downward path between the root and a leaf).
 Parameters
tree – input tree (Concept
CptHierarchy
)node_weights – weights on the nodes of the tree
accumulator – see
Accumulators
leaf_graph – graph of the tree leaves (deduced from
CptHierarchy
)
 Returns
returns leaf graph edge weights