#include <gtest/gtest.h>
#include <limits>
#include <random>
#include <utility>
#include <Tree_DP.H>

Include dependency graph for tree_dp_test.cc:

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

Functions
static G	build_path (size_t n, Array< G::Node * > &nodes)

static G	build_star (size_t n, Array< G::Node * > &nodes)

	TEST (TreeDP, SubtreeSizes_Path)

	TEST (TreeDP, SubtreeSizes_Star)

	TEST (TreeDP, SubtreeSizes_SingleNode)

	TEST (TreeDP, MaxDistance_Path)

	TEST (TreeDP, MaxDistance_Star)

	TEST (TreeDP, SumOfDistances_Path)

	TEST (TreeDP, NotATree)

	TEST (TreeDP, DisconnectedGraph)

	TEST (TreeDP, RootNotInGraph)

	TEST (TreeDP, ParallelEdgesAreIgnored)

	TEST (TreeDP, BinaryTree)

	TEST (TreeDP, RandomSumOfDistancesVsBfs)

Detailed Description

Tests for Tree_DP.H.

Definition in file tree_dp_test.cc.

Typedef Documentation

◆ G

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

Definition at line 47 of file tree_dp_test.cc.

Function Documentation

◆ build_path()

static G build_path	(	size_t	n,
		Array< G::Node * > &	nodes
	)

static

Definition at line 103 of file tree_dp_test.cc.

References Aleph::Array< T >::create(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), and nodes.

Referenced by TEST(), TEST(), and TEST().

◆ build_star()

static G build_star	(	size_t	n,
		Array< G::Node * > &	nodes
	)

static

Definition at line 115 of file tree_dp_test.cc.

References Aleph::Array< T >::create(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), and nodes.

Referenced by TEST(), and TEST().

◆ TEST() [1/12]

TEST	(	TreeDP	,
		BinaryTree
	)

Definition at line 315 of file tree_dp_test.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), and Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node().

◆ TEST() [2/12]

TEST	(	TreeDP	,
		DisconnectedGraph
	)

Definition at line 271 of file tree_dp_test.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(), and Aleph::tree_subtree_sizes().

◆ TEST() [3/12]

TEST	(	TreeDP	,
		MaxDistance_Path
	)

Definition at line 178 of file tree_dp_test.cc.

References build_path(), Aleph::divide_and_conquer_partition_dp(), nodes, and Aleph::tree_max_distance().

◆ TEST() [4/12]

TEST	(	TreeDP	,
		MaxDistance_Star
	)

Definition at line 205 of file tree_dp_test.cc.

References build_star(), Aleph::divide_and_conquer_partition_dp(), and nodes.

◆ TEST() [5/12]

TEST	(	TreeDP	,
		NotATree
	)

Definition at line 257 of file tree_dp_test.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(), and Aleph::tree_subtree_sizes().

◆ TEST() [6/12]

TEST	(	TreeDP	,
		ParallelEdgesAreIgnored
	)

Definition at line 294 of file tree_dp_test.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), and Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node().

◆ TEST() [7/12]

TEST	(	TreeDP	,
		RandomSumOfDistancesVsBfs
	)

Definition at line 346 of file tree_dp_test.cc.

References Aleph::Array< T >::append(), Aleph::Array< T >::create(), Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Tree_DP< GT, T, SA >::id_of(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), nodes, Aleph::Array< T >::reserve(), rng, and Aleph::tree_sum_of_distances().

◆ TEST() [8/12]

TEST	(	TreeDP	,
		RootNotInGraph
	)

Definition at line 283 of file tree_dp_test.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), and Aleph::tree_subtree_sizes().

◆ TEST() [9/12]

TEST	(	TreeDP	,
		SubtreeSizes_Path
	)

Definition at line 129 of file tree_dp_test.cc.

References build_path(), Aleph::divide_and_conquer_partition_dp(), nodes, and Aleph::tree_subtree_sizes().

◆ TEST() [10/12]

TEST	(	TreeDP	,
		SubtreeSizes_SingleNode
	)

Definition at line 166 of file tree_dp_test.cc.