graph_traverse_generators_test.cc File Reference

Tests for lazy graph traversal (graph-traverse-generators.H). More...

#include <set>
#include <stdexcept>
#include <type_traits>
#include <vector>
#include <gtest/gtest.h>
#include <graph-traverse-generators.H>
#include <graph-traverse.H>
#include <tpl_graph.H>

Include dependency graph for graph_traverse_generators_test.cc:

Go to the source code of this file.

Typedefs
using	BfsGen = Graph_Traverse_BFS_Generator< TestGraph, Itor >

Functions
	TEST (GraphTraverseGenerators, SingleNodeGraph)
	TEST (GraphTraverseGenerators, NullStartThrowsInvalidArgument)
	TEST (GraphTraverseGenerators, BfsVisitsAllReachableNodesExactlyOnce)
	TEST (GraphTraverseGenerators, BfsOrderMatchesEagerBfsOrder)
	TEST (GraphTraverseGenerators, DfsOrderMatchesEagerDfsOrder)
	TEST (GraphTraverseGenerators, DisconnectedGraphOnlyVisitsReachableComponent)
	TEST (GraphTraverseGenerators, EarlyBreakStopsTraversal)
	TEST (GraphTraverseGenerators, SelfLoopAtStartNodeYieldsOnce)
	TEST (GraphTraverseGenerators, SelfLoopMidTraversalYieldsOnce)
	TEST (GraphTraverseGenerators, CyclicGraphTerminates)
	TEST (GraphTraverseGenerators, DigraphRespectsArcDirection)

Detailed Description

Tests for lazy graph traversal (graph-traverse-generators.H).

Property tests comparing Graph_Traverse_BFS_Generator/ Graph_Traverse_DFS_Generator against the eager Graph_Traverse_BFS/ Graph_Traverse_DFS from graph-traverse.H: same set of visited nodes, same count, and (for BFS) the same level-by-level order. Also covers a single-node graph, a disconnected graph (unreachable nodes are not visited), early break, and a digraph.

Definition in file graph_traverse_generators_test.cc.

Typedef Documentation

BfsGen

using BfsGen = Graph_Traverse_BFS_Generator<TestGraph, Itor>

Definition at line 99 of file graph_traverse_generators_test.cc.

Function Documentation

TEST() [1/11]

TEST	(	GraphTraverseGenerators	,
		BfsOrderMatchesEagerBfsOrder
	)

Definition at line 148 of file graph_traverse_generators_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), GTNodeCommon< NodeInfo >::get_info(), and nodes.

TEST() [2/11]

TEST	(	GraphTraverseGenerators	,
		BfsVisitsAllReachableNodesExactlyOnce
	)

Definition at line 132 of file graph_traverse_generators_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), nodes, and Aleph::Graph_Traverse_Generator< GT, Itor, Q, Show_Arc >::traverse().

TEST() [3/11]

TEST	(	GraphTraverseGenerators	,
		CyclicGraphTerminates
	)

Definition at line 269 of file graph_traverse_generators_test.cc.

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

TEST() [4/11]

TEST	(	GraphTraverseGenerators	,
		DfsOrderMatchesEagerDfsOrder
	)

Definition at line 168 of file graph_traverse_generators_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), GTNodeCommon< NodeInfo >::get_info(), and nodes.

TEST() [5/11]

TEST	(	GraphTraverseGenerators	,
		DigraphRespectsArcDirection
	)

Definition at line 290 of file graph_traverse_generators_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), nodes, and Aleph::Graph_Traverse_Generator< GT, Itor, Q, Show_Arc >::traverse().

TEST() [6/11]

TEST	(	GraphTraverseGenerators	,
		DisconnectedGraphOnlyVisitsReachableComponent
	)

Definition at line 188 of file graph_traverse_generators_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), nodes, and Aleph::Graph_Traverse_Generator< GT, Itor, Q, Show_Arc >::traverse().

TEST() [7/11]

TEST	(	GraphTraverseGenerators	,
		EarlyBreakStopsTraversal
	)

Definition at line 207 of file graph_traverse_generators_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), nodes, and Aleph::Graph_Traverse_Generator< GT, Itor, Q, Show_Arc >::traverse().

TEST() [8/11]

TEST	(	GraphTraverseGenerators	,
		NullStartThrowsInvalidArgument
	)

Definition at line 119 of file graph_traverse_generators_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Graph_Traverse_Generator< GT, Itor, Q, Show_Arc >::traverse().

TEST() [9/11]

TEST	(	GraphTraverseGenerators	,
		SelfLoopAtStartNodeYieldsOnce
	)

Definition at line 228 of file graph_traverse_generators_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), and Aleph::Graph_Traverse_Generator< GT, Itor, Q, Show_Arc >::traverse().

TEST() [10/11]

TEST	(	GraphTraverseGenerators	,
		SelfLoopMidTraversalYieldsOnce
	)

Definition at line 252 of file graph_traverse_generators_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), and Aleph::Graph_Traverse_Generator< GT, Itor, Q, Show_Arc >::traverse().

TEST() [11/11]

TEST	(	GraphTraverseGenerators	,
		SingleNodeGraph
	)

Definition at line 107 of file graph_traverse_generators_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), and Aleph::Graph_Traverse_Generator< GT, Itor, Q, Show_Arc >::traverse().