Generic bottom-up tree DP. More...

#include <Tree_DP.H>

Collaboration diagram for Aleph::Gen_Tree_DP< GT, T, SA >:

Public Types
using	Node = typename GT::Node
	Node type.

using	Init_Fn = std::function< T(Node *)>
	Initialization function: maps a leaf/node to its base value.

using	Combine_Fn = std::function< T(Node , const T &, Node , const T &)>
	Combine function: folds a child's value into the accumulator.

Public Member Functions
	Gen_Tree_DP (const GT &g, Node *root, Init_Fn init, Combine_Fn combine, SA sa=SA())
	Construct and compute bottom-up DP.

const T &	value (Node *node) const
	Returns the DP value for a given node.

const Array< T > &	values () const noexcept
	Returns all DP values (indexed by internal node ID).

size_t	size () const noexcept
	Returns the number of nodes in the tree.

Node *	node_of (size_t id) const
	Returns the node pointer for a given internal ID.

size_t	id_of (Node *node) const
	Returns the internal ID for a given node pointer.

Private Attributes
tree_dp_detail::Tree_Topology< GT, SA >	topo_
	Tree topology and order.

Array< T >	dp_
	Computed DP values.

Detailed Description

template<class GT, typename T, class SA = Dft_Show_Arc<GT>>
class Aleph::Gen_Tree_DP< GT, T, SA >

Generic bottom-up tree DP.

Computes a value for each node by combining children's values in post-order.

Template Parameters

GT	Graph type.
T	Value type computed at each node.
SA	Arc filter (default Dft_Show_Arc).

Usage: Gen_Tree_DP<G, size_t> dp(g, root,

[](auto *) { return 1; }, // init: each node counts 1

[](auto *, const size_t & acc, auto *, const size_t & child_val) {

return acc + child_val; // combine: sum children

});

size_t subtree_size = dp.value(some_node);

Aleph::Gen_Tree_DP
Generic bottom-up tree DP.
Definition Tree_DP.H:333

Aleph::Gen_Tree_DP::value
const T & value(Node *node) const
Returns the DP value for a given node.
Definition Tree_DP.H:391

root
__gmp_expr< T, __gmp_binary_expr< __gmp_expr< T, U >, unsigned long int, __gmp_root_function > > root(const __gmp_expr< T, U > &expr, unsigned long int l)
Definition gmpfrxx.h:4060

Aleph::divide_and_conquer_partition_dp
Divide_Conquer_DP_Result< Cost > divide_and_conquer_partition_dp(const size_t groups, const size_t n, Transition_Cost_Fn transition_cost, const Cost inf=dp_optimization_detail::default_inf< Cost >())
Optimize partition DP using divide-and-conquer optimization.
Definition DP_Optimizations.H:133

Note: Complexity: O(n) time and space for the DP computation (after O(n) tree preprocessing).

Examples: tree_dp_example.cc.

Definition at line 332 of file Tree_DP.H.

Member Typedef Documentation

◆ Combine_Fn

template<class GT , typename T , class SA = Dft_Show_Arc<GT>>

using Aleph::Gen_Tree_DP< GT, T, SA >::Combine_Fn = std::function<T(Node *, const T &, Node *, const T &)>

Combine function: folds a child's value into the accumulator.

Parameters: (parent_node, accumulated_value, child_node, child_dp_value) Returns: new accumulated value.

Definition at line 345 of file Tree_DP.H.

◆ Init_Fn

template<class GT , typename T , class SA = Dft_Show_Arc<GT>>

using Aleph::Gen_Tree_DP< GT, T, SA >::Init_Fn = std::function<T(Node *)>

Initialization function: maps a leaf/node to its base value.

Definition at line 338 of file Tree_DP.H.

◆ Node

template<class GT , typename T , class SA = Dft_Show_Arc<GT>>

using Aleph::Gen_Tree_DP< GT, T, SA >::Node = typename GT::Node

Node type.

Definition at line 335 of file Tree_DP.H.

Constructor & Destructor Documentation

◆ Gen_Tree_DP()

template<class GT , typename T , class SA = Dft_Show_Arc<GT>>

Aleph::Gen_Tree_DP< GT, T, SA >::Gen_Tree_DP	(	const GT &	g,
		Node *	root,
		Init_Fn	init,
		Combine_Fn	combine,
		SA	sa = `SA()`
	)

inline

Construct and compute bottom-up DP.

Parameters

[in]	g	The graph (must be a tree under filter SA).
[in]	root	Root node.
[in]	init	Initialization function for each node.
[in]	combine	Combine function to fold children.
[in]	sa	Arc filter.

Definition at line 360 of file Tree_DP.H.

References Aleph::Array< T >::create(), Aleph::Gen_Tree_DP< GT, T, SA >::dp_, Aleph::init, k, and Aleph::Gen_Tree_DP< GT, T, SA >::topo_.

Member Function Documentation

◆ id_of()

template<class GT , typename T , class SA = Dft_Show_Arc<GT>>

size_t Aleph::Gen_Tree_DP< GT, T, SA >::id_of ( Node * node ) const

inline

Returns the internal ID for a given node pointer.

Parameters

[in] node Node pointer.

Returns: Internal node ID.

Definition at line 421 of file Tree_DP.H.

References Aleph::Gen_Tree_DP< GT, T, SA >::topo_.

Referenced by TEST().

◆ node_of()

template<class GT , typename T , class SA = Dft_Show_Arc<GT>>

Node * Aleph::Gen_Tree_DP< GT, T, SA >::node_of ( size_t id ) const

inline

Returns the node pointer for a given internal ID.

Parameters

[in] id Internal node ID.

Returns: Node pointer.

Definition at line 412 of file Tree_DP.H.

References Aleph::Gen_Tree_DP< GT, T, SA >::topo_.

◆ size()

template<class GT , typename T , class SA = Dft_Show_Arc<GT>>

size_t Aleph::Gen_Tree_DP< GT, T, SA >::size ( ) const

inlinenoexcept

Returns the number of nodes in the tree.

Definition at line 403 of file Tree_DP.H.

References Aleph::Gen_Tree_DP< GT, T, SA >::topo_.

◆ value()

template<class GT , typename T , class SA = Dft_Show_Arc<GT>>

const T & Aleph::Gen_Tree_DP< GT, T, SA >::value ( Node * node ) const

inline

Returns the DP value for a given node.

Parameters

[in] node Node pointer.

Returns: Constant reference to the computed DP value.

Examples: tree_dp_example.cc.

Definition at line 391 of file Tree_DP.H.

References Aleph::Gen_Tree_DP< GT, T, SA >::dp_, and Aleph::Gen_Tree_DP< GT, T, SA >::topo_.

Referenced by main().

◆ values()

template<class GT , typename T , class SA = Dft_Show_Arc<GT>>

const Array< T > & Aleph::Gen_Tree_DP< GT, T, SA >::values ( ) const

inlinenoexcept

Returns all DP values (indexed by internal node ID).

Definition at line 397 of file Tree_DP.H.

References Aleph::Gen_Tree_DP< GT, T, SA >::dp_.

Referenced by Aleph::tree_subtree_sizes().

Member Data Documentation

◆ dp_

template<class GT , typename T , class SA = Dft_Show_Arc<GT>>

Array<T> Aleph::Gen_Tree_DP< GT, T, SA >::dp_

private

Computed DP values.

Definition at line 349 of file Tree_DP.H.

Referenced by Aleph::Gen_Tree_DP< GT, T, SA >::Gen_Tree_DP(), Aleph::Gen_Tree_DP< GT, T, SA >::value(), and Aleph::Gen_Tree_DP< GT, T, SA >::values().

◆ topo_

template<class GT , typename T , class SA = Dft_Show_Arc<GT>>

tree_dp_detail::Tree_Topology<GT, SA> Aleph::Gen_Tree_DP< GT, T, SA >::topo_

private

Tree topology and order.

Definition at line 348 of file Tree_DP.H.

Referenced by Aleph::Gen_Tree_DP< GT, T, SA >::Gen_Tree_DP(), Aleph::Gen_Tree_DP< GT, T, SA >::id_of(), Aleph::Gen_Tree_DP< GT, T, SA >::node_of(), Aleph::Gen_Tree_DP< GT, T, SA >::size(), and Aleph::Gen_Tree_DP< GT, T, SA >::value().

The documentation for this class was generated from the following file:

Tree_DP.H

Public Types

Public Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ Combine_Fn

◆ Init_Fn

◆ Node

Constructor & Destructor Documentation

◆ Gen_Tree_DP()

Member Function Documentation

◆ id_of()

◆ node_of()

◆ size()

◆ value()

◆ values()

Member Data Documentation

◆ dp_

◆ topo_