hamiltonian_test.cc File Reference

Comprehensive tests for Hamiltonian sufficiency testing (hamiltonian.H) More...

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

Include dependency graph for hamiltonian_test.cc:

Go to the source code of this file.

Classes
class	HamiltonianUndirectedTest
class	HamiltonianDigraphTest

Functions
	TEST_F (HamiltonianUndirectedTest, CompleteGraphK3)
	TEST_F (HamiltonianUndirectedTest, CompleteGraphK4)
	TEST_F (HamiltonianUndirectedTest, CompleteGraphK5)
	TEST_F (HamiltonianUndirectedTest, CompleteGraphK10)
	TEST_F (HamiltonianUndirectedTest, CycleGraph)
	TEST_F (HamiltonianUndirectedTest, PathGraph)
	TEST_F (HamiltonianUndirectedTest, HighDegreeGraph)
	TEST_F (HamiltonianUndirectedTest, StarGraph)
	TEST_F (HamiltonianUndirectedTest, PetersenGraphLike)
	TEST_F (HamiltonianUndirectedTest, NearlyCompleteGraph)
	TEST_F (HamiltonianUndirectedTest, BipartiteK33)
	TEST_F (HamiltonianDigraphTest, CompleteDigraph)
	TEST_F (HamiltonianDigraphTest, DirectedCycle)
	TEST_F (HamiltonianDigraphTest, DirectedPath)
	TEST_F (HamiltonianDigraphTest, TournamentGraph)
	TEST_F (HamiltonianUndirectedTest, TwoNodes)
	TEST_F (HamiltonianUndirectedTest, TwoNodesDisconnected)
	TEST_F (HamiltonianUndirectedTest, LargeCompleteGraph)
	TEST_F (HamiltonianUndirectedTest, DiracCompleteGraphK4)
	TEST_F (HamiltonianUndirectedTest, DiracCompleteGraphK5)
	TEST_F (HamiltonianUndirectedTest, DiracCycleFails)
	TEST_F (HamiltonianUndirectedTest, DiracVsOre)
	TEST_F (HamiltonianUndirectedTest, DiracTwoNodes)
	TEST_F (HamiltonianUndirectedTest, DiracImpliesOre)
	TEST_F (HamiltonianDigraphTest, DiracCompleteTournament)
int	main (int argc, char **argv)

Detailed Description

Comprehensive tests for Hamiltonian sufficiency testing (hamiltonian.H)

Tests Ore's theorem: For n ≥ 3, if deg(u) + deg(v) ≥ n for every pair of non-adjacent vertices u and v, then the graph is Hamiltonian.

Definition in file hamiltonian_test.cc.

Function Documentation

main()

int main	(	int	argc,
		char **	argv
	)

Definition at line 517 of file hamiltonian_test.cc.

References Aleph::maps().

TEST_F() [1/25]

TEST_F	(	HamiltonianDigraphTest	,
		CompleteDigraph
	)

Definition at line 293 of file hamiltonian_test.cc.

References add_arc(), add_node(), Aleph::maps(), and test().

TEST_F() [2/25]

TEST_F	(	HamiltonianDigraphTest	,
		DiracCompleteTournament
	)

Definition at line 494 of file hamiltonian_test.cc.

References add_arc(), add_node(), Aleph::maps(), nodes, and test().

TEST_F() [3/25]

TEST_F	(	HamiltonianDigraphTest	,
		DirectedCycle
	)

Definition at line 310 of file hamiltonian_test.cc.

References add_arc(), add_node(), Aleph::maps(), and test().

TEST_F() [4/25]

TEST_F	(	HamiltonianDigraphTest	,
		DirectedPath
	)

Definition at line 327 of file hamiltonian_test.cc.

References add_arc(), add_node(), Aleph::maps(), and test().

TEST_F() [5/25]

TEST_F	(	HamiltonianDigraphTest	,
		TournamentGraph
	)

Definition at line 341 of file hamiltonian_test.cc.

References add_arc(), add_node(), Aleph::maps(), and test().

TEST_F() [6/25]

TEST_F	(	HamiltonianUndirectedTest	,
		BipartiteK33
	)

Definition at line 267 of file hamiltonian_test.cc.

References add_edge(), add_node(), Aleph::maps(), and test().

TEST_F() [7/25]

TEST_F	(	HamiltonianUndirectedTest	,
		CompleteGraphK10
	)

Definition at line 136 of file hamiltonian_test.cc.

References build_complete_graph(), Aleph::maps(), and test().

TEST_F() [8/25]

TEST_F	(	HamiltonianUndirectedTest	,
		CompleteGraphK3
	)

Definition at line 107 of file hamiltonian_test.cc.

References build_complete_graph(), Aleph::maps(), and test().

TEST_F() [9/25]

TEST_F	(	HamiltonianUndirectedTest	,
		CompleteGraphK4
	)

Definition at line 117 of file hamiltonian_test.cc.

References build_complete_graph(), Aleph::maps(), and test().

TEST_F() [10/25]

TEST_F	(	HamiltonianUndirectedTest	,
		CompleteGraphK5
	)

Definition at line 127 of file hamiltonian_test.cc.

References build_complete_graph(), Aleph::maps(), and test().

TEST_F() [11/25]

TEST_F	(	HamiltonianUndirectedTest	,
		CycleGraph
	)

Definition at line 145 of file hamiltonian_test.cc.

References add_edge(), add_node(), Aleph::maps(), and test().

TEST_F() [12/25]

TEST_F	(	HamiltonianUndirectedTest	,
		DiracCompleteGraphK4
	)

Definition at line 400 of file hamiltonian_test.cc.

References build_complete_graph(), Aleph::maps(), and test().

TEST_F() [13/25]

TEST_F	(	HamiltonianUndirectedTest	,
		DiracCompleteGraphK5
	)

Definition at line 411 of file hamiltonian_test.cc.

References build_complete_graph(), Aleph::maps(), and test().

TEST_F() [14/25]

TEST_F	(	HamiltonianUndirectedTest	,
		DiracCycleFails
	)

Definition at line 422 of file hamiltonian_test.cc.

References add_edge(), add_node(), Aleph::maps(), nodes, and test().

TEST_F() [15/25]

TEST_F	(	HamiltonianUndirectedTest	,
		DiracImpliesOre
	)

Definition at line 478 of file hamiltonian_test.cc.

References build_complete_graph(), and Aleph::maps().

TEST_F() [16/25]

TEST_F	(	HamiltonianUndirectedTest	,
		DiracTwoNodes
	)

Definition at line 467 of file hamiltonian_test.cc.

References add_edge(), add_node(), Aleph::maps(), and test().

TEST_F() [17/25]

TEST_F	(	HamiltonianUndirectedTest	,
		DiracVsOre
	)

Definition at line 441 of file hamiltonian_test.cc.

References add_edge(), add_node(), and Aleph::maps().

TEST_F() [18/25]

TEST_F	(	HamiltonianUndirectedTest	,
		HighDegreeGraph
	)

Definition at line 185 of file hamiltonian_test.cc.

References add_edge(), add_node(), Aleph::maps(), and test().

TEST_F() [19/25]

TEST_F	(	HamiltonianUndirectedTest	,
		LargeCompleteGraph
	)

Definition at line 387 of file hamiltonian_test.cc.

References build_complete_graph(), Aleph::maps(), and test().

TEST_F() [20/25]

TEST_F	(	HamiltonianUndirectedTest	,
		NearlyCompleteGraph
	)

Definition at line 247 of file hamiltonian_test.cc.

References add_edge(), add_node(), Aleph::maps(), and test().

TEST_F() [21/25]

TEST_F	(	HamiltonianUndirectedTest	,
		PathGraph
	)

Definition at line 167 of file hamiltonian_test.cc.

References add_edge(), add_node(), Aleph::maps(), and test().

TEST_F() [22/25]

TEST_F	(	HamiltonianUndirectedTest	,
		PetersenGraphLike
	)

Definition at line 228 of file hamiltonian_test.cc.

References add_edge(), add_node(), Aleph::maps(), and test().

TEST_F() [23/25]

TEST_F	(	HamiltonianUndirectedTest	,
		StarGraph
	)

Definition at line 208 of file hamiltonian_test.cc.

References add_edge(), add_node(), Aleph::maps(), and test().

TEST_F() [24/25]

TEST_F	(	HamiltonianUndirectedTest	,
		TwoNodes
	)

Definition at line 364 of file hamiltonian_test.cc.

References add_edge(), add_node(), Aleph::maps(), and test().

TEST_F() [25/25]

TEST_F	(	HamiltonianUndirectedTest	,
		TwoNodesDisconnected
	)

Definition at line 376 of file hamiltonian_test.cc.

References add_node(), Aleph::maps(), and test().