test_bidirectional_bfs.cc File Reference

Comprehensive tests for Bidirectional_BFS.H. More...

#include <gtest/gtest.h>
#include <Bidirectional_BFS.H>
#include <tpl_find_path.H>
#include <tpl_graph.H>

Include dependency graph for test_bidirectional_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
template<class G >
size_t	path_edge_count (Path< G > &p)
	TEST (BidirectionalBFS, BasicShortestPath)
	TEST (BidirectionalBFS, PathToSelf)
	TEST (BidirectionalBFS, NoPathExists)
	TEST (BidirectionalBFS, SingleNode)
	TEST (BidirectionalBFS, LinearChain)
	TEST (BidirectionalBFS, CompleteGraphK4)
	TEST (BidirectionalBFS, NullNodeValidation)
	TEST (BidirectionalBFS, DisconnectedComponents)
	TEST (BidirectionalBFS, TwoNodeGraph)
	TEST (BidirectionalBFS, GraphWithCycle)
	TEST (BidirectionalBFS, OddLengthPath)
	TEST (BidirectionalBFS, EvenLengthPath)
	TEST (BidirectionalBFS, CrossValidationWithBFS)
	TEST (BidirectionalBFS, MultipleComputations)
	TEST (BidirectionalBFS, LargeGraph)
	TEST (BidirectionalBFS, OperatorReturnsPath)
	TEST (BidirectionalBFS, StarGraph)
	TEST (BidirectionalBFS, BinaryTreeGraph)
	TEST (BidirectionalBFS, DigraphForward)
	TEST (BidirectionalBFS, DigraphNoBackward)
	TEST (BidirectionalBFS, DigraphInIteratorBackward)
	TEST (BidirectionalBFS, SocialNetworkExample)
	TEST (BidirectionalBFS, PathEndsCorrectness)
	TEST (BidirectionalBFS, CrossValidationMultipleEndpoints)
	TEST (BidirectionalBFS, GridGraph)
	TEST (BidirectionalBFS, MeetingPointDepthSumRegression)

Detailed Description

Comprehensive tests for Bidirectional_BFS.H.

Tests cover correctness, edge cases, validation, and cross-checks against standard BFS for unweighted shortest paths.

Definition in file test_bidirectional_bfs.cc.

Typedef Documentation

Arc

using Arc = GT::Arc

Definition at line 22 of file test_bidirectional_bfs.cc.

DArc

using DArc = DGT::Arc

Definition at line 26 of file test_bidirectional_bfs.cc.

DGT

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

Definition at line 24 of file test_bidirectional_bfs.cc.

DNode

using DNode = DGT::Node

Definition at line 25 of file test_bidirectional_bfs.cc.

GT

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

Definition at line 20 of file test_bidirectional_bfs.cc.

Node

using Node = GT::Node

Definition at line 21 of file test_bidirectional_bfs.cc.

Function Documentation

path_edge_count()

template<class G >

size_t path_edge_count

(

Path< G > &

p

)

Definition at line 30 of file test_bidirectional_bfs.cc.

References Aleph::count(), Aleph::Dlink::Iterator::has_curr(), and Aleph::Path< GT >::is_empty().

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

TEST() [1/26]

TEST	(	BidirectionalBFS	,
		BasicShortestPath
	)

Definition at line 43 of file test_bidirectional_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 path_edge_count().

TEST() [2/26]

TEST	(	BidirectionalBFS	,
		BinaryTreeGraph
	)

Definition at line 421 of file test_bidirectional_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 path_edge_count().

TEST() [3/26]

TEST	(	BidirectionalBFS	,
		CompleteGraphK4
	)

Definition at line 136 of file test_bidirectional_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 path_edge_count().

TEST() [4/26]

TEST	(	BidirectionalBFS	,
		CrossValidationMultipleEndpoints
	)

Definition at line 599 of file test_bidirectional_bfs.cc.

References Aleph::and, 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, nodes, and path_edge_count().

TEST() [5/26]

TEST	(	BidirectionalBFS	,
		CrossValidationWithBFS
	)

Definition at line 296 of file test_bidirectional_bfs.cc.

References Aleph::and, 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 path_edge_count().

TEST() [6/26]

TEST	(	BidirectionalBFS	,
		DigraphForward
	)

Definition at line 455 of file test_bidirectional_bfs.cc.

References Aleph::divide_and_conquer_partition_dp(), and path_edge_count().

TEST() [7/26]

TEST	(	BidirectionalBFS	,
		DigraphInIteratorBackward
	)

Definition at line 495 of file test_bidirectional_bfs.cc.

References Aleph::DynList< T >::append(), Aleph::divide_and_conquer_partition_dp(), Aleph::Dlink::Iterator::has_curr(), nodes, and path_edge_count().

TEST() [8/26]

TEST	(	BidirectionalBFS	,
		DigraphNoBackward
	)

Definition at line 477 of file test_bidirectional_bfs.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [9/26]

TEST	(	BidirectionalBFS	,
		DisconnectedComponents
	)

Definition at line 177 of file test_bidirectional_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() [10/26]

TEST	(	BidirectionalBFS	,
		EvenLengthPath
	)

Definition at line 273 of file test_bidirectional_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 path_edge_count().

TEST() [11/26]

TEST	(	BidirectionalBFS	,
		GraphWithCycle
	)

Definition at line 217 of file test_bidirectional_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 path_edge_count().

TEST() [12/26]

TEST	(	BidirectionalBFS	,
		GridGraph
	)

Definition at line 637 of file test_bidirectional_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(), path_edge_count(), and r.

TEST() [13/26]

TEST	(	BidirectionalBFS	,
		LargeGraph
	)

Definition at line 353 of file test_bidirectional_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, nodes, and path_edge_count().

TEST() [14/26]

TEST	(	BidirectionalBFS	,
		LinearChain
	)

Definition at line 113 of file test_bidirectional_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 path_edge_count().

TEST() [15/26]

TEST	(	BidirectionalBFS	,
		MeetingPointDepthSumRegression
	)

Definition at line 668 of file test_bidirectional_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 path_edge_count().

TEST() [16/26]

TEST	(	BidirectionalBFS	,
		MultipleComputations
	)

Definition at line 329 of file test_bidirectional_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 path_edge_count().

TEST() [17/26]

TEST	(	BidirectionalBFS	,
		NoPathExists
	)

Definition at line 82 of file test_bidirectional_bfs.cc.

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

TEST() [18/26]

TEST	(	BidirectionalBFS	,
		NullNodeValidation
	)

Definition at line 162 of file test_bidirectional_bfs.cc.

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

TEST() [19/26]

TEST	(	BidirectionalBFS	,
		OddLengthPath
	)

Definition at line 242 of file test_bidirectional_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() [20/26]

TEST	(	BidirectionalBFS	,
		OperatorReturnsPath
	)

Definition at line 376 of file test_bidirectional_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 path_edge_count().

TEST() [21/26]

TEST	(	BidirectionalBFS	,
		PathEndsCorrectness
	)

Definition at line 566 of file test_bidirectional_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() [22/26]

TEST	(	BidirectionalBFS	,
		PathToSelf
	)

Definition at line 67 of file test_bidirectional_bfs.cc.

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

TEST() [23/26]

TEST	(	BidirectionalBFS	,
		SingleNode
	)

Definition at line 98 of file test_bidirectional_bfs.cc.

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

TEST() [24/26]

TEST	(	BidirectionalBFS	,
		SocialNetworkExample
	)

Definition at line 538 of file test_bidirectional_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 path_edge_count().

TEST() [25/26]

TEST	(	BidirectionalBFS	,
		StarGraph
	)

Definition at line 396 of file test_bidirectional_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 path_edge_count().

TEST() [26/26]

TEST	(	BidirectionalBFS	,
		TwoNodeGraph
	)

Definition at line 198 of file test_bidirectional_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 path_edge_count().