Generic rerooting dynamic programming (all-roots DP). More...

#include <Tree_DP.H>

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

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

using	Init_Fn = std::function< T(Node *)>
	Initialization function signature.

using	Merge_Fn = std::function< T(const T &, const T &)>
	Merge function signature.

using	Apply_Edge_Fn = std::function< T(Node , Node , const T &)>
	Edge transformation signature.

Public Member Functions
	Gen_Reroot_DP (const GT &g, Node *root, const T &identity, Init_Fn init, Merge_Fn merge, Apply_Edge_Fn apply_edge, SA sa=SA())
	Construct and compute rerooting DP.

const T &	value (Node *node) const
	Returns the answer for a given node as root.

const Array< T > &	values () const noexcept
	Returns all computed answers (indexed by internal 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.

T	identity_
	Identity for merge operation.

Array< T >	init_vals_
	Cached per-node base values.

Array< T >	dp_down_
	Bottom-up DP results.

Array< T >	dp_up_
	Top-down contribution from parent side.

Array< T >	answer_
	Final answer for each node as root.

Detailed Description

template<AlephGraph GT, typename T, ArcFilter< GT > SA = Dft_Show_Arc<GT>>
class Aleph::Gen_Reroot_DP< GT, T, SA >

Generic rerooting dynamic programming (all-roots DP).

Efficiently computes a DP answer for every node in the tree as if each node were the root.

Standard bottom-up DP only gives the answer for a fixed root. Rerooting DP achieves the all-roots result in O(n) by performing:

A bottom-up pass: Computes "downward" values for a fixed root.
A top-down pass: Combines downward results with prefix/suffix merges to compute "upward" (parent-side) contributions.

The user provides:

identity: Neutral element for the merge operation.
init: Base value for a single node.
merge: Associative operation to combine results from children.
apply_edge: Function to transform a subtree's result when passing through an edge to the parent.

Template Parameters

Example: Tree Diameter / Eccentricities: Gen_Reroot_DP<G, size_t> dp(g, some_root,

0, // identity

[](auto *n) { return 0; }, // init: leaf distance is 0

[](size_t a, size_t b) { return std::max(a, b); }, // merge max

[](auto *p, auto *c, size_t val) { return val + 1; } // apply edge: dist+1

);

size_t max_dist_from_v = dp.value(v); // Max distance from v to any leaf

Aleph::Gen_Reroot_DP
Generic rerooting dynamic programming (all-roots DP).
Definition Tree_DP.H:479

Aleph::Gen_Reroot_DP::value
const T & value(Node *node) const
Returns the answer for a given node as root.
Definition Tree_DP.H:611

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

Definition at line 478 of file Tree_DP.H.