tree_decomposition_test.cc File Reference

Strong tests for Heavy-Light and Centroid decomposition on Aleph graphs. More...

#include <gtest/gtest.h>
#include <Tree_Decomposition.H>
#include <tpl_agraph.H>
#include <tpl_graph.H>
#include <tpl_sgraph.H>
#include <cstddef>
#include <limits>
#include <random>
#include <utility>
#include <vector>
#include "test_graph_helpers.h"

Include dependency graph for tree_decomposition_test.cc:

Go to the source code of this file.

Functions
	TYPED_TEST (TreeDecompositionTypedTest, EmptyGraph)
	TYPED_TEST (TreeDecompositionTypedTest, InvalidGraphsThrow)
	TYPED_TEST (TreeDecompositionTypedTest, ArcFilterSupport)
	TYPED_TEST (TreeDecompositionTypedTest, DeterministicHeavyLightQueries)
	TYPED_TEST (TreeDecompositionTypedTest, RandomHeavyLightAgainstOracle)
	TYPED_TEST (TreeDecompositionTypedTest, CentroidAnnotationsAndDynamicNearest)

Detailed Description

Strong tests for Heavy-Light and Centroid decomposition on Aleph graphs.

Definition in file tree_decomposition_test.cc.

Function Documentation

TYPED_TEST() [1/6]

TYPED_TEST	(	TreeDecompositionTypedTest	,
		ArcFilterSupport
	)

Definition at line 322 of file tree_decomposition_test.cc.

References Aleph::Gen_Centroid_Decomposition< GT, SA >::centroid_root(), Aleph::divide_and_conquer_partition_dp(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::query_path(), and Aleph::Gen_Centroid_Decomposition< GT, SA >::size().

TYPED_TEST() [2/6]

TYPED_TEST	(	TreeDecompositionTypedTest	,
		CentroidAnnotationsAndDynamicNearest
	)

Definition at line 463 of file tree_decomposition_test.cc.

References Aleph::Gen_Centroid_Decomposition< GT, SA >::centroid_ancestors_of_id(), Aleph::Gen_Centroid_Decomposition< GT, SA >::centroid_distances_of_id(), Aleph::Gen_Centroid_Decomposition< GT, SA >::centroid_level_of_id(), Aleph::Gen_Centroid_Decomposition< GT, SA >::centroid_parent_id(), Aleph::Gen_Centroid_Decomposition< GT, SA >::centroid_root(), Aleph::Gen_Centroid_Decomposition< GT, SA >::centroid_root_id(), Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Centroid_Decomposition< GT, SA >::for_each_centroid_ancestor_id(), Aleph::Gen_Centroid_Decomposition< GT, SA >::id_of(), k, nodes, rng, and Aleph::Gen_Centroid_Decomposition< GT, SA >::size().

TYPED_TEST() [3/6]

TYPED_TEST	(	TreeDecompositionTypedTest	,
		DeterministicHeavyLightQueries
	)

Definition at line 354 of file tree_decomposition_test.cc.

References Aleph::divide_and_conquer_partition_dp(), nodes, Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::query_path(), Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::query_subtree(), Aleph::range(), Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::set_node(), and Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::update_node().

TYPED_TEST() [4/6]

TYPED_TEST	(	TreeDecompositionTypedTest	,
		EmptyGraph
	)

Definition at line 246 of file tree_decomposition_test.cc.

References Aleph::Gen_Centroid_Decomposition< GT, SA >::centroid_root(), Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Centroid_Decomposition< GT, SA >::for_each_centroid_ancestor_id(), Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::is_empty(), Aleph::Gen_Centroid_Decomposition< GT, SA >::is_empty(), Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::query_path_id(), and Aleph::Gen_Centroid_Decomposition< GT, SA >::size().

TYPED_TEST() [5/6]

TYPED_TEST	(	TreeDecompositionTypedTest	,
		InvalidGraphsThrow
	)

Definition at line 271 of file tree_decomposition_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().

TYPED_TEST() [6/6]

TYPED_TEST	(	TreeDecompositionTypedTest	,
		RandomHeavyLightAgainstOracle
	)

Definition at line 401 of file tree_decomposition_test.cc.

References Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::decomposition(), Aleph::divide_and_conquer_partition_dp(), nodes, Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::query_path(), Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::query_subtree(), rng, Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::set_node(), Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::update_node(), and w.