test_kosaraju.cc File Reference

Tests for Test Kosaraju. More...

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

Include dependency graph for test_kosaraju.cc:

Go to the source code of this file.

Typedefs
using	GT = List_Digraph< Graph_Node< int >, Graph_Arc< int > >
using	Node = GT::Node
using	Arc = GT::Arc

Functions
GT	create_chain (size_t n)
GT	create_cycle (size_t n)
size_t	count_total_nodes (const DynList< DynList< Node * > > &sccs)
	TEST (KosarajuTest, EmptyGraph)
	TEST (KosarajuTest, SingleNode)
	TEST (KosarajuTest, SingleNodeWithSelfLoop)
	TEST (KosarajuTest, TwoDisconnectedNodes)
	TEST (KosarajuTest, SimpleChain)
	TEST (KosarajuTest, SimpleCycle)
	TEST (KosarajuTest, TwoSeparateCycles)
	TEST (KosarajuTest, TwoCyclesConnectedByOneArc)
	TEST (KosarajuTest, TwoCyclesConnectedBidirectionally)
	TEST (KosarajuTest, ClassicCLRSExample)
	TEST (KosarajuTest, SubgraphVersion)
	TEST (KosarajuTest, CrossArcListCorrectness)
	TEST (KosarajuTest, IsStronglyConnectedTrue)
	TEST (KosarajuTest, IsStronglyConnectedFalse)
	TEST (KosarajuTest, IsStronglyConnectedEmpty)
	TEST (KosarajuTest, IsStronglyConnectedSingleNode)
	TEST (KosarajuTest, SccCount)
	TEST (KosarajuTest, FunctorInterface)
	TEST (KosarajuTest, LargeChain)
	TEST (KosarajuTest, LargeCycle)
	TEST (KosarajuTest, NodeMappingCorrectness)
	TEST (KosarajuTest, ArcMappingCorrectness)
	TEST (KosarajuTest, DiamondGraph)
	TEST (KosarajuTest, CompleteDigraph)
	TEST (KosarajuTest, MultipleSelfLoops)
	TEST (KosarajuTest, TreeStructure)
	TEST (KosarajuTest, CompareWithTarjan)
	TEST (KosarajuTest, StressTest)
	TEST (KosarajuTest, IsolatedNodesAndSCCs)
	TEST (KosarajuTest, ParallelArcs)
	TEST (KosarajuTest, DenseGraphPerformance)
	TEST (KosarajuTest, MultipleLoopsOnSameNode)
	TEST (KosarajuTest, NodesWithoutArcs)
	TEST (KosarajuTest, FullyBidirectionalGraph)
	TEST (KosarajuTest, TransposedCycleCorrectness)
int	main (int argc, char **argv)

Detailed Description

Tests for Test Kosaraju.

Definition in file test_kosaraju.cc.

Typedef Documentation

Arc

using Arc = GT::Arc

Definition at line 56 of file test_kosaraju.cc.

GT

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

Definition at line 54 of file test_kosaraju.cc.

Node

using Node = GT::Node

Definition at line 55 of file test_kosaraju.cc.

Function Documentation

count_total_nodes()

size_t count_total_nodes

(

const DynList< DynList< Node * > > &

sccs

)

Definition at line 83 of file test_kosaraju.cc.

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

Referenced by TEST(), TEST(), and TEST().

create_chain()

GT create_chain

(

size_t

n

)

Definition at line 61 of file test_kosaraju.cc.

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

Referenced by TEST(), TEST(), TEST(), and TEST().

create_cycle()

GT create_cycle

(

size_t

n

)

Definition at line 72 of file test_kosaraju.cc.

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

Referenced by TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

main()

int main	(	int	argc,
		char **	argv
	)

Definition at line 754 of file test_kosaraju.cc.

References Aleph::maps().

TEST() [1/35]

TEST	(	KosarajuTest	,
		ArcMappingCorrectness
	)

Definition at line 454 of file test_kosaraju.cc.

References Aleph::DynList< T >::get_first(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), Aleph::kosaraju_connected_components(), and Aleph::maps().

TEST() [2/35]

TEST	(	KosarajuTest	,
		ClassicCLRSExample
	)

Definition at line 234 of file test_kosaraju.cc.

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

TEST() [3/35]

TEST	(	KosarajuTest	,
		CompareWithTarjan
	)

Definition at line 576 of file test_kosaraju.cc.

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

TEST() [4/35]

TEST	(	KosarajuTest	,
		CompleteDigraph
	)

Definition at line 509 of file test_kosaraju.cc.

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

TEST() [5/35]

TEST	(	KosarajuTest	,
		CrossArcListCorrectness
	)

Definition at line 309 of file test_kosaraju.cc.

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

TEST() [6/35]

TEST	(	KosarajuTest	,
		DenseGraphPerformance
	)

Definition at line 661 of file test_kosaraju.cc.

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

TEST() [7/35]

TEST	(	KosarajuTest	,
		DiamondGraph
	)

Definition at line 482 of file test_kosaraju.cc.

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

TEST() [8/35]

TEST	(	KosarajuTest	,
		EmptyGraph
	)

Definition at line 91 of file test_kosaraju.cc.

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

TEST() [9/35]

TEST	(	KosarajuTest	,
		FullyBidirectionalGraph
	)

Definition at line 716 of file test_kosaraju.cc.

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

TEST() [10/35]

TEST	(	KosarajuTest	,
		FunctorInterface
	)

Definition at line 390 of file test_kosaraju.cc.

References create_cycle(), Aleph::DynList< T >::get_first(), Aleph::maps(), and Aleph::HTList::size().

TEST() [11/35]

TEST	(	KosarajuTest	,
		IsolatedNodesAndSCCs
	)

Definition at line 623 of file test_kosaraju.cc.

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

TEST() [12/35]

TEST	(	KosarajuTest	,
		IsStronglyConnectedEmpty
	)

Definition at line 359 of file test_kosaraju.cc.

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

TEST() [13/35]

TEST	(	KosarajuTest	,
		IsStronglyConnectedFalse
	)

Definition at line 352 of file test_kosaraju.cc.

References create_chain(), Aleph::is_strongly_connected(), and Aleph::maps().

TEST() [14/35]

TEST	(	KosarajuTest	,
		IsStronglyConnectedSingleNode
	)

Definition at line 366 of file test_kosaraju.cc.

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

TEST() [15/35]

TEST	(	KosarajuTest	,
		IsStronglyConnectedTrue
	)

Definition at line 345 of file test_kosaraju.cc.

References create_cycle(), Aleph::is_strongly_connected(), and Aleph::maps().

TEST() [16/35]

TEST	(	KosarajuTest	,
		LargeChain
	)

Definition at line 409 of file test_kosaraju.cc.

References create_chain(), Aleph::kosaraju_connected_components(), Aleph::maps(), and Aleph::HTList::size().

TEST() [17/35]

TEST	(	KosarajuTest	,
		LargeCycle
	)

Definition at line 418 of file test_kosaraju.cc.

References create_cycle(), Aleph::DynList< T >::get_first(), Aleph::kosaraju_connected_components(), Aleph::maps(), and Aleph::HTList::size().

TEST() [18/35]

TEST	(	KosarajuTest	,
		MultipleLoopsOnSameNode
	)

Definition at line 683 of file test_kosaraju.cc.

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

TEST() [19/35]

TEST	(	KosarajuTest	,
		MultipleSelfLoops
	)

Definition at line 530 of file test_kosaraju.cc.

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

TEST() [20/35]

TEST	(	KosarajuTest	,
		NodeMappingCorrectness
	)

Definition at line 428 of file test_kosaraju.cc.

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

TEST() [21/35]

TEST	(	KosarajuTest	,
		NodesWithoutArcs
	)

Definition at line 699 of file test_kosaraju.cc.

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

TEST() [22/35]

TEST	(	KosarajuTest	,
		ParallelArcs
	)

Definition at line 642 of file test_kosaraju.cc.

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

TEST() [23/35]

TEST	(	KosarajuTest	,
		SccCount
	)

Definition at line 374 of file test_kosaraju.cc.

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

TEST() [24/35]

TEST	(	KosarajuTest	,
		SimpleChain
	)

Definition at line 136 of file test_kosaraju.cc.

References create_chain(), Aleph::kosaraju_connected_components(), Aleph::maps(), and Aleph::HTList::size().

TEST() [25/35]

TEST	(	KosarajuTest	,
		SimpleCycle
	)

Definition at line 146 of file test_kosaraju.cc.

References create_cycle(), Aleph::DynList< T >::get_first(), Aleph::kosaraju_connected_components(), Aleph::maps(), and Aleph::HTList::size().

TEST() [26/35]

TEST	(	KosarajuTest	,
		SingleNode
	)

Definition at line 100 of file test_kosaraju.cc.

References Aleph::DynList< T >::get_first(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), Aleph::kosaraju_connected_components(), Aleph::maps(), and Aleph::HTList::size().

TEST() [27/35]

TEST	(	KosarajuTest	,
		SingleNodeWithSelfLoop
	)

Definition at line 111 of file test_kosaraju.cc.

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

TEST() [28/35]

TEST	(	KosarajuTest	,
		StressTest
	)

Definition at line 604 of file test_kosaraju.cc.

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

TEST() [29/35]

TEST	(	KosarajuTest	,
		SubgraphVersion
	)

Definition at line 272 of file test_kosaraju.cc.

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

TEST() [30/35]

TEST	(	KosarajuTest	,
		TransposedCycleCorrectness
	)

Definition at line 737 of file test_kosaraju.cc.

References create_chain(), Aleph::kosaraju_connected_components(), Aleph::maps(), and Aleph::HTList::size().

TEST() [31/35]

TEST	(	KosarajuTest	,
		TreeStructure
	)

Definition at line 548 of file test_kosaraju.cc.

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

TEST() [32/35]

TEST	(	KosarajuTest	,
		TwoCyclesConnectedBidirectionally
	)

Definition at line 207 of file test_kosaraju.cc.

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

TEST() [33/35]

TEST	(	KosarajuTest	,
		TwoCyclesConnectedByOneArc
	)

Definition at line 182 of file test_kosaraju.cc.

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

TEST() [34/35]

TEST	(	KosarajuTest	,
		TwoDisconnectedNodes
	)

Definition at line 123 of file test_kosaraju.cc.

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

TEST() [35/35]

TEST	(	KosarajuTest	,
		TwoSeparateCycles
	)

Definition at line 157 of file test_kosaraju.cc.

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