topological_sort_test.cc File Reference

Tests for Topological Sort. More...

#include <gtest/gtest.h>
#include <set>
#include <map>
#include <string>
#include <topological_sort.H>
#include <tpl_graph.H>

Include dependency graph for topological_sort_test.cc:

Go to the source code of this file.

Typedefs
using	TestDigraph = Aleph::List_Digraph< Aleph::Graph_Node< std::string >, Aleph::Graph_Arc< int > >

Functions
template<class List >
bool	is_valid_topological_order (const TestDigraph &g, const List &order)
	TEST (TopologicalSortDFS, EmptyGraph)
	TEST (TopologicalSortDFS, SingleNode)
	TEST (TopologicalSortDFS, TwoNodesOneArc)
	TEST (TopologicalSortDFS, LinearChain)
	TEST (TopologicalSortDFS, DiamondDAG)
	TEST (TopologicalSortDFS, DisconnectedComponents)
	TEST (TopologicalSortDFS, ComplexDAG)
	TEST (TopologicalSortDFS, OperatorOverload)
	TEST (QTopologicalSortBFS, EmptyGraph)
	TEST (QTopologicalSortBFS, SingleNode)
	TEST (QTopologicalSortBFS, TwoNodesOneArc)
	TEST (QTopologicalSortBFS, LinearChain)
	TEST (QTopologicalSortBFS, DiamondDAG)
	TEST (QTopologicalSortRanks, EmptyGraph)
	TEST (QTopologicalSortRanks, SingleNode)
	TEST (QTopologicalSortRanks, LinearChain)
	TEST (QTopologicalSortRanks, ParallelNodes)
	TEST (QTopologicalSortRanks, DiamondRanks)
	TEST (QTopologicalSortRanks, DisconnectedComponents)
	TEST (QTopologicalSortOperators, PerformOverload)
	TEST (QTopologicalSortOperators, RanksOverloadDynDlist)
	TEST (QTopologicalSortOperators, RanksOverloadDynList)
	TEST (TopologicalSortStress, LargeDAG)
	TEST (TopologicalSortStress, WideDAG)
	TEST (TopologicalSortComparison, BothAlgorithmsProduceValidOrder)

Detailed Description

Tests for Topological Sort.

Definition in file topological_sort_test.cc.

Typedef Documentation

TestDigraph

using TestDigraph = Aleph::List_Digraph<Aleph::Graph_Node<std::string>, Aleph::Graph_Arc<int> >

Definition at line 46 of file topological_sort_test.cc.

Function Documentation

is_valid_topological_order()

template<class List >

bool is_valid_topological_order	(	const TestDigraph &	g,
		const List &	order
	)

Definition at line 50 of file topological_sort_test.cc.

References Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne().

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

TEST() [1/25]

TEST	(	QTopologicalSortBFS	,
		DiamondDAG
	)

Definition at line 279 of file topological_sort_test.cc.

References Aleph::divide_and_conquer_partition_dp(), is_valid_topological_order(), and Aleph::Q_Topological_Sort< GT, Itor, SA >::perform().

TEST() [2/25]

TEST	(	QTopologicalSortBFS	,
		EmptyGraph
	)

Definition at line 225 of file topological_sort_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and Aleph::Q_Topological_Sort< GT, Itor, SA >::perform().

TEST() [3/25]

TEST	(	QTopologicalSortBFS	,
		LinearChain
	)

Definition at line 260 of file topological_sort_test.cc.

References Aleph::divide_and_conquer_partition_dp(), is_valid_topological_order(), and Aleph::Q_Topological_Sort< GT, Itor, SA >::perform().

TEST() [4/25]

TEST	(	QTopologicalSortBFS	,
		SingleNode
	)

Definition at line 234 of file topological_sort_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and Aleph::Q_Topological_Sort< GT, Itor, SA >::perform().

TEST() [5/25]

TEST	(	QTopologicalSortBFS	,
		TwoNodesOneArc
	)

Definition at line 246 of file topological_sort_test.cc.

References Aleph::divide_and_conquer_partition_dp(), is_valid_topological_order(), and Aleph::Q_Topological_Sort< GT, Itor, SA >::perform().

TEST() [6/25]

TEST	(	QTopologicalSortOperators	,
		PerformOverload
	)

Definition at line 440 of file topological_sort_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and Aleph::DynDlist< T >::size().

TEST() [7/25]

TEST	(	QTopologicalSortOperators	,
		RanksOverloadDynDlist
	)

Definition at line 454 of file topological_sort_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and Aleph::DynDlist< T >::size().

TEST() [8/25]

TEST	(	QTopologicalSortOperators	,
		RanksOverloadDynList
	)

Definition at line 468 of file topological_sort_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and Aleph::HTList::size().

TEST() [9/25]

TEST	(	QTopologicalSortRanks	,
		DiamondRanks
	)

Definition at line 373 of file topological_sort_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and Aleph::Q_Topological_Sort< GT, Itor, SA >::ranks().

TEST() [10/25]

TEST	(	QTopologicalSortRanks	,
		DisconnectedComponents
	)

Definition at line 414 of file topological_sort_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and Aleph::Q_Topological_Sort< GT, Itor, SA >::ranks().

TEST() [11/25]

TEST	(	QTopologicalSortRanks	,
		EmptyGraph
	)

Definition at line 301 of file topological_sort_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and Aleph::Q_Topological_Sort< GT, Itor, SA >::ranks().

TEST() [12/25]

TEST	(	QTopologicalSortRanks	,
		LinearChain
	)

Definition at line 323 of file topological_sort_test.cc.

References Aleph::divide_and_conquer_partition_dp(), nodes, and Aleph::Q_Topological_Sort< GT, Itor, SA >::ranks().

TEST() [13/25]

TEST	(	QTopologicalSortRanks	,
		ParallelNodes
	)

Definition at line 343 of file topological_sort_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and Aleph::Q_Topological_Sort< GT, Itor, SA >::ranks().

TEST() [14/25]

TEST	(	QTopologicalSortRanks	,
		SingleNode
	)

Definition at line 310 of file topological_sort_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and Aleph::Q_Topological_Sort< GT, Itor, SA >::ranks().

TEST() [15/25]

TEST	(	TopologicalSortComparison	,
		BothAlgorithmsProduceValidOrder
	)

Definition at line 537 of file topological_sort_test.cc.

References Aleph::divide_and_conquer_partition_dp(), is_valid_topological_order(), Aleph::Topological_Sort< GT, Itor, SA >::perform(), and Aleph::Q_Topological_Sort< GT, Itor, SA >::perform().

TEST() [16/25]

TEST	(	TopologicalSortDFS	,
		ComplexDAG
	)

Definition at line 179 of file topological_sort_test.cc.

References Aleph::divide_and_conquer_partition_dp(), is_valid_topological_order(), and Aleph::Topological_Sort< GT, Itor, SA >::perform().

TEST() [17/25]

TEST	(	TopologicalSortDFS	,
		DiamondDAG
	)

Definition at line 134 of file topological_sort_test.cc.

References Aleph::divide_and_conquer_partition_dp(), is_valid_topological_order(), and Aleph::Topological_Sort< GT, Itor, SA >::perform().

TEST() [18/25]

TEST	(	TopologicalSortDFS	,
		DisconnectedComponents
	)

Definition at line 161 of file topological_sort_test.cc.

References Aleph::divide_and_conquer_partition_dp(), is_valid_topological_order(), and Aleph::Topological_Sort< GT, Itor, SA >::perform().

TEST() [19/25]

TEST	(	TopologicalSortDFS	,
		EmptyGraph
	)

Definition at line 77 of file topological_sort_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and Aleph::Topological_Sort< GT, Itor, SA >::perform().

TEST() [20/25]

TEST	(	TopologicalSortDFS	,
		LinearChain
	)

Definition at line 115 of file topological_sort_test.cc.

References Aleph::divide_and_conquer_partition_dp(), is_valid_topological_order(), and Aleph::Topological_Sort< GT, Itor, SA >::perform().

TEST() [21/25]

TEST	(	TopologicalSortDFS	,
		OperatorOverload
	)

Definition at line 208 of file topological_sort_test.cc.

References Aleph::divide_and_conquer_partition_dp(), is_valid_topological_order(), and Aleph::DynDlist< T >::size().

TEST() [22/25]

TEST	(	TopologicalSortDFS	,
		SingleNode
	)

Definition at line 86 of file topological_sort_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and Aleph::Topological_Sort< GT, Itor, SA >::perform().

TEST() [23/25]

TEST	(	TopologicalSortDFS	,
		TwoNodesOneArc
	)

Definition at line 98 of file topological_sort_test.cc.

References Aleph::divide_and_conquer_partition_dp(), is_valid_topological_order(), and Aleph::Topological_Sort< GT, Itor, SA >::perform().

TEST() [24/25]

TEST	(	TopologicalSortStress	,
		LargeDAG
	)

Definition at line 484 of file topological_sort_test.cc.

References Aleph::DynArray< T >::append(), Aleph::divide_and_conquer_partition_dp(), is_valid_topological_order(), N, nodes, Aleph::Topological_Sort< GT, Itor, SA >::perform(), and Aleph::Q_Topological_Sort< GT, Itor, SA >::perform().

TEST() [25/25]

TEST	(	TopologicalSortStress	,
		WideDAG
	)

Definition at line 514 of file topological_sort_test.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Array< T >::get_first(), Aleph::Array< T >::get_last(), Aleph::ranks(), Aleph::Array< T >::size(), and WIDTH.