Tests for Johnson. More...

#include <gtest/gtest.h>
#include <tpl_graph.H>
#include <Johnson.H>
#include <Dijkstra.H>
#include <Bellman_Ford.H>
#include <tpl_graph_utils.H>
#include <random>
#include <limits>
#include <vector>
#include <map>
#include <chrono>
#include <cmath>

Include dependency graph for johnson_test.cc:

Classes
struct	WeightedNode

struct	WeightedArc

struct	DoubleDistance

class	JohnsonTest

Typedefs
using	TestDigraph = List_Digraph< WeightedNode, WeightedArc >

using	Node = TestDigraph::Node

using	Arc = TestDigraph::Arc

Functions
	TEST_F (JohnsonTest, BellmanFordBasic)

	TEST_F (JohnsonTest, BellmanFordNegativeWeights)

	TEST_F (JohnsonTest, BellmanFordNegativeCycle)

	TEST_F (JohnsonTest, BellmanFordComputeNodesWeights)

	TEST_F (JohnsonTest, BellmanFordComputeNodesWeightsThrowsOnNegativeCycle)

	TEST_F (JohnsonTest, JohnsonBasicPath)

	TEST_F (JohnsonTest, JohnsonNegativeWeights)

	TEST_F (JohnsonTest, JohnsonNegativeCycleDetection)

	TEST_F (JohnsonTest, JohnsonAllPairs)

	TEST_F (JohnsonTest, ReweightingPreservesShortestPaths)

	TEST_F (JohnsonTest, DijkstraAfterReweighting)

	TEST_F (JohnsonTest, AllPairsSmallComplete)

	TEST_F (JohnsonTest, AllPairsSparse)

	TEST_F (JohnsonTest, SingleNode)

	TEST_F (JohnsonTest, TwoNodesNoEdge)

	TEST_F (JohnsonTest, TwoNodesOneEdge)

	TEST_F (JohnsonTest, SelfLoop)

	TEST_F (JohnsonTest, NegativeSelfLoop)

	TEST_F (JohnsonTest, ParallelEdges)

	TEST_F (JohnsonTest, MediumGraph)

	TEST_F (JohnsonTest, DISABLED_LargeGraphPerformance)

	TEST_F (JohnsonTest, CorrectnessVsFloydWarshall)

	TEST_F (JohnsonTest, SPFAvsStandard)

	TEST_F (JohnsonTest, NegativeCyclePathRetrieval)

	TEST_F (JohnsonTest, NegativeCycleNotReachable)

	TEST_F (JohnsonTest, ManualJohnsonImplementation)

int	main (int argc, char **argv)

Detailed Description

Tests for Johnson.

Intensive tests for Johnson's all-pairs shortest paths algorithm.

Tests cover:

Basic correctness on small graphs
Graphs with negative weights (but no negative cycles)
Detection of negative cycles
Comparison with Floyd-Warshall for verification
Sparse vs dense graphs performance characteristics
Edge cases: disconnected graphs, single node, etc.

Author: Generated for Aleph-w library

Definition in file johnson_test.cc.

Typedef Documentation

◆ Arc

using Arc = TestDigraph::Arc

Definition at line 83 of file johnson_test.cc.

◆ Node

using Node = TestDigraph::Node

Definition at line 82 of file johnson_test.cc.

◆ TestDigraph

using TestDigraph = List_Digraph<WeightedNode, WeightedArc>

Definition at line 81 of file johnson_test.cc.

Function Documentation

◆ main()

int main	(	int	argc,
		char **	argv
	)

Definition at line 888 of file johnson_test.cc.

References Aleph::maps().

◆ TEST_F() [1/26]

TEST_F	(	JohnsonTest	,
		AllPairsSmallComplete
	)

Definition at line 513 of file johnson_test.cc.

References Aleph::DynList< T >::empty(), StlAlephIterator< SetName >::end(), Aleph::maps(), and nodes.

◆ TEST_F() [2/26]

TEST_F	(	JohnsonTest	,
		AllPairsSparse
	)

Definition at line 531 of file johnson_test.cc.

References StlAlephIterator< SetName >::end(), Aleph::maps(), and nodes.

◆ TEST_F() [3/26]

TEST_F	(	JohnsonTest	,
		BellmanFordBasic
	)

Definition at line 253 of file johnson_test.cc.

TEST_F	(	JohnsonTest	,
		BellmanFordComputeNodesWeightsThrowsOnNegativeCycle
	)

Classes

Typedefs

Functions

Detailed Description

Typedef Documentation

◆ Arc

◆ Node

◆ TestDigraph

Function Documentation

◆ main()

◆ TEST_F() [1/26]

◆ TEST_F() [2/26]

◆ TEST_F() [3/26]

◆ TEST_F() [4/26]

◆ TEST_F() [5/26]

◆ TEST_F() [6/26]

◆ TEST_F() [7/26]

◆ TEST_F() [8/26]

◆ TEST_F() [9/26]

◆ TEST_F() [10/26]

◆ TEST_F() [11/26]

◆ TEST_F() [12/26]

◆ TEST_F() [13/26]

◆ TEST_F() [14/26]

◆ TEST_F() [15/26]

◆ TEST_F() [16/26]

◆ TEST_F() [17/26]

◆ TEST_F() [18/26]

◆ TEST_F() [19/26]

◆ TEST_F() [20/26]

◆ TEST_F() [21/26]

◆ TEST_F() [22/26]

◆ TEST_F() [23/26]

◆ TEST_F() [24/26]

◆ TEST_F() [25/26]

◆ TEST_F() [26/26]