cut_nodes_test.cc File Reference

Tests for Cut Nodes. More...

#include <gtest/gtest.h>
#include <set>
#include <vector>
#include <tpl_cut_nodes.H>
#include <tpl_graph.H>
#include <tpl_graph_utils.H>

Include dependency graph for cut_nodes_test.cc:

Go to the source code of this file.

Functions
	TEST (CutNodes, PathGraphHasInternalCutNodes)
	TEST (CutNodes, CycleGraphHasNoCutNodes)
	TEST (CutNodes, StarGraphHasCenterAsCutNode)
	TEST (CutNodes, PaintSubgraphsRequiresCutNodesComputed)
	TEST (CutNodes, PaintSubgraphsAndMapCutGraphOnStar)
	TEST (CutNodes, MapSubgraphMatchesColorCounts)
	TEST (CutNodes, MapCutGraphMatchesCutArcCountOnPath)
	TEST (CutNodes, CompleteGraphHasNoCutNodes)
	TEST (CutNodes, TreeAllInternalNodesAreCutNodes)
	TEST (CutNodes, BridgeGraphHasMultipleCutNodes)
	TEST (CutNodes, BiconnectedGraphHasNoCutNodes)
	TEST (CutNodes, ArticulationAtRootNode)
	TEST (CutNodes, MapSubgraphWithoutPaintingThrows)
	TEST (CutNodes, MapCutGraphWithoutPaintingThrows)
	TEST (CutNodes, CorrectSequenceCutNodesPaintMap)
	TEST (CutNodes, MultipleCutNodesCallsReinitialize)
	TEST (CutNodes, OperatorWithoutStartUsesFirstNode)
	TEST (CutNodes, OperatorWithSpecificStart)
	TEST (CutNodes, PaintAssignsCorrectColors)
	TEST (CutNodes, CrossArcsIdentifiedCorrectly)
	TEST (CutNodes, CutArcsIdentifiedInBridge)
	TEST (CutNodes, NumberOfColorsMatchesComponents)
	TEST (CutNodes, MapSubgraphWithInvalidColorThrows)
	TEST (CutNodes, MappedSubgraphIsCorrect)
	TEST (CutNodes, BidirectionalMappingEstablished)
	TEST (CutNodes, CutGraphContainsOnlyCutNodes)
	TEST (CutNodes, CrossArcsListMatchesGraph)
	TEST (CutNodes, ComputeBlocksWithoutCutNodesThrows)
	TEST (CutNodes, ComputeBlocksAutoPaints)
	TEST (CutNodes, ComputeBlocksGeneratesAllBlocks)
	TEST (CutNodes, ComputeBlocksGeneratesCutGraph)
	TEST (CutNodes, ComputeBlocksGeneratesCrossArcList)
	TEST (CutNodes, SingleNodeHasNoCutNodes)
	TEST (CutNodes, TwoNodesWithArcNoCutNodes)
	TEST (CutNodes, TriangleNoCutNodes)
	TEST (CutNodes, SelfLoopDoesNotAffectCutNodes)
	TEST (CutNodes, ParallelArcsDoNotAffectCutNodes)
	TEST (CutNodes, CompleteWorkflowDetectPaintMapAll)
	TEST (CutNodes, MultipleIterationsOnSameGraph)
	TEST (CutNodes, LargeGraphStressTest)
	TEST (CutNodes, ExceptionDuringMapSubgraphClearsGraph)

Detailed Description

Tests for Cut Nodes.

Definition in file cut_nodes_test.cc.

Function Documentation

TEST() [1/41]

TEST	(	CutNodes	,
		ArticulationAtRootNode
	)

Definition at line 320 of file cut_nodes_test.cc.

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

TEST() [2/41]

TEST	(	CutNodes	,
		BiconnectedGraphHasNoCutNodes
	)

Definition at line 303 of file cut_nodes_test.cc.

References Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::HTList::is_empty(), Aleph::maps(), and nodes.

TEST() [3/41]

TEST	(	CutNodes	,
		BidirectionalMappingEstablished
	)

Definition at line 588 of file cut_nodes_test.cc.

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

TEST() [4/41]

TEST	(	CutNodes	,
		BridgeGraphHasMultipleCutNodes
	)

Definition at line 283 of file cut_nodes_test.cc.

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

TEST() [5/41]

TEST	(	CutNodes	,
		CompleteGraphHasNoCutNodes
	)

Definition at line 242 of file cut_nodes_test.cc.

References Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::HTList::is_empty(), Aleph::maps(), and nodes.

TEST() [6/41]

TEST	(	CutNodes	,
		CompleteWorkflowDetectPaintMapAll
	)

Definition at line 842 of file cut_nodes_test.cc.

References Aleph::color(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::HTList::is_empty(), Aleph::maps(), and nodes.

TEST() [7/41]

TEST	(	CutNodes	,
		ComputeBlocksAutoPaints
	)

Definition at line 681 of file cut_nodes_test.cc.

References Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::maps(), nodes, and Aleph::DynDlist< T >::size().

TEST() [8/41]

TEST	(	CutNodes	,
		ComputeBlocksGeneratesAllBlocks
	)

Definition at line 701 of file cut_nodes_test.cc.

References Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::maps(), nodes, and Aleph::DynDlist< T >::size().

TEST() [9/41]

TEST	(	CutNodes	,
		ComputeBlocksGeneratesCrossArcList
	)

Definition at line 745 of file cut_nodes_test.cc.

References Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::HTList::is_empty(), Aleph::maps(), and nodes.

TEST() [10/41]

TEST	(	CutNodes	,
		ComputeBlocksGeneratesCutGraph
	)

Definition at line 724 of file cut_nodes_test.cc.

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

TEST() [11/41]

TEST	(	CutNodes	,
		ComputeBlocksWithoutCutNodesThrows
	)

Definition at line 666 of file cut_nodes_test.cc.

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

TEST() [12/41]

TEST	(	CutNodes	,
		CorrectSequenceCutNodesPaintMap
	)

Definition at line 372 of file cut_nodes_test.cc.

References Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::HTList::is_empty(), Aleph::maps(), and nodes.

TEST() [13/41]

TEST	(	CutNodes	,
		CrossArcsIdentifiedCorrectly
	)

Definition at line 482 of file cut_nodes_test.cc.

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

TEST() [14/41]

TEST	(	CutNodes	,
		CrossArcsListMatchesGraph
	)

Definition at line 637 of file cut_nodes_test.cc.

References GraphCommon< GT, Node, Arc >::get_arc_it(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::maps(), nodes, and Aleph::HTList::size().

TEST() [15/41]

TEST	(	CutNodes	,
		CutArcsIdentifiedInBridge
	)

Definition at line 503 of file cut_nodes_test.cc.

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

TEST() [16/41]

TEST	(	CutNodes	,
		CutGraphContainsOnlyCutNodes
	)

Definition at line 616 of file cut_nodes_test.cc.

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

TEST() [17/41]

TEST	(	CutNodes	,
		CycleGraphHasNoCutNodes
	)

Definition at line 120 of file cut_nodes_test.cc.

References Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::HTList::is_empty(), Aleph::maps(), and nodes.

TEST() [18/41]

TEST	(	CutNodes	,
		ExceptionDuringMapSubgraphClearsGraph
	)

Definition at line 908 of file cut_nodes_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::maps(), and nodes.

TEST() [19/41]

TEST	(	CutNodes	,
		LargeGraphStressTest
	)

Definition at line 891 of file cut_nodes_test.cc.

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

TEST() [20/41]

TEST	(	CutNodes	,
		MapCutGraphMatchesCutArcCountOnPath
	)

Definition at line 217 of file cut_nodes_test.cc.

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

TEST() [21/41]

TEST	(	CutNodes	,
		MapCutGraphWithoutPaintingThrows
	)

Definition at line 357 of file cut_nodes_test.cc.

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

TEST() [22/41]

TEST	(	CutNodes	,
		MappedSubgraphIsCorrect
	)

Definition at line 565 of file cut_nodes_test.cc.

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

TEST() [23/41]

TEST	(	CutNodes	,
		MapSubgraphMatchesColorCounts
	)

Definition at line 194 of file cut_nodes_test.cc.

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

TEST() [24/41]

TEST	(	CutNodes	,
		MapSubgraphWithInvalidColorThrows
	)

Definition at line 550 of file cut_nodes_test.cc.

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

TEST() [25/41]

TEST	(	CutNodes	,
		MapSubgraphWithoutPaintingThrows
	)

Definition at line 343 of file cut_nodes_test.cc.

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

TEST() [26/41]

TEST	(	CutNodes	,
		MultipleCutNodesCallsReinitialize
	)

Definition at line 395 of file cut_nodes_test.cc.

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

TEST() [27/41]

TEST	(	CutNodes	,
		MultipleIterationsOnSameGraph
	)

Definition at line 873 of file cut_nodes_test.cc.

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

TEST() [28/41]

TEST	(	CutNodes	,
		NumberOfColorsMatchesComponents
	)

Definition at line 524 of file cut_nodes_test.cc.

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

TEST() [29/41]

TEST	(	CutNodes	,
		OperatorWithoutStartUsesFirstNode
	)

Definition at line 419 of file cut_nodes_test.cc.

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

TEST() [30/41]

TEST	(	CutNodes	,
		OperatorWithSpecificStart
	)

Definition at line 434 of file cut_nodes_test.cc.

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

TEST() [31/41]

TEST	(	CutNodes	,
		PaintAssignsCorrectColors
	)

Definition at line 453 of file cut_nodes_test.cc.

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

TEST() [32/41]

TEST	(	CutNodes	,
		PaintSubgraphsAndMapCutGraphOnStar
	)

Definition at line 163 of file cut_nodes_test.cc.

References GraphCommon< GT, Node, Arc >::get_num_arcs(), Aleph::Dlink::Iterator::has_curr(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::maps(), nodes, and Aleph::HTList::size().

TEST() [33/41]

TEST	(	CutNodes	,
		PaintSubgraphsRequiresCutNodesComputed
	)

Definition at line 151 of file cut_nodes_test.cc.

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

TEST() [34/41]

TEST	(	CutNodes	,
		ParallelArcsDoNotAffectCutNodes
	)

Definition at line 823 of file cut_nodes_test.cc.

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

TEST() [35/41]

TEST	(	CutNodes	,
		PathGraphHasInternalCutNodes
	)

Definition at line 105 of file cut_nodes_test.cc.

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

TEST() [36/41]

TEST	(	CutNodes	,
		SelfLoopDoesNotAffectCutNodes
	)

Definition at line 808 of file cut_nodes_test.cc.

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

TEST() [37/41]

TEST	(	CutNodes	,
		SingleNodeHasNoCutNodes
	)

Definition at line 768 of file cut_nodes_test.cc.

References Aleph::HTList::is_empty(), Aleph::maps(), and nodes.

TEST() [38/41]

TEST	(	CutNodes	,
		StarGraphHasCenterAsCutNode
	)

Definition at line 136 of file cut_nodes_test.cc.

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

TEST() [39/41]

TEST	(	CutNodes	,
		TreeAllInternalNodesAreCutNodes
	)

Definition at line 258 of file cut_nodes_test.cc.

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

TEST() [40/41]

TEST	(	CutNodes	,
		TriangleNoCutNodes
	)

Definition at line 793 of file cut_nodes_test.cc.

References Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::HTList::is_empty(), Aleph::maps(), and nodes.

TEST() [41/41]

TEST	(	CutNodes	,
		TwoNodesWithArcNoCutNodes
	)

Definition at line 780 of file cut_nodes_test.cc.

References Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::HTList::is_empty(), Aleph::maps(), and nodes.