astar_test.cc File Reference

Tests for A* shortest path algorithm. More...

#include <gtest/gtest.h>
#include <tpl_graph.H>
#include <AStar.H>
#include <Dijkstra.H>
#include <tpl_graph_utils.H>
#include <random>
#include <cmath>

Include dependency graph for astar_test.cc:

Go to the source code of this file.

Classes
struct	BinHeapTag
struct	FibHeapTag
struct	SimpleNode
struct	SimpleArc
struct	GridNode
struct	GridArc
struct	DoubleDistance
struct	GridEuclideanHeuristic
struct	GridManhattanHeuristic
class	AStarBasicTest
class	AStarGridTest
class	AStarDijkstraModeTest
class	AStarHeapTest< HeapTag >

Typedefs
using	SimpleGraph = List_Graph< SimpleNode, SimpleArc >
using	GridGraph = List_Graph< GridNode, GridArc >
using	HeapTypes = ::testing::Types< BinHeapTag, FibHeapTag >

Functions
	TEST_F (AStarBasicTest, ZeroHeuristicMatchesDijkstra)
	TEST_F (AStarBasicTest, FindsShortestPath)
	TEST_F (AStarBasicTest, PaintPathWorks)
	TEST_F (AStarBasicTest, ComputePathBuildsTree)
	TEST_F (AStarBasicTest, NoPathReturnsMax)
	TEST_F (AStarBasicTest, StartEqualsEnd)
	TEST_F (AStarGridTest, EuclideanHeuristicFindsShortest)
	TEST_F (AStarGridTest, ManhattanHeuristicFindsShortest)
	TEST_F (AStarGridTest, GoodHeuristicReducesExploration)
	TEST_F (AStarBasicTest, OperatorInterface)
	TEST (AStarEdgeCases, SingleNodeGraph)
	TEST (AStarEdgeCases, NullParametersThrow)
	TEST (AStarEdgeCases, EmptyGraphThrows)
	TEST (AStarComparison, RandomGraphMatchesDijkstra)
	TEST_F (AStarDijkstraModeTest, ComputeMinPathsTreeBuildsCompleteTree)
	TEST_F (AStarDijkstraModeTest, PaintMinPathsTreePaintsAll)
	TEST_F (AStarDijkstraModeTest, FindMinPathMatchesDijkstra)
	TEST_F (AStarDijkstraModeTest, ComputePartialMinPathsTree)
	TEST_F (AStarDijkstraModeTest, PaintPartialMinPathsTree)
	TEST_F (AStarDijkstraModeTest, GetDistanceAfterPainting)
	TEST_F (AStarDijkstraModeTest, CopyPaintedMinPathsTree)
	TEST_F (AStarDijkstraModeTest, OperatorTreeVersion)
	TEST (AStarErrorCases, GetDistanceThrowsIfNotPainted)
	TEST (AStarErrorCases, CopyPaintedThrowsIfNotPainted)
	TEST_F (AStarDijkstraModeTest, TreesMatchDijkstra)
	TEST (AStarDijkstraMode, DisconnectedGraph)
	TEST_F (AStarDijkstraModeTest, StateGetters)
	TYPED_TEST_SUITE (AStarHeapTest, HeapTypes)
	TYPED_TEST (AStarHeapTest, FindPathWithHeuristic)
	TYPED_TEST (AStarHeapTest, ComputeMinPathsTree)
	TYPED_TEST (AStarHeapTest, PaintAndGetDistance)
	TYPED_TEST (AStarHeapTest, MatchesDijkstra)
	TEST (AStarEdgeCaseTest, SelfLoop)
	TEST (AStarEdgeCaseTest, MultipleArcsBetweenNodes)
	TEST (AStarEdgeCaseTest, UniformWeights)
	TEST (AStarEdgeCaseTest, LargeWeights)
	TEST (AStarEdgeCaseTest, Reusability)
	TEST (AStarEdgeCaseTest, ZeroWeightArcs)
	TEST (AStarEdgeCaseTest, InadmissibleHeuristic)
int	main (int argc, char **argv)

Detailed Description

Tests for A* shortest path algorithm.

Tests cover:

• Basic correctness on simple graphs
• Comparison with Dijkstra to verify optimality
• Different heuristics (zero, euclidean, manhattan)
• Grid-based pathfinding
• Edge cases: no path, same start/end, single node

Definition in file astar_test.cc.

Typedef Documentation

GridGraph

using GridGraph = List_Graph<GridNode, GridArc>

Definition at line 100 of file astar_test.cc.

HeapTypes

using HeapTypes = ::testing::Types<BinHeapTag, FibHeapTag>

Definition at line 713 of file astar_test.cc.

SimpleGraph

using SimpleGraph = List_Graph<SimpleNode, SimpleArc>

Definition at line 82 of file astar_test.cc.

Function Documentation

main()

int main	(	int	argc,
		char **	argv
	)

Definition at line 981 of file astar_test.cc.

References Aleph::maps().

TEST() [1/14]

TEST	(	AStarComparison	,
		RandomGraphMatchesDijkstra
	)

Definition at line 408 of file astar_test.cc.

References Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), Aleph::maps(), nodes, rng, and w.

TEST() [2/14]

TEST	(	AStarDijkstraMode	,
		DisconnectedGraph
	)

Definition at line 651 of file astar_test.cc.

References GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), and Aleph::maps().

TEST() [3/14]

TEST	(	AStarEdgeCases	,
		EmptyGraphThrows
	)

Definition at line 395 of file astar_test.cc.

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

TEST() [4/14]

TEST	(	AStarEdgeCases	,
		NullParametersThrow
	)

Definition at line 382 of file astar_test.cc.

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

TEST() [5/14]

TEST	(	AStarEdgeCases	,
		SingleNodeGraph
	)

Definition at line 369 of file astar_test.cc.

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

TEST() [6/14]

TEST	(	AStarEdgeCaseTest	,
		InadmissibleHeuristic
	)

Definition at line 941 of file astar_test.cc.

References Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), Aleph::Path< GT >::is_empty(), Aleph::maps(), and GridNode::x.

TEST() [7/14]

TEST	(	AStarEdgeCaseTest	,
		LargeWeights
	)

Definition at line 859 of file astar_test.cc.

References Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), Aleph::Path< GT >::is_empty(), and Aleph::maps().

TEST() [8/14]

TEST	(	AStarEdgeCaseTest	,
		MultipleArcsBetweenNodes
	)

Definition at line 814 of file astar_test.cc.

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

TEST() [9/14]

TEST	(	AStarEdgeCaseTest	,
		Reusability
	)

Definition at line 881 of file astar_test.cc.

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

TEST() [10/14]

TEST	(	AStarEdgeCaseTest	,
		SelfLoop
	)

Definition at line 794 of file astar_test.cc.

References Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), Aleph::maps(), and Aleph::Path< GT >::size().

TEST() [11/14]

TEST	(	AStarEdgeCaseTest	,
		UniformWeights
	)

Definition at line 834 of file astar_test.cc.

References Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), Aleph::maps(), nodes, and Aleph::Path< GT >::size().

TEST() [12/14]

TEST	(	AStarEdgeCaseTest	,
		ZeroWeightArcs
	)

Definition at line 920 of file astar_test.cc.

References Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), Aleph::maps(), and Aleph::Path< GT >::size().

TEST() [13/14]

TEST	(	AStarErrorCases	,
		CopyPaintedThrowsIfNotPainted
	)

Definition at line 623 of file astar_test.cc.

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

TEST() [14/14]

TEST	(	AStarErrorCases	,
		GetDistanceThrowsIfNotPainted
	)

Definition at line 612 of file astar_test.cc.

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

TEST_F() [1/20]

TEST_F	(	AStarBasicTest	,
		ComputePathBuildsTree
	)

Definition at line 273 of file astar_test.cc.

References GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::maps(), and nodes.

TEST_F() [2/20]

TEST_F	(	AStarBasicTest	,
		FindsShortestPath
	)

Definition at line 246 of file astar_test.cc.

References Aleph::maps(), nodes, and Aleph::Path< GT >::size().

TEST_F() [3/20]

TEST_F	(	AStarBasicTest	,
		NoPathReturnsMax
	)

Definition at line 285 of file astar_test.cc.

References Aleph::Path< GT >::is_empty(), Aleph::maps(), and nodes.

TEST_F() [4/20]

TEST_F	(	AStarBasicTest	,
		OperatorInterface
	)

Definition at line 358 of file astar_test.cc.

References Aleph::maps(), and nodes.

TEST_F() [5/20]

TEST_F	(	AStarBasicTest	,
		PaintPathWorks
	)

Definition at line 259 of file astar_test.cc.

References Aleph::maps(), and nodes.

TEST_F() [6/20]

TEST_F	(	AStarBasicTest	,
		StartEqualsEnd
	)

Definition at line 300 of file astar_test.cc.

References Aleph::maps(), and nodes.

TEST_F() [7/20]

TEST_F	(	AStarBasicTest	,
		ZeroHeuristicMatchesDijkstra
	)

Definition at line 230 of file astar_test.cc.

References Aleph::maps(), nodes, and Aleph::HTList::size().

TEST_F() [8/20]

TEST_F	(	AStarDijkstraModeTest	,
		ComputeMinPathsTreeBuildsCompleteTree
	)

Definition at line 483 of file astar_test.cc.

References GraphCommon< GT, Node, Arc >::get_num_arcs(), GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::maps(), nodes, and root().

TEST_F() [9/20]

TEST_F	(	AStarDijkstraModeTest	,
		ComputePartialMinPathsTree
	)

Definition at line 534 of file astar_test.cc.

References GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::maps(), and nodes.

TEST_F() [10/20]

TEST_F	(	AStarDijkstraModeTest	,
		CopyPaintedMinPathsTree
	)

Definition at line 584 of file astar_test.cc.

References GraphCommon< GT, Node, Arc >::get_num_arcs(), GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::maps(), and nodes.

TEST_F() [11/20]

TEST_F	(	AStarDijkstraModeTest	,
		FindMinPathMatchesDijkstra
	)

Definition at line 518 of file astar_test.cc.

References Aleph::maps(), nodes, and Aleph::HTList::size().

TEST_F() [12/20]

TEST_F	(	AStarDijkstraModeTest	,
		GetDistanceAfterPainting
	)

Definition at line 564 of file astar_test.cc.

References Aleph::maps(), and nodes.

TEST_F() [13/20]

TEST_F	(	AStarDijkstraModeTest	,
		OperatorTreeVersion
	)

Definition at line 601 of file astar_test.cc.

References GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::maps(), and nodes.

TEST_F() [14/20]

TEST_F	(	AStarDijkstraModeTest	,
		PaintMinPathsTreePaintsAll
	)

Definition at line 498 of file astar_test.cc.

References Aleph::maps(), and nodes.

TEST_F() [15/20]

TEST_F	(	AStarDijkstraModeTest	,
		PaintPartialMinPathsTree
	)

Definition at line 548 of file astar_test.cc.

References Aleph::maps(), and nodes.

TEST_F() [16/20]

TEST_F	(	AStarDijkstraModeTest	,
		StateGetters
	)

Definition at line 670 of file astar_test.cc.

References Aleph::maps(), and nodes.

TEST_F() [17/20]

TEST_F	(	AStarDijkstraModeTest	,
		TreesMatchDijkstra
	)

Definition at line 635 of file astar_test.cc.

References Aleph::maps(), and nodes.

TEST_F() [18/20]

TEST_F	(	AStarGridTest	,
		EuclideanHeuristicFindsShortest
	)

Definition at line 311 of file astar_test.cc.

References Aleph::maps().

TEST_F() [19/20]

TEST_F	(	AStarGridTest	,
		GoodHeuristicReducesExploration
	)

Definition at line 342 of file astar_test.cc.

References Aleph::Path< GT >::is_empty(), and Aleph::maps().

TEST_F() [20/20]

TEST_F	(	AStarGridTest	,
		ManhattanHeuristicFindsShortest
	)

Definition at line 327 of file astar_test.cc.

References Aleph::maps().

TYPED_TEST() [1/4]

TYPED_TEST	(	AStarHeapTest	,
		ComputeMinPathsTree
	)

Definition at line 733 of file astar_test.cc.

References GraphCommon< GT, Node, Arc >::get_num_arcs(), GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::maps(), nodes, and root().

TYPED_TEST() [2/4]

TYPED_TEST	(	AStarHeapTest	,
		FindPathWithHeuristic
	)

Definition at line 717 of file astar_test.cc.

References Aleph::Path< GT >::is_empty(), Aleph::maps(), and nodes.

TYPED_TEST() [3/4]

TYPED_TEST	(	AStarHeapTest	,
		MatchesDijkstra
	)

Definition at line 768 of file astar_test.cc.

References Aleph::maps(), nodes, and Aleph::HTList::size().

TYPED_TEST() [4/4]

TYPED_TEST	(	AStarHeapTest	,
		PaintAndGetDistance
	)

Definition at line 750 of file astar_test.cc.

References Aleph::maps(), and nodes.

TYPED_TEST_SUITE()

TYPED_TEST_SUITE	(	AStarHeapTest	,
		HeapTypes
	)