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)
	TEST (SelfLoopTest, SingleOpVisitsStartOnce)
	TEST (SelfLoopTest, ExecVisitsStartOnce)
	TEST (SelfLoopTest, DualOpVisitsStartOnceAndSkipsSelfLoopArc)
	TEST (SelfLoopTest, MidTraversalSelfLoopDoesNotBlockDiscovery)
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 889 of file graph_traverse_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST() [1/11]

TEST	(	CompleteGraphTest	,
		DFSCompleteGraph
	)

Definition at line 681 of file graph_traverse_test.cc.

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

TEST() [2/11]

TEST	(	LinearChainTest	,
		BFSLinearChain
	)

Definition at line 649 of file graph_traverse_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() [3/11]

TEST	(	LinearChainTest	,
		DFSLinearChain
	)

Definition at line 622 of file graph_traverse_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	(	SelfLoopTest	,
		DualOpVisitsStartOnceAndSkipsSelfLoopArc
	)

Definition at line 830 of file graph_traverse_test.cc.

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

TEST() [5/11]

TEST	(	SelfLoopTest	,
		ExecVisitsStartOnce
	)

Definition at line 811 of file graph_traverse_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::count(), Graph_Traverse< GT, Itor, Q, Show_Arc >::exec(), GTNodeCommon< NodeInfo >::get_info(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), and Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node().

TEST() [6/11]

TEST	(	SelfLoopTest	,
		MidTraversalSelfLoopDoesNotBlockDiscovery
	)

Definition at line 861 of file graph_traverse_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::count(), GTNodeCommon< NodeInfo >::get_info(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), and Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node().

TEST() [7/11]

TEST	(	SelfLoopTest	,
		SingleOpVisitsStartOnce
	)

Definition at line 783 of file graph_traverse_test.cc.

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

TEST() [8/11]

TEST	(	SingleNodeTest	,
		BFSSingleNode
	)

Definition at line 563 of file graph_traverse_test.cc.

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

TEST() [9/11]

TEST	(	SingleNodeTest	,
		DFSSingleNode
	)

Definition at line 543 of file graph_traverse_test.cc.

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

TEST() [10/11]

TEST	(	StressTest	,
		LargeGraphBFS
	)

Definition at line 742 of file graph_traverse_test.cc.

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

TEST() [11/11]

TEST	(	StressTest	,
		LargeGraphDFS
	)

Definition at line 713 of file graph_traverse_test.cc.

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

TEST_F() [1/18]

TEST_F	(	CyclicGraphTest	,
		BFSHandlesCycle
	)

Definition at line 360 of file graph_traverse_test.cc.

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

TEST_F() [2/18]

TEST_F	(	CyclicGraphTest	,
		DFSHandlesCycle
	)

Definition at line 342 of file graph_traverse_test.cc.

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

TEST_F() [3/18]

TEST_F	(	DigraphTraverseTest	,
		BFSOnDigraph
	)

Definition at line 521 of file graph_traverse_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and nodes.

TEST_F() [4/18]

TEST_F	(	DigraphTraverseTest	,
		DFSOnDigraph
	)

Definition at line 502 of file graph_traverse_test.cc.

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

TEST_F() [5/18]

TEST_F	(	DisconnectedGraphTest	,
		CanTraverseSecondComponent
	)

Definition at line 319 of file graph_traverse_test.cc.

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

TEST_F() [6/18]

TEST_F	(	DisconnectedGraphTest	,
		TraversalStopsAtComponentBoundary
	)

Definition at line 297 of file graph_traverse_test.cc.

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

TEST_F() [7/18]

TEST_F	(	GraphTraverseTest	,
		BFSEarlyTermination
	)

Definition at line 277 of file graph_traverse_test.cc.

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

TEST_F() [8/18]

TEST_F	(	GraphTraverseTest	,
		BFSVisitsAllNodes
	)

Definition at line 231 of file graph_traverse_test.cc.

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

TEST_F() [9/18]

TEST_F	(	GraphTraverseTest	,
		DFSEarlyTermination
	)

Definition at line 210 of file graph_traverse_test.cc.

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

TEST_F() [10/18]

TEST_F	(	GraphTraverseTest	,
		DFSStartsFromCorrectNode
	)

Definition at line 193 of file graph_traverse_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and nodes.

TEST_F() [11/18]

TEST_F	(	GraphTraverseTest	,
		DFSVisitsAllNodes
	)

Definition at line 174 of file graph_traverse_test.cc.

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

TEST_F() [12/18]

TEST_F	(	GraphTraverseTest	,
		DFSWithArcFilter
	)

Definition at line 596 of file graph_traverse_test.cc.

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

TEST_F() [13/18]

TEST_F	(	GraphTraverseTest	,
		DualOpArcEarlyTermination
	)

Definition at line 475 of file graph_traverse_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and nodes.

TEST_F() [14/18]

TEST_F	(	GraphTraverseTest	,
		DualOpNodeEarlyTermination
	)

Definition at line 452 of file graph_traverse_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and nodes.

TEST_F() [15/18]

TEST_F	(	GraphTraverseTest	,
		DualOpVisitsNodesAndArcs
	)

Definition at line 425 of file graph_traverse_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and nodes.

TEST_F() [16/18]

TEST_F	(	GraphTraverseTest	,
		ExecEarlyTermination
	)

Definition at line 405 of file graph_traverse_test.cc.

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

TEST_F() [17/18]

TEST_F	(	GraphTraverseTest	,
		ExecProvidesArcInformation
	)

Definition at line 381 of file graph_traverse_test.cc.

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

TEST_F() [18/18]

TEST_F	(	TreeGraphTest	,
		BFSVisitsInLevelOrder
	)

Definition at line 248 of file graph_traverse_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and nodes.