tree_dp_example.cc File Reference

Illustrated tree DP + rerooting walkthrough. More...

#include <iostream>
#include <iomanip>
#include <array>
#include <Tree_DP.H>
#include <print_rule.H>

Include dependency graph for tree_dp_example.cc:

Go to the source code of this file.

Typedefs
using	G = List_Graph< Graph_Node< int >, Graph_Arc< int > >

Functions
int	main ()
	Example program demonstrating tree dynamic programming (DP) and rerooting DP.

Detailed Description

Illustrated tree DP + rerooting walkthrough.

Definition in file tree_dp_example.cc.

Typedef Documentation

G

using G = List_Graph<Graph_Node<int>, Graph_Arc<int> >

Definition at line 46 of file tree_dp_example.cc.

Function Documentation

main()

int main

(

)

Example program demonstrating tree dynamic programming (DP) and rerooting DP.

Builds a fixed rooted tree and demonstrates two types of DP:

1. Gen_Tree_DP: Bottom-up computation (subtree sizes, subtree value sums).
2. Gen_Reroot_DP: Computation of metrics as if each node were the root (eccentricity/max distance and sum of distances to all other nodes).

Prints a formatted table of these per-node metrics.

Returns

int 0 on successful completion.

Definition at line 60 of file tree_dp_example.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), nodes, Aleph::print_rule(), Aleph::tree_max_distance(), Aleph::tree_subtree_sizes(), Aleph::tree_sum_of_distances(), and Aleph::Gen_Tree_DP< GT, T, SA >::value().