Aleph-w: Tests/test_ida_star.cc File Reference

Aleph-w 3.0

A C++ Library for Data Structures and Algorithms

Loading...

Searching...

No Matches

Comprehensive tests for IDA_Star.H. More...

#include <gtest/gtest.h>
#include <IDA_Star.H>
#include <AStar.H>
#include <Dijkstra.H>
#include <tpl_graph.H>

Include dependency graph for test_ida_star.cc:

Go to the source code of this file.

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

using	Node = GT::Node

using	Arc = GT::Arc

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

using	INode = IGT::Node

using	IArc = IGT::Arc

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

using	DNode = DGT::Node

using	DArc = DGT::Arc

template<class G >
using	IDA_Zero = IDA_Star< G, Dft_Dist< G >, Zero_Heuristic< G, Dft_Dist< G > > >

Functions
	TEST (IDAStar, BasicShortestPath)

	TEST (IDAStar, PathToSelf)

	TEST (IDAStar, NoPathExists)

	TEST (IDAStar, SingleNode)

	TEST (IDAStar, LinearChain)

	TEST (IDAStar, TwoNodeGraph)

	TEST (IDAStar, NullNodeValidation)

	TEST (IDAStar, RelaxationFindsCheaperPath)

	TEST (IDAStar, CrossValidationWithDijkstra)

	TEST (IDAStar, CrossValidationWithAStar)

	TEST (IDAStar, CompleteGraphK4)

	TEST (IDAStar, GraphWithCycle)

	TEST (IDAStar, IntegerWeights)

	TEST (IDAStar, MultipleComputations)

	TEST (IDAStar, PathNodeVerification)

	TEST (IDAStar, ZeroWeightEdges)

	TEST (IDAStar, FractionalWeights)

	TEST (IDAStar, DigraphBasic)

	TEST (IDAStar, DigraphNoReturn)

	TEST (IDAStar, StarGraph)

	TEST (IDAStar, DisconnectedGraph)

	TEST (IDAStar, LargerCrossValidation)

	TEST (IDAStar, WeightedGridExample)

	TEST (IDAStar, SelfLoop)

	TEST (IDAStar, ChebyshevHeuristicExists)

Detailed Description

Comprehensive tests for IDA_Star.H.

Tests cover correctness, edge cases, heuristic behavior, and cross-checks against A* and Dijkstra for weighted shortest paths.

Definition in file test_ida_star.cc.

Typedef Documentation

◆ Arc

using Arc = GT::Arc

Definition at line 23 of file test_ida_star.cc.

◆ DArc

using DArc = DGT::Arc

Definition at line 31 of file test_ida_star.cc.

◆ DGT

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

Definition at line 29 of file test_ida_star.cc.

◆ DNode

using DNode = DGT::Node

Definition at line 30 of file test_ida_star.cc.

◆ GT

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

Definition at line 21 of file test_ida_star.cc.

◆ IArc

using IArc = IGT::Arc

Definition at line 27 of file test_ida_star.cc.

◆ IDA_Zero

template<class G >

using IDA_Zero = IDA_Star<G, Dft_Dist<G>, Zero_Heuristic<G, Dft_Dist<G> >>

Definition at line 35 of file test_ida_star.cc.

◆ IGT

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

Definition at line 25 of file test_ida_star.cc.

◆ INode

using INode = IGT::Node

Definition at line 26 of file test_ida_star.cc.

◆ Node

using Node = GT::Node

Definition at line 22 of file test_ida_star.cc.

Function Documentation

◆ TEST() [1/25]

TEST	(	IDAStar	,
		BasicShortestPath
	)

Definition at line 40 of file test_ida_star.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() [2/25]

TEST	(	IDAStar	,
		ChebyshevHeuristicExists
	)

Definition at line 605 of file test_ida_star.cc.

References Aleph::divide_and_conquer_partition_dp(), Coord::x, and Coord::y.

◆ TEST() [3/25]

TEST	(	IDAStar	,
		CompleteGraphK4
	)

Definition at line 258 of file test_ida_star.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() [4/25]

TEST	(	IDAStar	,
		CrossValidationWithAStar
	)

Definition at line 230 of file test_ida_star.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/25]

TEST	(	IDAStar	,
		CrossValidationWithDijkstra
	)

Definition at line 199 of file test_ida_star.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/25]

TEST	(	IDAStar	,
		DigraphBasic
	)

Definition at line 426 of file test_ida_star.cc.

References Aleph::divide_and_conquer_partition_dp().

◆ TEST() [7/25]

TEST	(	IDAStar	,
		DigraphNoReturn
	)

Definition at line 446 of file test_ida_star.cc.

References Aleph::divide_and_conquer_partition_dp().

◆ TEST() [8/25]

TEST	(	IDAStar	,
		DisconnectedGraph
	)

Definition at line 489 of file test_ida_star.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() [9/25]

TEST	(	IDAStar	,
		FractionalWeights
	)

Definition at line 406 of file test_ida_star.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/25]

TEST	(	IDAStar	,
		GraphWithCycle
	)

Definition at line 283 of file test_ida_star.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() [11/25]

TEST	(	IDAStar	,
		IntegerWeights
	)

Definition at line 308 of file test_ida_star.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() [12/25]

TEST	(	IDAStar	,
		LargerCrossValidation
	)

Definition at line 511 of file test_ida_star.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() [13/25]

TEST	(	IDAStar	,
		LinearChain
	)

Definition at line 111 of file test_ida_star.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/25]

TEST	(	IDAStar	,
		MultipleComputations
	)

Definition at line 328 of file test_ida_star.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() [15/25]

TEST	(	IDAStar	,
		NoPathExists
	)

Definition at line 79 of file test_ida_star.cc.

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

◆ TEST() [16/25]

TEST	(	IDAStar	,
		NullNodeValidation
	)

Definition at line 151 of file test_ida_star.cc.

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

◆ TEST() [17/25]

TEST	(	IDAStar	,
		PathNodeVerification
	)

Definition at line 352 of file test_ida_star.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() [18/25]

TEST	(	IDAStar	,
		PathToSelf
	)

Definition at line 64 of file test_ida_star.cc.

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

◆ TEST() [19/25]

TEST	(	IDAStar	,
		RelaxationFindsCheaperPath
	)

Definition at line 178 of file test_ida_star.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/25]

TEST	(	IDAStar	,
		SelfLoop
	)

Definition at line 584 of file test_ida_star.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() [21/25]

TEST	(	IDAStar	,
		SingleNode
	)

Definition at line 96 of file test_ida_star.cc.

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

◆ TEST() [22/25]

TEST	(	IDAStar	,
		StarGraph
	)

Definition at line 464 of file test_ida_star.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() [23/25]

TEST	(	IDAStar	,
		TwoNodeGraph
	)

Definition at line 133 of file test_ida_star.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() [24/25]

TEST	(	IDAStar	,
		WeightedGridExample
	)

Definition at line 552 of file test_ida_star.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() [25/25]

TEST	(	IDAStar	,
		ZeroWeightEdges
	)

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

Tests
test_ida_star.cc
Generated by 1.9.8