test_dijkstra.cc File Reference

GoogleTest suite for Dijkstra.H. More...

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

Include dependency graph for test_dijkstra.cc:

Go to the source code of this file.

Classes
class	Out_Iterator_AllArcs< GT, SA >
struct	BinHeapTag
struct	FibHeapTag
class	DijkstraHeapTest< HeapTag >
class	DijkstraDigraphHeapTest< HeapTag >

Typedefs
using	GT = List_Graph< Graph_Node< int >, Graph_Arc< double > >
using	Node = GT::Node
using	Arc = GT::Arc
using	DGT = List_Digraph< Graph_Node< int >, Graph_Arc< double > >
using	DNode = DGT::Node
using	DArc = DGT::Arc
template<typename HeapTag , typename Graph >
using	DijkstraFor = Dijkstra_Min_Paths< Graph, Dft_Dist< Graph >, Node_Arc_Iterator, Dft_Show_Arc< Graph >, HeapTag::template Heap >
template<typename HeapTag , typename Graph >
using	DijkstraForAllArcs = Dijkstra_Min_Paths< Graph, Dft_Dist< Graph >, Out_Iterator_AllArcs, Dft_Show_Arc< Graph >, HeapTag::template Heap >
template<typename HeapTag >
using	Dijkstra = DijkstraFor< HeapTag, GT >
template<typename HeapTag >
using	DijkstraAllArcs = DijkstraForAllArcs< HeapTag, GT >
template<typename HeapTag >
using	DigraphDijkstra = DijkstraFor< HeapTag, DGT >
using	HeapTypes = ::testing::Types< BinHeapTag, FibHeapTag >

Functions
	TYPED_TEST_SUITE (DijkstraHeapTest, HeapTypes)
	TYPED_TEST_SUITE (DijkstraDigraphHeapTest, HeapTypes)
	TYPED_TEST (DijkstraHeapTest, BasicShortestPath)
	TYPED_TEST (DijkstraHeapTest, PathToSelf)
	TYPED_TEST (DijkstraHeapTest, NoPathExists)
	TYPED_TEST (DijkstraHeapTest, ComputeSpanningTree)
	TYPED_TEST (DijkstraHeapTest, RelaxationUpdate)
	TYPED_TEST (DijkstraHeapTest, PaintSpanningTree)
	TYPED_TEST (DijkstraHeapTest, CopyPaintedMinPathsTree)
	TYPED_TEST (DijkstraHeapTest, SingleNodeGraph)
	TYPED_TEST (DijkstraHeapTest, LinearChainGraph)
	TYPED_TEST (DijkstraHeapTest, CompleteGraphK4)
	TYPED_TEST (DijkstraHeapTest, GraphWithSelfLoop)
	TYPED_TEST (DijkstraDigraphHeapTest, BasicPath)
	TYPED_TEST (DijkstraDigraphHeapTest, NoReturnPath)
	TYPED_TEST (DijkstraHeapTest, EmptyGraph)
	TYPED_TEST (DijkstraHeapTest, MultiplePathsSameCost)
	TYPED_TEST (DijkstraHeapTest, LargeWeights)
	TYPED_TEST (DijkstraHeapTest, ZeroWeightEdges)
	TYPED_TEST (DijkstraHeapTest, FractionalWeights)
	TYPED_TEST (DijkstraHeapTest, StarGraph)
	TYPED_TEST (DijkstraHeapTest, VerifyPathNodes)
	TYPED_TEST (DijkstraHeapTest, StateGetters)
	TYPED_TEST (DijkstraHeapTest, ComputePartialMinPathsTree)
	TYPED_TEST (DijkstraHeapTest, GetMinPathFromTree)
	TYPED_TEST (DijkstraHeapTest, NullNodeValidation)
	TYPED_TEST (DijkstraHeapTest, DisconnectedGraph)
	TYPED_TEST (DijkstraHeapTest, IntegerWeights)
	TYPED_TEST (DijkstraHeapTest, GetDistanceAfterPainting)
	TYPED_TEST (DijkstraHeapTest, GetDistanceBeforePainting)
	TYPED_TEST (DijkstraHeapTest, GetDistanceUnreachableNode)
	TYPED_TEST (DijkstraHeapTest, MultipleSuccessiveComputations)
	TYPED_TEST (DijkstraHeapTest, PaintPartialReturnsFalse)
	TYPED_TEST (DijkstraHeapTest, PaintPartialReturnsTrue)
	TYPED_TEST (DijkstraHeapTest, VeryLongPath)
	TYPED_TEST (DijkstraHeapTest, DenseGraphPerformance)
	TYPED_TEST (DijkstraHeapTest, ComputeSpanningTreeDisconnected)
	TYPED_TEST (DijkstraHeapTest, ParallelArcsChoosesMinimum)
	TYPED_TEST (DijkstraHeapTest, ParallelArcsBothDirections)
	TYPED_TEST (DijkstraHeapTest, ComplexMultigraph)
	TYPED_TEST (DijkstraHeapTest, GetMinPathFromTreeMethod)
	TYPED_TEST (DijkstraHeapTest, GetMinPathFromTreeMultipleQueries)
int	main (int argc, char **argv)

Detailed Description

GoogleTest suite for Dijkstra.H.

This file contains exhaustive tests to verify the correctness of Dijkstra's shortest path algorithm implementation in Aleph-w.

Tests for Test Dijkstra

Definition in file test_dijkstra.cc.

Typedef Documentation

Arc

using Arc = GT::Arc

Definition at line 38 of file test_dijkstra.cc.

DArc

using DArc = DGT::Arc

Definition at line 43 of file test_dijkstra.cc.

DGT

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

Definition at line 41 of file test_dijkstra.cc.

DigraphDijkstra

template<typename HeapTag >

using DigraphDijkstra = DijkstraFor<HeapTag, DGT>

Definition at line 75 of file test_dijkstra.cc.

Dijkstra

template<typename HeapTag >

using Dijkstra = DijkstraFor<HeapTag, GT>

Definition at line 69 of file test_dijkstra.cc.

DijkstraAllArcs

template<typename HeapTag >

using DijkstraAllArcs = DijkstraForAllArcs<HeapTag, GT>

Definition at line 72 of file test_dijkstra.cc.

DijkstraFor

template<typename HeapTag , typename Graph >

using DijkstraFor = Dijkstra_Min_Paths<Graph, Dft_Dist<Graph>, Node_Arc_Iterator, Dft_Show_Arc<Graph>, HeapTag::template Heap>

Definition at line 58 of file test_dijkstra.cc.

DijkstraForAllArcs

template<typename HeapTag , typename Graph >

using DijkstraForAllArcs = Dijkstra_Min_Paths<Graph, Dft_Dist<Graph>, Out_Iterator_AllArcs, Dft_Show_Arc<Graph>, HeapTag::template Heap>

Definition at line 64 of file test_dijkstra.cc.

DNode

using DNode = DGT::Node

Definition at line 42 of file test_dijkstra.cc.

GT

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

Definition at line 36 of file test_dijkstra.cc.

HeapTypes

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

Definition at line 83 of file test_dijkstra.cc.

Node

using Node = GT::Node

Definition at line 37 of file test_dijkstra.cc.

Function Documentation

main()

int main	(	int	argc,
		char **	argv
	)

Definition at line 988 of file test_dijkstra.cc.

References Aleph::maps().

TYPED_TEST() [1/40]

TYPED_TEST	(	DijkstraDigraphHeapTest	,
		BasicPath
	)

Definition at line 341 of file test_dijkstra.cc.

References Aleph::maps().

TYPED_TEST() [2/40]

TYPED_TEST	(	DijkstraDigraphHeapTest	,
		NoReturnPath
	)

Definition at line 359 of file test_dijkstra.cc.

References Aleph::maps().

TYPED_TEST() [3/40]

TYPED_TEST	(	DijkstraHeapTest	,
		BasicShortestPath
	)

Definition at line 88 of file test_dijkstra.cc.

References Aleph::Path< GT >::Iterator::get_current_node(), Aleph::Dlink::Iterator::has_curr(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), Aleph::maps(), and Aleph::DynDlist< T >::Iterator::next().

TYPED_TEST() [4/40]

TYPED_TEST	(	DijkstraHeapTest	,
		CompleteGraphK4
	)

Definition at line 302 of file test_dijkstra.cc.

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

TYPED_TEST() [5/40]

TYPED_TEST	(	DijkstraHeapTest	,
		ComplexMultigraph
	)

Definition at line 875 of file test_dijkstra.cc.

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

TYPED_TEST() [6/40]

TYPED_TEST	(	DijkstraHeapTest	,
		ComputePartialMinPathsTree
	)

Definition at line 545 of file test_dijkstra.cc.

References GraphCommon< GT, Node, Arc >::get_num_arcs(), 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().

TYPED_TEST() [7/40]

TYPED_TEST	(	DijkstraHeapTest	,
		ComputeSpanningTree
	)

Definition at line 162 of file test_dijkstra.cc.

References GraphCommon< GT, Node, Arc >::get_num_arcs(), 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().

TYPED_TEST() [8/40]

TYPED_TEST	(	DijkstraHeapTest	,
		ComputeSpanningTreeDisconnected
	)

Definition at line 802 of file test_dijkstra.cc.

References GraphCommon< GT, Node, Arc >::get_num_arcs(), 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().

TYPED_TEST() [9/40]

TYPED_TEST	(	DijkstraHeapTest	,
		CopyPaintedMinPathsTree
	)

Definition at line 246 of file test_dijkstra.cc.

References GraphCommon< GT, Node, Arc >::get_num_arcs(), 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().

TYPED_TEST() [10/40]

TYPED_TEST	(	DijkstraHeapTest	,
		DenseGraphPerformance
	)

Definition at line 780 of file test_dijkstra.cc.

References GraphCommon< GT, Node, Arc >::get_num_arcs(), 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(), Aleph::maps(), N, and nodes.

TYPED_TEST() [11/40]

TYPED_TEST	(	DijkstraHeapTest	,
		DisconnectedGraph
	)

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

TYPED_TEST() [12/40]

TYPED_TEST	(	DijkstraHeapTest	,
		EmptyGraph
	)

Definition at line 378 of file test_dijkstra.cc.

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

TYPED_TEST() [13/40]

TYPED_TEST	(	DijkstraHeapTest	,
		FractionalWeights
	)

Definition at line 449 of file test_dijkstra.cc.

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

TYPED_TEST() [14/40]

TYPED_TEST	(	DijkstraHeapTest	,
		GetDistanceAfterPainting
	)

Definition at line 653 of file test_dijkstra.cc.

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

TYPED_TEST() [15/40]

TYPED_TEST	(	DijkstraHeapTest	,
		GetDistanceBeforePainting
	)

Definition at line 674 of file test_dijkstra.cc.

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

TYPED_TEST() [16/40]

TYPED_TEST	(	DijkstraHeapTest	,
		GetDistanceUnreachableNode
	)

Definition at line 685 of file test_dijkstra.cc.

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

TYPED_TEST() [17/40]

TYPED_TEST	(	DijkstraHeapTest	,
		GetMinPathFromTree
	)

Definition at line 568 of file test_dijkstra.cc.

References GraphCommon< GT, Node, Arc >::get_num_arcs(), 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(), Aleph::Path< GT >::is_empty(), and Aleph::maps().

TYPED_TEST() [18/40]

TYPED_TEST	(	DijkstraHeapTest	,
		GetMinPathFromTreeMethod
	)

Definition at line 907 of file test_dijkstra.cc.

References Aleph::DynList< T >::append(), LocateFunctions< Container, Type >::get_it(), Aleph::Dlink::Iterator::has_curr(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), Aleph::HTList::is_empty(), Aleph::maps(), and Aleph::HTList::size().

TYPED_TEST() [19/40]

TYPED_TEST	(	DijkstraHeapTest	,
		GetMinPathFromTreeMultipleQueries
	)

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

TYPED_TEST() [20/40]

TYPED_TEST	(	DijkstraHeapTest	,
		GraphWithSelfLoop
	)

Definition at line 325 of file test_dijkstra.cc.

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

TYPED_TEST() [21/40]

TYPED_TEST	(	DijkstraHeapTest	,
		IntegerWeights
	)

Definition at line 634 of file test_dijkstra.cc.

References Aleph::maps().

TYPED_TEST() [22/40]

TYPED_TEST	(	DijkstraHeapTest	,
		LargeWeights
	)

Definition at line 415 of file test_dijkstra.cc.

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

TYPED_TEST() [23/40]

TYPED_TEST	(	DijkstraHeapTest	,
		LinearChainGraph
	)

Definition at line 283 of file test_dijkstra.cc.

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

TYPED_TEST() [24/40]

TYPED_TEST	(	DijkstraHeapTest	,
		MultiplePathsSameCost
	)

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

TYPED_TEST() [25/40]

TYPED_TEST	(	DijkstraHeapTest	,
		MultipleSuccessiveComputations
	)

Definition at line 701 of file test_dijkstra.cc.

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

TYPED_TEST() [26/40]

TYPED_TEST	(	DijkstraHeapTest	,
		NoPathExists
	)

Definition at line 146 of file test_dijkstra.cc.

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

TYPED_TEST() [27/40]

TYPED_TEST	(	DijkstraHeapTest	,
		NullNodeValidation
	)

Definition at line 597 of file test_dijkstra.cc.

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

TYPED_TEST() [28/40]

TYPED_TEST	(	DijkstraHeapTest	,
		PaintPartialReturnsFalse
	)

Definition at line 725 of file test_dijkstra.cc.

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

TYPED_TEST() [29/40]

TYPED_TEST	(	DijkstraHeapTest	,
		PaintPartialReturnsTrue
	)

Definition at line 740 of file test_dijkstra.cc.

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

TYPED_TEST() [30/40]

TYPED_TEST	(	DijkstraHeapTest	,
		PaintSpanningTree
	)

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

TYPED_TEST() [31/40]

TYPED_TEST	(	DijkstraHeapTest	,
		ParallelArcsBothDirections
	)

Definition at line 851 of file test_dijkstra.cc.

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

TYPED_TEST() [32/40]

TYPED_TEST	(	DijkstraHeapTest	,
		ParallelArcsChoosesMinimum
	)

Definition at line 823 of file test_dijkstra.cc.

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

TYPED_TEST() [33/40]

TYPED_TEST	(	DijkstraHeapTest	,
		PathToSelf
	)

Definition at line 131 of file test_dijkstra.cc.

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

TYPED_TEST() [34/40]

TYPED_TEST	(	DijkstraHeapTest	,
		RelaxationUpdate
	)

Definition at line 190 of file test_dijkstra.cc.

References Aleph::Path< GT >::Iterator::get_current_node(), Aleph::Dlink::Iterator::has_curr(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), Aleph::maps(), and Aleph::DynDlist< T >::Iterator::next().

TYPED_TEST() [35/40]

TYPED_TEST	(	DijkstraHeapTest	,
		SingleNodeGraph
	)

Definition at line 270 of file test_dijkstra.cc.

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

TYPED_TEST() [36/40]

TYPED_TEST	(	DijkstraHeapTest	,
		StarGraph
	)

Definition at line 466 of file test_dijkstra.cc.

References GraphCommon< GT, Node, Arc >::get_num_arcs(), 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().

TYPED_TEST() [37/40]

TYPED_TEST	(	DijkstraHeapTest	,
		StateGetters
	)

Definition at line 521 of file test_dijkstra.cc.

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

TYPED_TEST() [38/40]

TYPED_TEST	(	DijkstraHeapTest	,
		VerifyPathNodes
	)

Definition at line 488 of file test_dijkstra.cc.

References Aleph::DynList< T >::append(), LocateFunctions< Container, Type >::get_it(), Aleph::Dlink::Iterator::has_curr(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), Aleph::maps(), and Aleph::HTList::size().

TYPED_TEST() [39/40]

TYPED_TEST	(	DijkstraHeapTest	,
		VeryLongPath
	)

Definition at line 761 of file test_dijkstra.cc.

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

TYPED_TEST() [40/40]

TYPED_TEST	(	DijkstraHeapTest	,
		ZeroWeightEdges
	)

Definition at line 432 of file test_dijkstra.cc.

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

TYPED_TEST_SUITE() [1/2]

TYPED_TEST_SUITE	(	DijkstraDigraphHeapTest	,
		HeapTypes
	)

TYPED_TEST_SUITE() [2/2]

TYPED_TEST_SUITE	(	DijkstraHeapTest	,
		HeapTypes
	)