prim_test.cc File Reference

GoogleTest suite for Prim.H. More...

#include <gtest/gtest.h>
#include <limits>
#include <random>
#include <set>
#include <vector>
#include <Prim.H>
#include <Kruskal.H>
#include <tpl_graph.H>
#include <tpl_graph_utils.H>

Include dependency graph for prim_test.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

Functions
	TEST (PrimBasic, EmptyGraph)
	TEST (PrimBasic, SingleNode)
	TEST (PrimBasic, TwoNodesOneArc)
	TEST (PrimBasic, TriangleGraph)
	TEST (PrimBasic, SquareGraph)
	TEST (PrimVsKruskal, SameWeightOnSimpleGraph)
	TEST (PrimVsKruskal, RandomGraph)
	TEST (PrimEdgeCases, AllEqualWeights)
	TEST (PrimEdgeCases, LinearGraph)
	TEST (PrimEdgeCases, StarGraph)
	TEST (PrimStress, LargeGraph)
	TEST (PrimStress, DenseGraph)
	TEST (PrimMapping, NodesAreMapped)
	TEST (PrimTextbook, ClassicExample)

Detailed Description

GoogleTest suite for Prim.H.

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

Tests for Prim

Definition in file prim_test.cc.

Typedef Documentation

Arc

using Arc = GT::Arc

Definition at line 30 of file prim_test.cc.

GT

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

Definition at line 28 of file prim_test.cc.

Node

using Node = GT::Node

Definition at line 29 of file prim_test.cc.

Function Documentation

TEST() [1/14]

TEST	(	PrimBasic	,
		EmptyGraph
	)

Definition at line 90 of file prim_test.cc.

References Aleph::maps().

TEST() [2/14]

TEST	(	PrimBasic	,
		SingleNode
	)

Definition at line 101 of file prim_test.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() [3/14]

TEST	(	PrimBasic	,
		SquareGraph
	)

Definition at line 152 of file prim_test.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() [4/14]

TEST	(	PrimBasic	,
		TriangleGraph
	)

Definition at line 130 of file prim_test.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() [5/14]

TEST	(	PrimBasic	,
		TwoNodesOneArc
	)

Definition at line 114 of file prim_test.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() [6/14]

TEST	(	PrimEdgeCases	,
		AllEqualWeights
	)

Definition at line 251 of file prim_test.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/14]

TEST	(	PrimEdgeCases	,
		LinearGraph
	)

Definition at line 277 of file prim_test.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() [8/14]

TEST	(	PrimEdgeCases	,
		StarGraph
	)

Definition at line 302 of file prim_test.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() [9/14]

TEST	(	PrimMapping	,
		NodesAreMapped
	)

Definition at line 406 of file prim_test.cc.

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

TEST() [10/14]

TEST	(	PrimStress	,
		DenseGraph
	)

Definition at line 369 of file prim_test.cc.

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

TEST() [11/14]

TEST	(	PrimStress	,
		LargeGraph
	)

Definition at line 328 of file prim_test.cc.

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

TEST() [12/14]

TEST	(	PrimTextbook	,
		ClassicExample
	)

Definition at line 434 of file prim_test.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() [13/14]

TEST	(	PrimVsKruskal	,
		RandomGraph
	)

Definition at line 211 of file prim_test.cc.

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

TEST() [14/14]

TEST	(	PrimVsKruskal	,
		SameWeightOnSimpleGraph
	)

Definition at line 181 of file prim_test.cc.

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