graph_traverse_test.cc File Reference

Tests for Graph Traverse. More...

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

Include dependency graph for graph_traverse_test.cc:

Go to the source code of this file.

Classes
class	GraphTraverseTest
class	DisconnectedGraphTest
class	TreeGraphTest
	Tree graph for graph_to_tree conversion testing. More...
class	CyclicGraphTest
class	DigraphTraverseTest
struct	EvenArcFilter< GT >

Typedefs
using	TestGraph = List_Graph< Graph_Node< int >, Graph_Arc< double > >
using	TestDigraph = List_Digraph< Graph_Node< int >, Graph_Arc< double > >

Functions
	TEST_F (GraphTraverseTest, DFSVisitsAllNodes)
	TEST_F (GraphTraverseTest, DFSStartsFromCorrectNode)
	TEST_F (GraphTraverseTest, DFSEarlyTermination)
	TEST_F (GraphTraverseTest, BFSVisitsAllNodes)
	TEST_F (TreeGraphTest, BFSVisitsInLevelOrder)
	TEST_F (GraphTraverseTest, BFSEarlyTermination)
	TEST_F (DisconnectedGraphTest, TraversalStopsAtComponentBoundary)
	TEST_F (DisconnectedGraphTest, CanTraverseSecondComponent)
	TEST_F (CyclicGraphTest, DFSHandlesCycle)
	TEST_F (CyclicGraphTest, BFSHandlesCycle)
	TEST_F (GraphTraverseTest, ExecProvidesArcInformation)
	TEST_F (GraphTraverseTest, ExecEarlyTermination)
	TEST_F (GraphTraverseTest, DualOpVisitsNodesAndArcs)
	TEST_F (GraphTraverseTest, DualOpNodeEarlyTermination)
	TEST_F (GraphTraverseTest, DualOpArcEarlyTermination)
	TEST_F (DigraphTraverseTest, DFSOnDigraph)
	TEST_F (DigraphTraverseTest, BFSOnDigraph)
	TEST (SingleNodeTest, DFSSingleNode)
	TEST (SingleNodeTest, BFSSingleNode)
	TEST_F (GraphTraverseTest, DFSWithArcFilter)
	TEST (LinearChainTest, DFSLinearChain)
	TEST (LinearChainTest, BFSLinearChain)
	TEST (CompleteGraphTest, DFSCompleteGraph)
	TEST (StressTest, LargeGraphDFS)
	TEST (StressTest, LargeGraphBFS)
int	main (int argc, char **argv)

Detailed Description

Tests for Graph Traverse.

Definition in file graph_traverse_test.cc.

Typedef Documentation

TestDigraph

using TestDigraph = List_Digraph<Graph_Node<int>, Graph_Arc<double> >

Definition at line 48 of file graph_traverse_test.cc.

TestGraph

using TestGraph = List_Graph<Graph_Node<int>, Graph_Arc<double> >

Definition at line 47 of file graph_traverse_test.cc.

Function Documentation

main()

int main	(	int	argc,
		char **	argv
	)

Definition at line 775 of file graph_traverse_test.cc.

References Aleph::maps().

TEST() [1/7]

TEST	(	CompleteGraphTest	,
		DFSCompleteGraph
	)

Definition at line 681 of file graph_traverse_test.cc.

References Aleph::count(), Aleph::DynList< T >::insert(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), Aleph::maps(), nodes, and Aleph::HTList::size().

TEST() [2/7]

TEST	(	LinearChainTest	,
		BFSLinearChain
	)

Definition at line 649 of file graph_traverse_test.cc.

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

TEST() [3/7]

TEST	(	LinearChainTest	,
		DFSLinearChain
	)

Definition at line 622 of file graph_traverse_test.cc.

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

TEST() [4/7]

TEST	(	SingleNodeTest	,
		BFSSingleNode
	)

Definition at line 563 of file graph_traverse_test.cc.

References Aleph::count(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), and Aleph::maps().

TEST() [5/7]

TEST	(	SingleNodeTest	,
		DFSSingleNode
	)

Definition at line 543 of file graph_traverse_test.cc.

References Aleph::count(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), and Aleph::maps().

TEST() [6/7]

TEST	(	StressTest	,
		LargeGraphBFS
	)

Definition at line 742 of file graph_traverse_test.cc.

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

TEST() [7/7]

TEST	(	StressTest	,
		LargeGraphDFS
	)

Definition at line 713 of file graph_traverse_test.cc.

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

TEST_F() [1/18]

TEST_F	(	CyclicGraphTest	,
		BFSHandlesCycle
	)

Definition at line 360 of file graph_traverse_test.cc.

References Aleph::count(), Aleph::DynList< T >::insert(), Aleph::maps(), nodes, and Aleph::HTList::size().

TEST_F() [2/18]

TEST_F	(	CyclicGraphTest	,
		DFSHandlesCycle
	)

Definition at line 342 of file graph_traverse_test.cc.

References Aleph::count(), Aleph::DynList< T >::insert(), Aleph::maps(), nodes, and Aleph::HTList::size().

TEST_F() [3/18]

TEST_F	(	DigraphTraverseTest	,
		BFSOnDigraph
	)

Definition at line 521 of file graph_traverse_test.cc.

References Aleph::maps(), nodes, and Aleph::HTList::size().

TEST_F() [4/18]

TEST_F	(	DigraphTraverseTest	,
		DFSOnDigraph
	)

Definition at line 502 of file graph_traverse_test.cc.

References Aleph::count(), Aleph::DynList< T >::insert(), Aleph::maps(), nodes, and Aleph::HTList::size().

TEST_F() [5/18]

TEST_F	(	DisconnectedGraphTest	,
		CanTraverseSecondComponent
	)

Definition at line 319 of file graph_traverse_test.cc.

References Aleph::count(), Aleph::DynList< T >::insert(), Aleph::maps(), and nodes.

TEST_F() [6/18]

TEST_F	(	DisconnectedGraphTest	,
		TraversalStopsAtComponentBoundary
	)

Definition at line 297 of file graph_traverse_test.cc.

References Aleph::count(), Aleph::DynList< T >::insert(), Aleph::maps(), and nodes.

TEST_F() [7/18]

TEST_F	(	GraphTraverseTest	,
		BFSEarlyTermination
	)

Definition at line 277 of file graph_traverse_test.cc.

References Aleph::count(), Aleph::maps(), and nodes.

TEST_F() [8/18]

TEST_F	(	GraphTraverseTest	,
		BFSVisitsAllNodes
	)

Definition at line 231 of file graph_traverse_test.cc.

References Aleph::count(), Aleph::DynList< T >::insert(), Aleph::maps(), nodes, and Aleph::HTList::size().

TEST_F() [9/18]

TEST_F	(	GraphTraverseTest	,
		DFSEarlyTermination
	)

Definition at line 210 of file graph_traverse_test.cc.

References Aleph::count(), Aleph::maps(), and nodes.

TEST_F() [10/18]

TEST_F	(	GraphTraverseTest	,
		DFSStartsFromCorrectNode
	)

Definition at line 193 of file graph_traverse_test.cc.

References Aleph::maps(), and nodes.

TEST_F() [11/18]

TEST_F	(	GraphTraverseTest	,
		DFSVisitsAllNodes
	)

Definition at line 174 of file graph_traverse_test.cc.

References Aleph::count(), Aleph::DynList< T >::insert(), Aleph::maps(), nodes, and Aleph::HTList::size().

TEST_F() [12/18]

TEST_F	(	GraphTraverseTest	,
		DFSWithArcFilter
	)

Definition at line 596 of file graph_traverse_test.cc.

References Aleph::count(), Aleph::DynList< T >::insert(), Aleph::maps(), and nodes.

TEST_F() [13/18]

TEST_F	(	GraphTraverseTest	,
		DualOpArcEarlyTermination
	)

Definition at line 475 of file graph_traverse_test.cc.

References Aleph::maps(), and nodes.

TEST_F() [14/18]

TEST_F	(	GraphTraverseTest	,
		DualOpNodeEarlyTermination
	)

Definition at line 452 of file graph_traverse_test.cc.

References Aleph::maps(), and nodes.

TEST_F() [15/18]

TEST_F	(	GraphTraverseTest	,
		DualOpVisitsNodesAndArcs
	)

Definition at line 425 of file graph_traverse_test.cc.

References Aleph::DynList< T >::insert(), Aleph::maps(), nodes, and Aleph::HTList::size().

TEST_F() [16/18]

TEST_F	(	GraphTraverseTest	,
		ExecEarlyTermination
	)

Definition at line 405 of file graph_traverse_test.cc.

References Aleph::count(), Graph_Traverse< GT, Itor, Q, Show_Arc >::exec(), Aleph::maps(), and nodes.

TEST_F() [17/18]

TEST_F	(	GraphTraverseTest	,
		ExecProvidesArcInformation
	)

Definition at line 381 of file graph_traverse_test.cc.

References Aleph::count(), Graph_Traverse< GT, Itor, Q, Show_Arc >::exec(), GTNodeCommon< NodeInfo >::get_info(), Aleph::maps(), nodes, and Aleph::HTList::size().

TEST_F() [18/18]

TEST_F	(	TreeGraphTest	,
		BFSVisitsInLevelOrder
	)

Definition at line 248 of file graph_traverse_test.cc.

References Aleph::maps(), and nodes.