Utility functions move and accumulates values along trees

propagate_parallel(tree, node_weights[, …])

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)\).

propagate_sequential(tree, node_weights, …)

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)\).

propagate_sequential_and_accumulate(tree, …)

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)))\).

accumulate_parallel(tree, node_weights, …)

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)))\)

accumulate_sequential(tree, leaf_data, …)

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

accumulate_and_add_sequential(tree, …[, …])

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

accumulate_and_multiply_sequential(tree, …)

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

accumulate_and_max_sequential(tree, …[, …])

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

accumulate_and_min_sequential(tree, …[, …])

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

accumulate_on_contours(tree, node_weights, …)

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)[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