Tree_DP.H File Reference

Generic tree dynamic programming and rerooting algorithms. More...

#include <ah-graph-concepts.H>
#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 >
	Pre-processes and extracts tree topology from a graph. More...
class	Aleph::Gen_Tree_DP< GT, T, SA >
	Generic bottom-up tree dynamic programming. More...
class	Aleph::Gen_Reroot_DP< GT, T, SA >
	Generic rerooting dynamic programming (all-roots DP). 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<AlephGraph GT, ArcFilter< GT > 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<AlephGraph GT, ArcFilter< GT > 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<AlephGraph GT, ArcFilter< GT > 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 dynamic programming and rerooting algorithms.

Provides a powerful framework for solving dynamic programming problems on trees represented as Aleph graphs.

Two main patterns are supported:

• Bottom-up Tree DP: Standard DP that computes values from leaves up to the root. Useful for subtree-related queries (size, height, etc.).
• Rerooting DP: An O(n) technique that computes the answer for every node as if it were the root of the tree. This is achieved through two passes (bottom-up and top-down) using prefix and suffix combinations.

Additionally, high-level convenience functions are provided for common queries like subtree sizes and tree diameters.

Definition in file Tree_DP.H.