test_kruskal.cc File Reference

GoogleTest suite for Kruskal.H. More...

#include <gtest/gtest.h>
#include <limits>
#include <random>
#include <set>
#include <vector>
#include <Kruskal.H>
#include <tpl_graph.H>
#include <tpl_sgraph.H>
#include <tpl_agraph.H>

Include dependency graph for test_kruskal.cc:

Go to the source code of this file.

Typedefs
using	GT = List_Graph< Graph_Node< int >, Graph_Arc< int > >
using	Node = GT::Node
using	Arc = GT::Arc
using	AGT = Array_Graph< Graph_Anode< int >, Graph_Aarc< int > >
using	ANode = AGT::Node
using	AArc = AGT::Arc

Functions
	TEST (KruskalTest, SimpleConnectedGraph)
	TEST (KruskalTest, SingleNodeGraph)
	TEST (KruskalTest, TwoNodesOneArc)
	TEST (KruskalTest, LinearChain)
	TEST (KruskalTest, CompleteGraphK4)
	TEST (KruskalTest, StarGraph)
	TEST (KruskalTest, GridGraph3x3)
	TEST (KruskalTest, DiamondGraph)
	TEST (KruskalTest, AllEqualWeights)
	TEST (KruskalTest, UniqueWeights)
	TEST (KruskalTest, ZeroWeightEdges)
	TEST (KruskalTest, LargeWeights)
	TEST (KruskalTest, ParallelEdges)
	TEST (KruskalTest, SelfLoop)
	TEST (KruskalTest, CycleGraph)
	TEST (KruskalTest, PaintMode)
	TEST (KruskalTest, TreeBuildingMode)
	TEST (KruskalTest, TreeHasCorrectArcCount)
	TEST (KruskalTest, AllNodesInTree)
	TEST (KruskalTest, TreeIsConnected)
	TEST (KruskalTest, BitFlagsCorrectlySet)
	TEST (KruskalTest, NodeMappingCorrect)
	TEST (KruskalTest, ArcMappingCorrect)
	TEST (KruskalTest, DigraphRejection)
	TEST (KruskalTest, EmptyGraph)
	TEST (KruskalTest, CustomDistanceFunctor)
	TEST (KruskalTest, ArrayGraphType)
	TEST (KruskalTest, MultipleCallsSameInstance)
	TEST (KruskalTest, LargeConnectedGraph)
	TEST (KruskalTest, PaintThenBuildTree)
	TEST (KruskalTest, DisconnectedGraphCreatesForest)
	TEST (KruskalTest, VerifyMinimumWeightProperty)
	TEST (KruskalTest, RepeatedEdgesSameNodes)
	TEST (KruskalTest, IsPaintedGetter)
int	main (int argc, char **argv)

Detailed Description

GoogleTest suite for Kruskal.H.

This file contains exhaustive tests to verify the correctness of Kruskal's minimum spanning tree algorithm implementation in Aleph-w.

Tests for Test Kruskal

Definition in file test_kruskal.cc.

Typedef Documentation

AArc

using AArc = AGT::Arc

Definition at line 35 of file test_kruskal.cc.

AGT

using AGT = Array_Graph<Graph_Anode<int>, Graph_Aarc<int> >

Definition at line 33 of file test_kruskal.cc.

ANode

using ANode = AGT::Node

Definition at line 34 of file test_kruskal.cc.

Arc

using Arc = GT::Arc

Definition at line 30 of file test_kruskal.cc.

GT

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

Definition at line 28 of file test_kruskal.cc.

Node

using Node = GT::Node

Definition at line 29 of file test_kruskal.cc.

Function Documentation

main()

int main	(	int	argc,
		char **	argv
	)

Definition at line 959 of file test_kruskal.cc.

References Aleph::maps().

TEST() [1/34]

TEST	(	KruskalTest	,
		AllEqualWeights
	)

Definition at line 344 of file test_kruskal.cc.

References GraphCommon< GT, Node, Arc >::get_num_arcs(), GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), and Aleph::maps().

TEST() [2/34]

TEST	(	KruskalTest	,
		AllNodesInTree
	)

Definition at line 574 of file test_kruskal.cc.

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

TEST() [3/34]

TEST	(	KruskalTest	,
		ArcMappingCorrect
	)

Definition at line 673 of file test_kruskal.cc.

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

TEST() [4/34]

TEST	(	KruskalTest	,
		ArrayGraphType
	)

Definition at line 747 of file test_kruskal.cc.

References GraphCommon< GT, Node, Arc >::get_num_arcs(), GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::Array_Graph< __Graph_Node, __Graph_Arc >::insert_arc(), Aleph::Array_Graph< __Graph_Node, __Graph_Arc >::insert_node(), and Aleph::maps().

TEST() [5/34]

TEST	(	KruskalTest	,
		BitFlagsCorrectlySet
	)

Definition at line 628 of file test_kruskal.cc.

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

TEST() [6/34]

TEST	(	KruskalTest	,
		CompleteGraphK4
	)

Definition at line 234 of file test_kruskal.cc.

References GraphCommon< GT, Node, Arc >::get_num_arcs(), GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), and Aleph::maps().

TEST() [7/34]

TEST	(	KruskalTest	,
		CustomDistanceFunctor
	)

Definition at line 724 of file test_kruskal.cc.

References GraphCommon< GT, Node, Arc >::get_num_arcs(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), and Aleph::maps().

TEST() [8/34]

TEST	(	KruskalTest	,
		CycleGraph
	)

Definition at line 480 of file test_kruskal.cc.

References GraphCommon< GT, Node, Arc >::get_num_arcs(), GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), Aleph::maps(), nodes, and num_nodes.

TEST() [9/34]

TEST	(	KruskalTest	,
		DiamondGraph
	)

Definition at line 319 of file test_kruskal.cc.

References GraphCommon< GT, Node, Arc >::get_num_arcs(), GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), and Aleph::maps().

TEST() [10/34]

TEST	(	KruskalTest	,
		DigraphRejection
	)

Definition at line 697 of file test_kruskal.cc.

References Aleph::maps().

TEST() [11/34]

TEST	(	KruskalTest	,
		DisconnectedGraphCreatesForest
	)

Definition at line 857 of file test_kruskal.cc.

References GraphCommon< GT, Node, Arc >::get_num_arcs(), GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), and Aleph::maps().

TEST() [12/34]

TEST	(	KruskalTest	,
		EmptyGraph
	)

Definition at line 711 of file test_kruskal.cc.

References GraphCommon< GT, Node, Arc >::get_num_arcs(), GraphCommon< GT, Node, Arc >::get_num_nodes(), and Aleph::maps().

TEST() [13/34]

TEST	(	KruskalTest	,
		GridGraph3x3
	)

Definition at line 287 of file test_kruskal.cc.

References GraphCommon< GT, Node, Arc >::get_num_arcs(), GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), and Aleph::maps().

TEST() [14/34]

TEST	(	KruskalTest	,
		IsPaintedGetter
	)

Definition at line 933 of file test_kruskal.cc.

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

TEST() [15/34]

TEST	(	KruskalTest	,
		LargeConnectedGraph
	)

Definition at line 794 of file test_kruskal.cc.

References GraphCommon< GT, Node, Arc >::get_num_arcs(), GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), Aleph::maps(), nodes, num_nodes, and rng.

TEST() [16/34]

TEST	(	KruskalTest	,
		LargeWeights
	)

Definition at line 417 of file test_kruskal.cc.

References GraphCommon< GT, Node, Arc >::get_num_arcs(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), and Aleph::maps().

TEST() [17/34]

TEST	(	KruskalTest	,
		LinearChain
	)

Definition at line 209 of file test_kruskal.cc.

References GraphCommon< GT, Node, Arc >::get_num_arcs(), GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), Aleph::maps(), nodes, and num_nodes.

TEST() [18/34]

TEST	(	KruskalTest	,
		MultipleCallsSameInstance
	)

Definition at line 768 of file test_kruskal.cc.

References Aleph::maps().

TEST() [19/34]

TEST	(	KruskalTest	,
		NodeMappingCorrect
	)

Definition at line 648 of file test_kruskal.cc.

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

TEST() [20/34]

TEST	(	KruskalTest	,
		PaintMode
	)

Definition at line 505 of file test_kruskal.cc.

References GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), and Aleph::maps().

TEST() [21/34]

TEST	(	KruskalTest	,
		PaintThenBuildTree
	)

Definition at line 830 of file test_kruskal.cc.

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

TEST() [22/34]

TEST	(	KruskalTest	,
		ParallelEdges
	)

Definition at line 438 of file test_kruskal.cc.

References GraphCommon< GT, Node, Arc >::get_num_arcs(), GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), and Aleph::maps().

TEST() [23/34]

TEST	(	KruskalTest	,
		RepeatedEdgesSameNodes
	)

Definition at line 911 of file test_kruskal.cc.

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

TEST() [24/34]

TEST	(	KruskalTest	,
		SelfLoop
	)

Definition at line 460 of file test_kruskal.cc.

References GraphCommon< GT, Node, Arc >::get_num_arcs(), GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), and Aleph::maps().

TEST() [25/34]

TEST	(	KruskalTest	,
		SimpleConnectedGraph
	)

Definition at line 149 of file test_kruskal.cc.

References GraphCommon< GT, Node, Arc >::get_num_arcs(), GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), and Aleph::maps().

TEST() [26/34]

TEST	(	KruskalTest	,
		SingleNodeGraph
	)

Definition at line 178 of file test_kruskal.cc.

References GraphCommon< GT, Node, Arc >::get_num_arcs(), GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), and Aleph::maps().

TEST() [27/34]

TEST	(	KruskalTest	,
		StarGraph
	)

Definition at line 261 of file test_kruskal.cc.

References GraphCommon< GT, Node, Arc >::get_num_arcs(), GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), and Aleph::maps().

TEST() [28/34]

TEST	(	KruskalTest	,
		TreeBuildingMode
	)

Definition at line 529 of file test_kruskal.cc.

References GraphCommon< GT, Node, Arc >::get_num_arcs(), GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), and Aleph::maps().

TEST() [29/34]

TEST	(	KruskalTest	,
		TreeHasCorrectArcCount
	)

Definition at line 550 of file test_kruskal.cc.

References GraphCommon< GT, Node, Arc >::get_num_arcs(), GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), Aleph::maps(), nodes, and num_nodes.

TEST() [30/34]

TEST	(	KruskalTest	,
		TreeIsConnected
	)

Definition at line 602 of file test_kruskal.cc.

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

TEST() [31/34]

TEST	(	KruskalTest	,
		TwoNodesOneArc
	)

Definition at line 192 of file test_kruskal.cc.

References GraphCommon< GT, Node, Arc >::get_num_arcs(), GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), and Aleph::maps().

TEST() [32/34]

TEST	(	KruskalTest	,
		UniqueWeights
	)

Definition at line 372 of file test_kruskal.cc.

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

TEST() [33/34]

TEST	(	KruskalTest	,
		VerifyMinimumWeightProperty
	)

Definition at line 880 of file test_kruskal.cc.

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

TEST() [34/34]

TEST	(	KruskalTest	,
		ZeroWeightEdges
	)

Definition at line 397 of file test_kruskal.cc.

References GraphCommon< GT, Node, Arc >::get_num_arcs(), GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), and Aleph::maps().