k_shortest_paths_test.cc File Reference

Tests for K_Shortest_Paths.H (Yen / Eppstein-style API). More...

#include <gtest/gtest.h>
#include <algorithm>
#include <chrono>
#include <cstdlib>
#include <functional>
#include <limits>
#include <random>
#include <string>
#include <tuple>
#include <utility>
#include <K_Shortest_Paths.H>
#include <tpl_array.H>
#include <tpl_dynArray.H>
#include <tpl_graph.H>
#include <tpl_olhash.H>

Include dependency graph for k_shortest_paths_test.cc:

Go to the source code of this file.

Functions
	TEST (KShortestPathsTest, YenKnownGraphProducesExpectedCosts)
	TEST (KShortestPathsTest, EppsteinApiMatchesYenOnKnownGraph)
	TEST (KShortestPathsTest, EppsteinCanReturnCyclicAlternatives)
	TEST (KShortestPathsTest, SourceEqualsTargetReturnsTrivialPath)
	TEST (KShortestPathsTest, UnreachableReturnsEmpty)
	TEST (KShortestPathsTest, NegativeWeightsThrowDomainError)
	TEST (KShortestPathsTest, RandomSmallGraphsMatchExactOracle)
	TEST (KShortestPathsTest, ReturnedPathsAreSimpleAndNonDecreasingCost)
	TEST (KShortestPathsTest, EppsteinResultsAreNonDecreasingCost)
	TEST (KShortestPathsTest, SelfLoopAndParallelArcs)
	TEST (KShortestPathsTest, PerfRegression)

Detailed Description

Tests for K_Shortest_Paths.H (Yen / Eppstein-style API).

Definition in file k_shortest_paths_test.cc.

Function Documentation

TEST() [1/11]

TEST	(	KShortestPathsTest	,
		EppsteinApiMatchesYenOnKnownGraph
	)

Definition at line 327 of file k_shortest_paths_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [2/11]

TEST	(	KShortestPathsTest	,
		EppsteinCanReturnCyclicAlternatives
	)

Definition at line 349 of file k_shortest_paths_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and nodes.

TEST() [3/11]

TEST	(	KShortestPathsTest	,
		EppsteinResultsAreNonDecreasingCost
	)

Definition at line 490 of file k_shortest_paths_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [4/11]

TEST	(	KShortestPathsTest	,
		NegativeWeightsThrowDomainError
	)

Definition at line 406 of file k_shortest_paths_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [5/11]

TEST	(	KShortestPathsTest	,
		PerfRegression
	)

Definition at line 589 of file k_shortest_paths_test.cc.

References Aleph::divide_and_conquer_partition_dp(), N, and rng.

TEST() [6/11]

TEST	(	KShortestPathsTest	,
		RandomSmallGraphsMatchExactOracle
	)

Definition at line 422 of file k_shortest_paths_test.cc.

References Aleph::divide_and_conquer_partition_dp(), nodes, and rng.

TEST() [7/11]

TEST	(	KShortestPathsTest	,
		ReturnedPathsAreSimpleAndNonDecreasingCost
	)

Definition at line 468 of file k_shortest_paths_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [8/11]

TEST	(	KShortestPathsTest	,
		SelfLoopAndParallelArcs
	)

Definition at line 511 of file k_shortest_paths_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and nodes.

TEST() [9/11]

TEST	(	KShortestPathsTest	,
		SourceEqualsTargetReturnsTrivialPath
	)

Definition at line 374 of file k_shortest_paths_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and nodes.

TEST() [10/11]

TEST	(	KShortestPathsTest	,
		UnreachableReturnsEmpty
	)

Definition at line 393 of file k_shortest_paths_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [11/11]

TEST	(	KShortestPathsTest	,
		YenKnownGraphProducesExpectedCosts
	)

Definition at line 306 of file k_shortest_paths_test.cc.

References Aleph::divide_and_conquer_partition_dp().