Generic bottom-up tree dynamic programming. 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 signature.

using	Combine_Fn = std::function< T(Node , const T &, Node , const T &)>
	Combine function signature.

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<AlephGraph GT, typename T, ArcFilter< GT > SA = Dft_Show_Arc<GT>>
class Aleph::Gen_Tree_DP< GT, T, SA >

Generic bottom-up tree dynamic programming.

This class computes a DP value for every node in a rooted tree by combining the results of its children in post-order traversal.

The user defines the logic by providing:

An Init_Fn to set the base value for each node.
A Combine_Fn to merge a child's result into the parent's accumulator.

Template Parameters

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

Complexity: Time O(n), Space O(n), where n is the number of nodes.

Example: Subtree Size: using G = List_Graph<>;

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

[](auto *node) { return 1; }, // Each node starts with size 1

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

return acc + child_val; // Add subtree size of child to parent

});

size_t root_subtree = dp.value(root); // Should be total nodes in the tree

Aleph::Gen_Tree_DP
Generic bottom-up tree dynamic programming.
Definition Tree_DP.H:341

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

Aleph::List_Graph
Graph implemented with double-linked adjacency lists.
Definition tpl_graph.H:429

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:4071

Aleph::blossom_maximum_cardinality_matching
size_t blossom_maximum_cardinality_matching(const GT &g, DynDlist< typename GT::Arc * > &matching, SA sa=SA())
Alias of compute_maximum_cardinality_general_matching().
Definition Blossom.H:466

Examples: tree_dp_example.cc.

Definition at line 340 of file Tree_DP.H.

Member Typedef Documentation

◆ Combine_Fn

template<AlephGraph GT, typename T , ArcFilter< GT > 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 signature.

Merges a child's DP result into the parent's current accumulator. Signature: (parent_node, current_accumulator, child_node, child_result) -> new_accumulator

Definition at line 354 of file Tree_DP.H.

◆ Init_Fn

template<AlephGraph GT, typename T , ArcFilter< GT > SA = Dft_Show_Arc<GT>>

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

Initialization function signature.

Given a node, returns its initial DP value.

Definition at line 348 of file Tree_DP.H.

◆ Node

template<AlephGraph GT, typename T , ArcFilter< GT > SA = Dft_Show_Arc<GT>>

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

Node type.

Definition at line 343 of file Tree_DP.H.

Constructor & Destructor Documentation

◆ Gen_Tree_DP()

template<AlephGraph GT, typename T , ArcFilter< GT > 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 369 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<AlephGraph GT, typename T , ArcFilter< GT > 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 428 of file Tree_DP.H.

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

Referenced by TEST().

◆ node_of()

template<AlephGraph GT, typename T , ArcFilter< GT > 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 419 of file Tree_DP.H.

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

◆ size()

template<AlephGraph GT, typename T , ArcFilter< GT > 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 410 of file Tree_DP.H.

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

◆ value()

template<AlephGraph GT, typename T , ArcFilter< GT > 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 398 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<AlephGraph GT, typename T , ArcFilter< GT > 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 404 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<AlephGraph GT, typename T , ArcFilter< GT > SA = Dft_Show_Arc<GT>>

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

private

Computed DP values.

Definition at line 358 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<AlephGraph GT, typename T , ArcFilter< GT > 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 357 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_