test_zero_one_bfs.cc File Reference

Comprehensive tests for Zero_One_BFS.H. More...

#include <gtest/gtest.h>
#include <Zero_One_BFS.H>
#include <Dijkstra.H>
#include <tpl_graph.H>
#include <tpl_sgraph.H>
#include <tpl_agraph.H>

Include dependency graph for test_zero_one_bfs.cc:

Go to the source code of this file.

Typedefs
using	GT = List_Graph< Graph_Node< int >, Graph_Arc< int > >
using	Node = GT::Node
using	Arc = GT::Arc
using	DGT = List_Digraph< Graph_Node< int >, Graph_Arc< int > >
using	DNode = DGT::Node
using	DArc = DGT::Arc

Functions
	TEST (ZeroOneBFS, BasicShortestPath)
	TEST (ZeroOneBFS, AllZeroWeights)
	TEST (ZeroOneBFS, AllOneWeights)
	TEST (ZeroOneBFS, PathToSelf)
	TEST (ZeroOneBFS, NoPathExists)
	TEST (ZeroOneBFS, SingleNode)
	TEST (ZeroOneBFS, LinearChain)
	TEST (ZeroOneBFS, ZeroWeightShortcut)
	TEST (ZeroOneBFS, NullNodeValidation)
	TEST (ZeroOneBFS, EmptyGraphValidation)
	TEST (ZeroOneBFS, InvalidWeightValidation)
	TEST (ZeroOneBFS, PaintAndGetMinPath)
	TEST (ZeroOneBFS, GetDistanceAfterPainting)
	TEST (ZeroOneBFS, GetDistanceBeforePainting)
	TEST (ZeroOneBFS, PathNodeVerification)
	TEST (ZeroOneBFS, CompleteGraphK4)
	TEST (ZeroOneBFS, GraphWithCycle)
	TEST (ZeroOneBFS, DigraphBasic)
	TEST (ZeroOneBFS, DigraphNoReversePath)
	TEST (ZeroOneBFS, MultipleComputations)
	TEST (ZeroOneBFS, LargeLinearGraph)
	TEST (ZeroOneBFS, CrossValidationWithDijkstra)
	TEST (ZeroOneBFS, StarGraph)
	TEST (ZeroOneBFS, GridExample)
	TEST (ZeroOneBFS, TwoNodeZeroWeight)
	TEST (ZeroOneBFS, TwoNodeOneWeight)
	TEST (ZeroOneBFS, NegativeWeightValidation)
	TEST (ZeroOneBFS, StateGetters)
	TEST (ZeroOneBFS, DisconnectedPainting)
	TEST (ZeroOneBFS, LargeGraphManyZeros)
	TEST (ZeroOneBFS, ParallelEdgesKeepSingleParentArcMarked)
	TEST (ZeroOneBFS, DestructorRestoresGraphState)

Detailed Description

Comprehensive tests for Zero_One_BFS.H.

Tests cover correctness, edge cases, validation, and cross-checks against Dijkstra's algorithm for 0-1 weighted graphs.

Definition in file test_zero_one_bfs.cc.

Typedef Documentation

Arc

using Arc = GT::Arc

Definition at line 25 of file test_zero_one_bfs.cc.

DArc

using DArc = DGT::Arc

Definition at line 30 of file test_zero_one_bfs.cc.

DGT

using DGT = List_Digraph<Graph_Node<int>, Graph_Arc<int> >

Definition at line 28 of file test_zero_one_bfs.cc.

DNode

using DNode = DGT::Node

Definition at line 29 of file test_zero_one_bfs.cc.

GT

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

Definition at line 23 of file test_zero_one_bfs.cc.

Node

using Node = GT::Node

Definition at line 24 of file test_zero_one_bfs.cc.

Function Documentation

TEST() [1/32]

TEST	(	ZeroOneBFS	,
		AllOneWeights
	)

Definition at line 82 of file test_zero_one_bfs.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/32]

TEST	(	ZeroOneBFS	,
		AllZeroWeights
	)

Definition at line 60 of file test_zero_one_bfs.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() [3/32]

TEST	(	ZeroOneBFS	,
		BasicShortestPath
	)

Definition at line 35 of file test_zero_one_bfs.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::Path< GT >::is_empty().

TEST() [4/32]

TEST	(	ZeroOneBFS	,
		CompleteGraphK4
	)

Definition at line 362 of file test_zero_one_bfs.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() [5/32]

TEST	(	ZeroOneBFS	,
		CrossValidationWithDijkstra
	)

Definition at line 504 of file test_zero_one_bfs.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() [6/32]

TEST	(	ZeroOneBFS	,
		DestructorRestoresGraphState
	)

Definition at line 780 of file test_zero_one_bfs.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(), IS_ARC_VISITED, IS_NODE_VISITED, NODE_COOKIE, Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::paint_min_paths_tree(), and Aleph::Spanning_Tree.

TEST() [7/32]

TEST	(	ZeroOneBFS	,
		DigraphBasic
	)

Definition at line 413 of file test_zero_one_bfs.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [8/32]

TEST	(	ZeroOneBFS	,
		DigraphNoReversePath
	)

Definition at line 433 of file test_zero_one_bfs.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [9/32]

TEST	(	ZeroOneBFS	,
		DisconnectedPainting
	)

Definition at line 698 of file test_zero_one_bfs.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::get_distance(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), and Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::paint_min_paths_tree().

TEST() [10/32]

TEST	(	ZeroOneBFS	,
		EmptyGraphValidation
	)

Definition at line 224 of file test_zero_one_bfs.cc.

References Aleph::divide_and_conquer_partition_dp(), GraphCommon< GT, Node, Arc >::get_num_nodes(), and Aleph::Path< GT >::is_empty().

TEST() [11/32]

TEST	(	ZeroOneBFS	,
		GetDistanceAfterPainting
	)

Definition at line 292 of file test_zero_one_bfs.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::get_distance(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), and Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::paint_min_paths_tree().

TEST() [12/32]

TEST	(	ZeroOneBFS	,
		GetDistanceBeforePainting
	)

Definition at line 316 of file test_zero_one_bfs.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::get_distance(), and Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node().

TEST() [13/32]

TEST	(	ZeroOneBFS	,
		GraphWithCycle
	)

Definition at line 389 of file test_zero_one_bfs.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() [14/32]

TEST	(	ZeroOneBFS	,
		GridExample
	)

Definition at line 580 of file test_zero_one_bfs.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 r.

TEST() [15/32]

TEST	(	ZeroOneBFS	,
		InvalidWeightValidation
	)

Definition at line 243 of file test_zero_one_bfs.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(), IS_ARC_VISITED, IS_NODE_VISITED, NODE_COOKIE, and Aleph::Spanning_Tree.

TEST() [16/32]

TEST	(	ZeroOneBFS	,
		LargeGraphManyZeros
	)

Definition at line 719 of file test_zero_one_bfs.cc.

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

TEST() [17/32]

TEST	(	ZeroOneBFS	,
		LargeLinearGraph
	)

Definition at line 479 of file test_zero_one_bfs.cc.

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

TEST() [18/32]

TEST	(	ZeroOneBFS	,
		LinearChain
	)

Definition at line 157 of file test_zero_one_bfs.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() [19/32]

TEST	(	ZeroOneBFS	,
		MultipleComputations
	)

Definition at line 455 of file test_zero_one_bfs.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() [20/32]

TEST	(	ZeroOneBFS	,
		NegativeWeightValidation
	)

Definition at line 653 of file test_zero_one_bfs.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(), IS_ARC_VISITED, IS_NODE_VISITED, NODE_COOKIE, and Aleph::Spanning_Tree.

TEST() [21/32]

TEST	(	ZeroOneBFS	,
		NoPathExists
	)

Definition at line 121 of file test_zero_one_bfs.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::Path< GT >::is_empty().

TEST() [22/32]

TEST	(	ZeroOneBFS	,
		NullNodeValidation
	)

Definition at line 209 of file test_zero_one_bfs.cc.

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

TEST() [23/32]

TEST	(	ZeroOneBFS	,
		PaintAndGetMinPath
	)

Definition at line 265 of file test_zero_one_bfs.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::get_min_path(), Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::get_start_node(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), Aleph::Path< GT >::is_empty(), Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::is_painted(), and Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::paint_min_paths_tree().

TEST() [24/32]

TEST	(	ZeroOneBFS	,
		ParallelEdgesKeepSingleParentArcMarked
	)

Definition at line 745 of file test_zero_one_bfs.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::get_distance(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), IS_ARC_VISITED, IS_NODE_VISITED, Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::paint_min_paths_tree(), and Aleph::Spanning_Tree.

TEST() [25/32]

TEST	(	ZeroOneBFS	,
		PathNodeVerification
	)

Definition at line 328 of file test_zero_one_bfs.cc.

References Aleph::DynList< T >::append(), Aleph::divide_and_conquer_partition_dp(), Aleph::Dlink::Iterator::has_curr(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), and nodes.

TEST() [26/32]

TEST	(	ZeroOneBFS	,
		PathToSelf
	)

Definition at line 104 of file test_zero_one_bfs.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() [27/32]

TEST	(	ZeroOneBFS	,
		SingleNode
	)

Definition at line 142 of file test_zero_one_bfs.cc.

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

TEST() [28/32]

TEST	(	ZeroOneBFS	,
		StarGraph
	)

Definition at line 539 of file test_zero_one_bfs.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::get_distance(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), and Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::paint_min_paths_tree().

TEST() [29/32]

TEST	(	ZeroOneBFS	,
		StateGetters
	)

Definition at line 675 of file test_zero_one_bfs.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::get_graph(), Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::get_start_node(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::is_painted(), and Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::paint_min_paths_tree().

TEST() [30/32]

TEST	(	ZeroOneBFS	,
		TwoNodeOneWeight
	)

Definition at line 635 of file test_zero_one_bfs.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() [31/32]

TEST	(	ZeroOneBFS	,
		TwoNodeZeroWeight
	)

Definition at line 617 of file test_zero_one_bfs.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() [32/32]

TEST	(	ZeroOneBFS	,
		ZeroWeightShortcut
	)

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