tarjan_test.cc File Reference

Tests for Tarjan. More...

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

Include dependency graph for tarjan_test.cc:

Go to the source code of this file.

Classes
struct	SkipWeightZeroArcs

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

Functions
TestDigraph::Node *	add_node (TestDigraph &g, int value)
TestDigraph::Arc *	add_arc (TestDigraph &g, TestDigraph::Node *src, TestDigraph::Node *tgt, int value=0)
	TEST (TarjanTest, EmptyGraph)
	TEST (TarjanTest, SingleNodeNoLoop)
	TEST (TarjanTest, SingleNodeWithLoop)
	TEST (TarjanTest, TwoNodesNoCycle)
	TEST (TarjanTest, TwoNodesWithCycle)
	TEST (TarjanTest, LinearChain)
	TEST (TarjanTest, SimpleCycle)
	TEST (TarjanTest, MultipleSCCs)
	TEST (TarjanTest, ConnectedComponentsWithArcs)
	TEST (TarjanTest, ComputeCycleFromSource)
	TEST (TarjanTest, ComputeCycleInTestDigraphClass)
	TEST (TarjanTest, DiamondDAG)
	TEST (TarjanTest, ComplexNestedCycles)
	TEST (TarjanTest, DynDlistOverloads)
	TEST (TarjanTest, DisconnectedComponents)
	TEST (TarjanTest, LargeCycle)
	TEST (TarjanTest, SCCTree)
	TEST (TarjanTest, NumConnectedComponents)
	TEST (TarjanTest, NullSourceValidation)
	TEST (TarjanTest, FilterAccessor)
	TEST (TarjanTest, StateGetters)
	TEST (TarjanTest, MoveSemantics)
	TEST (TarjanTest, CustomArcFilter)
	TEST (TarjanTest, LargeGraphStress)
	TEST (TarjanTest, MultipleDisjointCycles)
	TEST (TarjanTest, CyclePathVerification)
	TEST (TarjanTest, CompleteDigraph)
	TEST (TarjanTest, ReuseInstance)
	TEST (TarjanExtended, StarGraphOutward)
	TEST (TarjanExtended, StarGraphInward)
	TEST (TarjanExtended, WheelGraph)
	TEST (TarjanExtended, BinaryTreeDAG)
	TEST (TarjanExtended, MultipleSelfLoops)
	TEST (TarjanExtended, ChainOfSCCs)
	TEST (TarjanExtended, DiamondPatternSCCs)
	TEST (TarjanExtended, BipartiteDAG)
	TEST (TarjanExtended, StronglyConnectedBipartite)
	TEST (TarjanExtended, GridDAG)
	TEST (TarjanExtended, GridWithCycles)
	TEST (TarjanExtended, DeepLinearChain)
	TEST (TarjanExtended, ConsistencyBetweenOverloads)
	TEST (TarjanExtended, CycleDetectionConsistency)
	TEST (TarjanExtended, LargeSCC)
	TEST (TarjanExtended, ManySmallSCCs)
	TEST (TarjanExtended, CyclePathDetails)
	TEST (TarjanExtended, EmptyGraphEdgeCases)
	TEST (TarjanExtended, ParallelArcs)
	TEST (TarjanExtended, TournamentGraph)
	TEST (TarjanExtended, DenseGraph)
	TEST (TarjanExtended, ComputeCycleNoCycle)

Detailed Description

Tests for Tarjan.

Definition in file tarjan_test.cc.

Typedef Documentation

TestDigraph

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

Definition at line 44 of file tarjan_test.cc.

Function Documentation

add_arc()

TestDigraph::Arc * add_arc	(	TestDigraph &	g,
		TestDigraph::Node *	src,
		TestDigraph::Node *	tgt,
		int	value = 0
	)

Definition at line 52 of file tarjan_test.cc.

References value.

Referenced by Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::create_dummy_node(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), and TEST_F().

add_node()

TestDigraph::Node * add_node	(	TestDigraph &	g,
		int	value
	)

Definition at line 47 of file tarjan_test.cc.

References value.

Referenced by Aleph::planarity_detail::collect_certificate_nodes(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), and TEST_F().

TEST() [1/50]

TEST	(	TarjanExtended	,
		BinaryTreeDAG
	)

Definition at line 1032 of file tarjan_test.cc.

References add_arc(), add_node(), Aleph::blossom_maximum_cardinality_matching(), and nodes.

TEST() [2/50]

TEST	(	TarjanExtended	,
		BipartiteDAG
	)

Definition at line 1175 of file tarjan_test.cc.

References add_arc(), add_node(), and Aleph::blossom_maximum_cardinality_matching().

TEST() [3/50]

TEST	(	TarjanExtended	,
		ChainOfSCCs
	)

Definition at line 1091 of file tarjan_test.cc.

References add_arc(), add_node(), and Aleph::blossom_maximum_cardinality_matching().

TEST() [4/50]

TEST	(	TarjanExtended	,
		ComputeCycleNoCycle
	)

Definition at line 1629 of file tarjan_test.cc.

References add_arc(), add_node(), and Aleph::blossom_maximum_cardinality_matching().

TEST() [5/50]

TEST	(	TarjanExtended	,
		ConsistencyBetweenOverloads
	)

Definition at line 1333 of file tarjan_test.cc.

References add_arc(), add_node(), Aleph::blossom_maximum_cardinality_matching(), and Aleph::HTList::size().

TEST() [6/50]

TEST	(	TarjanExtended	,
		CycleDetectionConsistency
	)

Definition at line 1399 of file tarjan_test.cc.

References add_node(), and Aleph::blossom_maximum_cardinality_matching().

TEST() [7/50]

TEST	(	TarjanExtended	,
		CyclePathDetails
	)

Definition at line 1484 of file tarjan_test.cc.

References add_arc(), add_node(), Aleph::blossom_maximum_cardinality_matching(), Aleph::Path< GT >::get_first_node(), Aleph::Path< GT >::get_last_node(), and Aleph::Dlink::Iterator::has_curr().

TEST() [8/50]

TEST	(	TarjanExtended	,
		DeepLinearChain
	)

Definition at line 1311 of file tarjan_test.cc.

References add_arc(), add_node(), Aleph::blossom_maximum_cardinality_matching(), and nodes.

TEST() [9/50]

TEST	(	TarjanExtended	,
		DenseGraph
	)

Definition at line 1601 of file tarjan_test.cc.

References add_arc(), add_node(), Aleph::blossom_maximum_cardinality_matching(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::connected_components(), N, and nodes.

TEST() [10/50]

TEST	(	TarjanExtended	,
		DiamondPatternSCCs
	)

Definition at line 1131 of file tarjan_test.cc.

References add_arc(), add_node(), Aleph::blossom_maximum_cardinality_matching(), l1, and l2.

TEST() [11/50]

TEST	(	TarjanExtended	,
		EmptyGraphEdgeCases
	)

Definition at line 1517 of file tarjan_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::HTList::is_empty().

TEST() [12/50]

TEST	(	TarjanExtended	,
		GridDAG
	)

Definition at line 1238 of file tarjan_test.cc.

References add_arc(), add_node(), Aleph::blossom_maximum_cardinality_matching(), and r.

TEST() [13/50]

TEST	(	TarjanExtended	,
		GridWithCycles
	)

Definition at line 1271 of file tarjan_test.cc.

References add_arc(), add_node(), Aleph::blossom_maximum_cardinality_matching(), and r.

TEST() [14/50]

TEST	(	TarjanExtended	,
		LargeSCC
	)

Definition at line 1423 of file tarjan_test.cc.

References add_arc(), add_node(), Aleph::blossom_maximum_cardinality_matching(), Aleph::DynList< T >::get_first(), N, nodes, and Aleph::HTList::size().

TEST() [15/50]

TEST	(	TarjanExtended	,
		ManySmallSCCs
	)

Definition at line 1457 of file tarjan_test.cc.

References add_arc(), add_node(), and Aleph::blossom_maximum_cardinality_matching().

TEST() [16/50]

TEST	(	TarjanExtended	,
		MultipleSelfLoops
	)

Definition at line 1068 of file tarjan_test.cc.

References add_arc(), add_node(), Aleph::blossom_maximum_cardinality_matching(), and N.

TEST() [17/50]

TEST	(	TarjanExtended	,
		ParallelArcs
	)

Definition at line 1540 of file tarjan_test.cc.

References add_arc(), add_node(), and Aleph::blossom_maximum_cardinality_matching().

TEST() [18/50]

TEST	(	TarjanExtended	,
		StarGraphInward
	)

Definition at line 980 of file tarjan_test.cc.

References add_arc(), add_node(), Aleph::blossom_maximum_cardinality_matching(), and N.

TEST() [19/50]

TEST	(	TarjanExtended	,
		StarGraphOutward
	)

Definition at line 956 of file tarjan_test.cc.

References add_arc(), add_node(), Aleph::blossom_maximum_cardinality_matching(), and N.

TEST() [20/50]

TEST	(	TarjanExtended	,
		StronglyConnectedBipartite
	)

Definition at line 1205 of file tarjan_test.cc.

References add_arc(), add_node(), and Aleph::blossom_maximum_cardinality_matching().

TEST() [21/50]

TEST	(	TarjanExtended	,
		TournamentGraph
	)

Definition at line 1569 of file tarjan_test.cc.

References add_arc(), add_node(), Aleph::blossom_maximum_cardinality_matching(), N, nodes, and Aleph::Tarjan_Connected_Components< GT, Itor, SA >::num_connected_components().

TEST() [22/50]

TEST	(	TarjanExtended	,
		WheelGraph
	)

Definition at line 1002 of file tarjan_test.cc.

References add_arc(), add_node(), Aleph::blossom_maximum_cardinality_matching(), and N.

TEST() [23/50]

TEST	(	TarjanTest	,
		CompleteDigraph
	)

Definition at line 896 of file tarjan_test.cc.

References add_arc(), add_node(), Aleph::blossom_maximum_cardinality_matching(), N, and nodes.

TEST() [24/50]

TEST	(	TarjanTest	,
		ComplexNestedCycles
	)

Definition at line 459 of file tarjan_test.cc.

References add_arc(), add_node(), Aleph::blossom_maximum_cardinality_matching(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::connected_components(), Aleph::Path< GT >::get_first_node(), and Aleph::Path< GT >::get_last_node().

TEST() [25/50]

TEST	(	TarjanTest	,
		ComputeCycleFromSource
	)

Definition at line 378 of file tarjan_test.cc.

References add_arc(), add_node(), and Aleph::blossom_maximum_cardinality_matching().

TEST() [26/50]

TEST	(	TarjanTest	,
		ComputeCycleInTestDigraphClass
	)

Definition at line 404 of file tarjan_test.cc.

References add_arc(), add_node(), Aleph::blossom_maximum_cardinality_matching(), and Aleph::Path< GT >::is_empty().

TEST() [27/50]

TEST	(	TarjanTest	,
		ConnectedComponentsWithArcs
	)

Definition at line 330 of file tarjan_test.cc.

References add_arc(), add_node(), Aleph::blossom_maximum_cardinality_matching(), and Aleph::HTList::size().

TEST() [28/50]

TEST	(	TarjanTest	,
		CustomArcFilter
	)

Definition at line 773 of file tarjan_test.cc.

References add_arc(), add_node(), and Aleph::blossom_maximum_cardinality_matching().

TEST() [29/50]

TEST	(	TarjanTest	,
		CyclePathVerification
	)

Definition at line 864 of file tarjan_test.cc.

References add_arc(), add_node(), Aleph::blossom_maximum_cardinality_matching(), Aleph::Path< GT >::get_first_node(), Aleph::Path< GT >::get_last_node(), Aleph::Dlink::Iterator::has_curr(), and Aleph::Path< GT >::is_empty().

TEST() [30/50]

TEST	(	TarjanTest	,
		DiamondDAG
	)

Definition at line 433 of file tarjan_test.cc.

References add_arc(), add_node(), Aleph::blossom_maximum_cardinality_matching(), and Aleph::Tarjan_Connected_Components< GT, Itor, SA >::connected_components().

TEST() [31/50]

TEST	(	TarjanTest	,
		DisconnectedComponents
	)

Definition at line 523 of file tarjan_test.cc.

References add_arc(), add_node(), Aleph::blossom_maximum_cardinality_matching(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::connected_components(), and Aleph::HTList::size().

TEST() [32/50]

TEST	(	TarjanTest	,
		DynDlistOverloads
	)

Definition at line 496 of file tarjan_test.cc.

References add_arc(), add_node(), Aleph::blossom_maximum_cardinality_matching(), and Aleph::Dlink::is_empty().

TEST() [33/50]

TEST	(	TarjanTest	,
		EmptyGraph
	)

Definition at line 61 of file tarjan_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::connected_components(), Aleph::HTList::is_empty(), and Aleph::Path< GT >::is_empty().

TEST() [34/50]

TEST	(	TarjanTest	,
		FilterAccessor
	)

Definition at line 701 of file tarjan_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::filter(), and Aleph::Tarjan_Connected_Components< GT, Itor, SA >::get_filter().

TEST() [35/50]

TEST	(	TarjanTest	,
		LargeCycle
	)

Definition at line 576 of file tarjan_test.cc.

References add_arc(), add_node(), Aleph::DynList< T >::append(), Aleph::blossom_maximum_cardinality_matching(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::connected_components(), N, and nodes.

TEST() [36/50]

TEST	(	TarjanTest	,
		LargeGraphStress
	)

Definition at line 797 of file tarjan_test.cc.

References add_arc(), add_node(), Aleph::blossom_maximum_cardinality_matching(), N, and nodes.

TEST() [37/50]

TEST	(	TarjanTest	,
		LinearChain
	)

Definition at line 229 of file tarjan_test.cc.

References add_arc(), add_node(), Aleph::blossom_maximum_cardinality_matching(), and Aleph::Tarjan_Connected_Components< GT, Itor, SA >::connected_components().

TEST() [38/50]

TEST	(	TarjanTest	,
		MoveSemantics
	)

Definition at line 738 of file tarjan_test.cc.

References add_arc(), add_node(), Aleph::blossom_maximum_cardinality_matching(), and Aleph::Tarjan_Connected_Components< GT, Itor, SA >::connected_components().

TEST() [39/50]

TEST	(	TarjanTest	,
		MultipleDisjointCycles
	)

Definition at line 826 of file tarjan_test.cc.

References add_arc(), add_node(), and Aleph::blossom_maximum_cardinality_matching().

TEST() [40/50]

TEST	(	TarjanTest	,
		MultipleSCCs
	)

Definition at line 284 of file tarjan_test.cc.

References add_arc(), add_node(), Aleph::blossom_maximum_cardinality_matching(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::connected_components(), and Aleph::HTList::size().

TEST() [41/50]

TEST	(	TarjanTest	,
		NullSourceValidation
	)

Definition at line 687 of file tarjan_test.cc.

References add_node(), and Aleph::blossom_maximum_cardinality_matching().

TEST() [42/50]

TEST	(	TarjanTest	,
		NumConnectedComponents
	)

Definition at line 659 of file tarjan_test.cc.

References add_arc(), add_node(), and Aleph::blossom_maximum_cardinality_matching().

TEST() [43/50]

TEST	(	TarjanTest	,
		ReuseInstance
	)

Definition at line 922 of file tarjan_test.cc.

References add_arc(), add_node(), and Aleph::blossom_maximum_cardinality_matching().

TEST() [44/50]

TEST	(	TarjanTest	,
		SCCTree
	)

Definition at line 614 of file tarjan_test.cc.

References add_arc(), add_node(), Aleph::blossom_maximum_cardinality_matching(), and Aleph::Tarjan_Connected_Components< GT, Itor, SA >::connected_components().

TEST() [45/50]

TEST	(	TarjanTest	,
		SimpleCycle
	)

Definition at line 254 of file tarjan_test.cc.

References add_arc(), add_node(), Aleph::blossom_maximum_cardinality_matching(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::connected_components(), Aleph::Path< GT >::get_first_node(), and Aleph::Path< GT >::get_last_node().

TEST() [46/50]

TEST	(	TarjanTest	,
		SingleNodeNoLoop
	)

Definition at line 93 of file tarjan_test.cc.

References add_node(), Aleph::blossom_maximum_cardinality_matching(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::connected_components(), Aleph::DynList< T >::get_first(), and Aleph::HTList::size().

TEST() [47/50]

TEST	(	TarjanTest	,
		SingleNodeWithLoop
	)

Definition at line 129 of file tarjan_test.cc.

References add_arc(), add_node(), Aleph::blossom_maximum_cardinality_matching(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::connected_components(), Aleph::Path< GT >::get_first_node(), Aleph::Path< GT >::get_last_node(), and Aleph::Path< GT >::is_empty().

TEST() [48/50]

TEST	(	TarjanTest	,
		StateGetters
	)

Definition at line 715 of file tarjan_test.cc.

References add_arc(), add_node(), and Aleph::blossom_maximum_cardinality_matching().

TEST() [49/50]

TEST	(	TarjanTest	,
		TwoNodesNoCycle
	)

Definition at line 163 of file tarjan_test.cc.

References add_arc(), add_node(), Aleph::blossom_maximum_cardinality_matching(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::connected_components(), and Aleph::HTList::size().

TEST() [50/50]

TEST	(	TarjanTest	,
		TwoNodesWithCycle
	)

Definition at line 197 of file tarjan_test.cc.

References add_arc(), add_node(), Aleph::blossom_maximum_cardinality_matching(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::connected_components(), Aleph::Path< GT >::get_first_node(), Aleph::Path< GT >::get_last_node(), and Aleph::Path< GT >::is_empty().