Rerooting DP: O(n) computation of DP answer for all roots. 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: base contribution of a node.

using	Merge_Fn = std::function< T(const T &, const T &)>
	Merge function: associative binary operation to combine results.

using	Apply_Edge_Fn = std::function< T(Node , Node , const T &)>
	Edge transformation function: applies edge effects to a subtree result.

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

Rerooting DP: O(n) computation of DP answer for all roots.

Uses prefix/suffix merges to efficiently compute the DP value as if each node were the root.

The user provides:

identity: neutral element for merge
init: base value for a node (leaf contribution)
merge: associative binary operation to combine child contributions
apply_edge: transforms a child's contribution when passing through an edge (parent, child, child_merged_value) -> contribution

Template Parameters

Example: Sum of distances from every node: // Each node's answer = sum of distances to all other nodes.

// Here T is a pair (count, sum_dist).

Definition at line 461 of file Tree_DP.H.

Member Typedef Documentation

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

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

Edge transformation function: applies edge effects to a subtree result.

Parameters: (parent_node, child_node, subtree_value) Returns: contribution to parent's DP.

Definition at line 477 of file Tree_DP.H.

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

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

Initialization function: base contribution of a node.

Definition at line 467 of file Tree_DP.H.

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

using Aleph::Gen_Reroot_DP< GT, T, SA >::Merge_Fn = std::function<T(const T &, const T &)>

Merge function: associative binary operation to combine results.

Definition at line 470 of file Tree_DP.H.

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

Node type.

Definition at line 464 of file Tree_DP.H.

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

Aleph::Gen_Reroot_DP< GT, T, SA >::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()`
	)

inline

Construct and compute rerooting DP.

Parameters

[in]	g	The graph (tree under SA).
[in]	root	Initial root for bottom-up pass.
[in]	identity	Neutral element for merge.
[in]	init	Base value for each node.
[in]	merge	Associative merge operation.
[in]	apply_edge	Transform child value across an edge.
[in]	sa	Arc filter.