Tree_DP.H File Reference

Generic tree DP and rerooting DP on Aleph graph trees. More...

#include <algorithm>
#include <cstddef>
#include <functional>
#include <limits>
#include <utility>
#include <ah-errors.H>
#include <tpl_array.H>
#include <tpl_dynListStack.H>
#include <tpl_dynMapOhash.H>
#include <tpl_dynMapTree.H>
#include <tpl_graph.H>

Include dependency graph for Tree_DP.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	Aleph::tree_dp_detail::Tree_Topology< GT, SA >
	Extract tree topology: node indexing, adjacency, parent, order. More...
class	Aleph::Gen_Tree_DP< GT, T, SA >
	Generic bottom-up tree DP. More...
class	Aleph::Gen_Reroot_DP< GT, T, SA >
	Rerooting DP: O(n) computation of DP answer for all roots. More...

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.
namespace	Aleph::tree_dp_detail

Typedefs
template<class GT , typename T , class SA = Dft_Show_Arc<GT>>
using	Aleph::Tree_DP = Gen_Tree_DP< GT, T, SA >
	Convenient alias for Gen_Tree_DP.
template<class GT , typename T , class SA = Dft_Show_Arc<GT>>
using	Aleph::Reroot_DP = Gen_Reroot_DP< GT, T, SA >
	Convenient alias for Gen_Reroot_DP.

Functions
template<class GT , class SA = Dft_Show_Arc<GT>>
Array< size_t >	Aleph::tree_subtree_sizes (const GT &g, typename GT::Node *root, SA sa=SA())
	Compute subtree sizes for every node.
template<class GT , class SA = Dft_Show_Arc<GT>>
Array< size_t >	Aleph::tree_max_distance (const GT &g, typename GT::Node *root, SA sa=SA())
	Compute the maximum distance from each node to any leaf.
template<class GT , class SA = Dft_Show_Arc<GT>>
Array< size_t >	Aleph::tree_sum_of_distances (const GT &g, typename GT::Node *root, SA sa=SA())
	Compute sum of distances from each node to all others.

Detailed Description

Generic tree DP and rerooting DP on Aleph graph trees.

Provides:

• Gen_Tree_DP: bottom-up DP on a rooted tree with user-defined init and combine functions.
• Gen_Reroot_DP: O(n) rerooting DP that computes the answer for every possible root using prefix/suffix merges.
• Convenience functions: subtree sizes, max distance, sum of distances.

Definition in file Tree_DP.H.