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 the children value. |
|
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 pseudo-code 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, condition=None)[source]¶ Sequentially propagates parent values to children and accumulates with the children value.
The root value is defined as:
\(output(root) = accumulator(node\_weights(root))\) if \(condition(root)\); and
\(output(root) = node\_weights(root)\) otherwise.
Then for each node \(i\) from the root (excluded) to the leaves:
\(output(i) = accumulator(node\_weights(i), output(parent(i)))\) if \(condition(i)\); and
\(output(i) = node\_weights(i)\) otherwise .
If the condition array is not provided, then \(condition(i)=true\) for every node \(i\).
- Parameters:
tree – input tree
node_weights – Weights on the nodes of the tree
accumulator – see
Accumulators
condition – Boolean array on the nodes of the tree (optional)
- 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