Comprehensive tests for Floyd-Warshall algorithm (latex_floyd.H) More...

#include <gtest/gtest.h>
#include <sstream>
#include <fstream>
#include <limits>
#include <cmath>
#include <tpl_graph.H>
#include <tpl_matgraph.H>
#include <latex_floyd.H>

Include dependency graph for latex_floyd_test.cc:

Classes
struct	DistanceArc
	Arc info type with required Distance_Type and constants. More...

struct	IntDistanceArc
	Integer distance arc type. More...

class	FloydSimpleGraphTest
	Test fixture with a simple weighted graph. More...

class	FloydIntGraphTest
	Test fixture with integer weights. More...

struct	TestIndexFormatter< Mat >
	Index formatter: takes matrix and index, returns string. More...

struct	TestPathFormatter< Mat >
	Path formatter: takes matrix, i, j indices, returns formatted entry. More...

struct	TestDistFormatter< Mat >
	Distance formatter: takes matrix, i, j indices, returns formatted entry. More...

struct	MaxCompare

struct	MinPlus

Functions
	TEST_F (FloydSimpleGraphTest, DiagonalIsZero)

	TEST_F (FloydSimpleGraphTest, DirectEdgeDistance)

	TEST_F (FloydSimpleGraphTest, ShortestPathOverMultipleEdges)

	TEST_F (FloydSimpleGraphTest, ShortestPathToLastNode)

	TEST_F (FloydSimpleGraphTest, UnreachableNodesHaveInfinity)

	TEST_F (FloydIntGraphTest, SymmetricGraph)

	TEST_F (FloydIntGraphTest, ShortcutUsed)

	TEST_F (FloydSimpleGraphTest, PathReconstructionSameNode)

	TEST_F (FloydSimpleGraphTest, PathReconstructionDirectEdge)

	TEST_F (FloydSimpleGraphTest, PathReconstructionMultipleEdges)

	TEST_F (FloydIntGraphTest, LatexOutputContainsBeginFigure)

	TEST_F (FloydIntGraphTest, LatexOutputContainsMatrices)

	TEST_F (FloydIntGraphTest, LatexOutputHasCorrectNumberOfIterations)

	TEST (SingleNodeTest, FloydOnSingleNode)

	TEST (TwoNodeTest, FloydOnTwoNodes)

	TEST (DisconnectedGraphTest, FloydOnDisconnectedGraph)

	TEST (DisconnectedGraphTest, UnreachableStaysInfinityWithNegativeEdges)

	TEST (CompleteGraphTest, FloydOnCompleteGraph)

	TEST (CustomSemiringTest, MaxMinSemiring)

	TEST (StressTest, FloydOnLargerGraph)

	TEST_F (FloydIntGraphTest, PathMatrixPointsToNextHop)

	TEST_F (FloydSimpleGraphTest, DistanceMatrixTriangleInequality)

	TEST_F (FloydIntGraphTest, InitializationSetsEdgeWeightsCorrectly)

	TEST (NegativeWeightsTest, FloydWithNegativeWeights)

	TEST (DenseGraphTest, FloydOnDenseGraph)

Detailed Description

Comprehensive tests for Floyd-Warshall algorithm (latex_floyd.H)

Tests cover:

floyd_all_shortest_paths() algorithm correctness
find_min_path() path reconstruction
floyd_all_shortest_paths_latex() LaTeX output format
Edge cases (single node, disconnected graphs, etc.)

Definition in file latex_floyd_test.cc.

Function Documentation

◆ TEST() [1/9]

TEST	(	CompleteGraphTest	,
		FloydOnCompleteGraph
	)

Definition at line 598 of file latex_floyd_test.cc.

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

◆ TEST() [2/9]

TEST	(	CustomSemiringTest	,
		MaxMinSemiring
	)

Definition at line 646 of file latex_floyd_test.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/9]

TEST	(	DenseGraphTest	,
		FloydOnDenseGraph
	)

Definition at line 832 of file latex_floyd_test.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::floyd_all_shortest_paths(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), IntDistanceArc::Max_Distance, N, and nodes.

◆ TEST() [4/9]

TEST	(	DisconnectedGraphTest	,
		FloydOnDisconnectedGraph
	)

Definition at line 520 of file latex_floyd_test.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::floyd_all_shortest_paths(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), and IntDistanceArc::Max_Distance.

◆ TEST() [5/9]

TEST	(	DisconnectedGraphTest	,
		UnreachableStaysInfinityWithNegativeEdges
	)

Definition at line 559 of file latex_floyd_test.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::floyd_all_shortest_paths(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), and IntDistanceArc::Max_Distance.

◆ TEST() [6/9]

TEST	(	NegativeWeightsTest	,
		FloydWithNegativeWeights
	)

Definition at line 796 of file latex_floyd_test.cc.

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

◆ TEST() [7/9]

TEST	(	SingleNodeTest	,
		FloydOnSingleNode
	)

Definition at line 477 of file latex_floyd_test.cc.

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

◆ TEST() [8/9]

TEST	(	StressTest	,
		FloydOnLargerGraph
	)

Definition at line 677 of file latex_floyd_test.cc.

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

◆ TEST() [9/9]

TEST	(	TwoNodeTest	,
		FloydOnTwoNodes
	)

Definition at line 493 of file latex_floyd_test.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::floyd_all_shortest_paths(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), and IntDistanceArc::Max_Distance.

◆ TEST_F() [1/16]

TEST_F	(	FloydIntGraphTest	,
		InitializationSetsEdgeWeightsCorrectly
	)

Definition at line 767 of file latex_floyd_test.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::floyd_all_shortest_paths(), and IntDistanceArc::Max_Distance.

◆ TEST_F() [2/16]

TEST_F	(	FloydIntGraphTest	,
		LatexOutputContainsBeginFigure
	)

Definition at line 394 of file latex_floyd_test.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::floyd_all_shortest_paths_latex(), and output.

◆ TEST_F() [3/16]

TEST_F	(	FloydIntGraphTest	,
		LatexOutputContainsMatrices
	)

Definition at line 419 of file latex_floyd_test.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::floyd_all_shortest_paths_latex(), and output.

◆ TEST_F() [4/16]

TEST_F	(	FloydIntGraphTest	,
		LatexOutputHasCorrectNumberOfIterations
	)

Definition at line 445 of file latex_floyd_test.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::floyd_all_shortest_paths_latex(), output, and Aleph::to_string().

◆ TEST_F() [5/16]

TEST_F	(	FloydIntGraphTest	,
		PathMatrixPointsToNextHop
	)

Definition at line 718 of file latex_floyd_test.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::floyd_all_shortest_paths(), IntDistanceArc::Max_Distance, and Aleph::next().

◆ TEST_F() [6/16]

TEST_F	(	FloydIntGraphTest	,
		ShortcutUsed
	)

Definition at line 281 of file latex_floyd_test.cc.

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

◆ TEST_F() [7/16]

TEST_F	(	FloydIntGraphTest	,
		SymmetricGraph
	)

Definition at line 265 of file latex_floyd_test.cc.

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

◆ TEST_F() [8/16]

TEST_F	(	FloydSimpleGraphTest	,
		DiagonalIsZero
	)

Definition at line 195 of file latex_floyd_test.cc.

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

◆ TEST_F() [9/16]

TEST_F	(	FloydSimpleGraphTest	,
		DirectEdgeDistance
	)

Definition at line 208 of file latex_floyd_test.cc.

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

◆ TEST_F() [10/16]

TEST_F	(	FloydSimpleGraphTest	,
		DistanceMatrixTriangleInequality
	)

Definition at line 741 of file latex_floyd_test.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::floyd_all_shortest_paths(), and k.

◆ TEST_F() [11/16]

TEST_F	(	FloydSimpleGraphTest	,
		PathReconstructionDirectEdge
	)

Definition at line 320 of file latex_floyd_test.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::find_min_path(), Aleph::floyd_all_shortest_paths(), and Aleph::Path< GT >::size().

◆ TEST_F() [12/16]

TEST_F	(	FloydSimpleGraphTest	,
		PathReconstructionMultipleEdges
	)

Definition at line 337 of file latex_floyd_test.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::find_min_path(), Aleph::floyd_all_shortest_paths(), and Aleph::Path< GT >::size().

◆ TEST_F() [13/16]

TEST_F	(	FloydSimpleGraphTest	,
		PathReconstructionSameNode
	)

Definition at line 304 of file latex_floyd_test.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::find_min_path(), Aleph::floyd_all_shortest_paths(), and Aleph::Path< GT >::size().

◆ TEST_F() [14/16]

TEST_F	(	FloydSimpleGraphTest	,
		ShortestPathOverMultipleEdges
	)

Definition at line 223 of file latex_floyd_test.cc.

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

◆ TEST_F() [15/16]

TEST_F	(	FloydSimpleGraphTest	,
		ShortestPathToLastNode
	)

Definition at line 237 of file latex_floyd_test.cc.

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

◆ TEST_F() [16/16]

TEST_F	(	FloydSimpleGraphTest	,
		UnreachableNodesHaveInfinity
	)

Definition at line 251 of file latex_floyd_test.cc.

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

Classes

Functions

Detailed Description

Function Documentation

◆ TEST() [1/9]

◆ TEST() [2/9]

◆ TEST() [3/9]

◆ TEST() [4/9]

◆ TEST() [5/9]

◆ TEST() [6/9]

◆ TEST() [7/9]

◆ TEST() [8/9]

◆ TEST() [9/9]

◆ TEST_F() [1/16]

◆ TEST_F() [2/16]

◆ TEST_F() [3/16]

◆ TEST_F() [4/16]

◆ TEST_F() [5/16]

◆ TEST_F() [6/16]

◆ TEST_F() [7/16]

◆ TEST_F() [8/16]

◆ TEST_F() [9/16]

◆ TEST_F() [10/16]

◆ TEST_F() [11/16]

◆ TEST_F() [12/16]

◆ TEST_F() [13/16]

◆ TEST_F() [14/16]

◆ TEST_F() [15/16]

◆ TEST_F() [16/16]