Tests for tpl_graph_utils.H. More...

#include <gtest/gtest.h>
#include <functional>
#include <queue>
#include <random>
#include <set>
#include <tuple>
#include <vector>
#include <tpl_dynArray.H>
#include <tpl_graph.H>
#include <tpl_graph_utils.H>

Include dependency graph for tpl_graph_utils_test.cc:

Functions
	TEST (GraphUtilsTraversal, DepthFirstTraversalCountsReachableNodes)

	TEST (GraphUtilsTraversal, DepthFirstTraversalProvidesFromArc)

	TEST (GraphUtilsTraversal, DepthFirstTraversalStopsImmediately)

	TEST (GraphUtilsTraversal, BreadthFirstTraversalCountsReachableNodes)

	TEST (GraphUtilsTraversal, BreadthFirstTraversalProvidesFromArc)

	TEST (GraphUtilsTraversal, BreadthFirstTraversalStopsImmediately)

	TEST (GraphUtilsTraversal, DepthFirstTraversalFunctorHonorsArcFilter)

	TEST (GraphUtilsTraversal, BreadthFirstTraversalFunctorHonorsArcFilter)

	TEST (GraphUtilsPath, FindPathBreadthFirstStartEqualsEnd)

	TEST (GraphUtilsPath, FindPathBreadthFirstReturnsEmptyPathWhenUnreachable)

	TEST (GraphUtilsPath, FindPathBreadthFirstFindsShortestByEdges)

	TEST (GraphUtilsPath, FindPathBreadthFirstRandomGraphsMatchesReferenceBfs)

	TEST (GraphUtilsProperties, TestConnectivityBasics)

	TEST (GraphUtilsProperties, TestConnectivityRejectsDigraphs)

	TEST (GraphUtilsProperties, TestForCycleBehavior)

	TEST (GraphUtilsProperties, AcyclicAndHasCycleAgreement)

	TEST (GraphUtilsProperties, AcyclicRejectsDigraphs)

	TEST (GraphUtilsProperties, TestForPathBasicAndRegression)

	TEST (GraphUtilsComponents, InconnectedComponentsReturnsMappedSubgraphs)

	TEST (GraphUtilsComponents, BuildSubgraphCopiesReachableComponent)

	TEST (GraphUtilsSpanningTrees, DepthFirstSpanningTreeIsTreeAndMapped)

	TEST (GraphUtilsSpanningTrees, BreadthFirstSpanningTreeIsTreeAndMapped)

	TEST (GraphUtilsSpanningTrees, BuildSpanningTreeFromArcsUsesOneWayMapping)

	TEST (GraphUtilsCutNodes, ComputeCutNodesClearsCookiesAndFindsArticulations)

	TEST (GraphUtilsCutNodes, PaintAndExtractCutGraphOnChain)

	TEST (GraphUtilsCutNodes, PaintAndExtractBlocksOnStar)

	TEST (GraphUtilsDigraph, InvertDigraphPreservesIsolatedNodesAndMapsArcs)

	TEST (GraphUtilsDigraph, InvertDigraphRejectsUndirectedGraphs)

	TEST (GraphUtilsDigraph, InvertDigraphFunctorFiltersArcs)

	TEST (GraphUtilsCosts, DftDistConstants)

	TEST (GraphUtilsCosts, GetMinPathReconstructsCookieChainAndComputesCost)

	TEST (GraphUtilsCosts, TotalCostSumsArcsAndAccumulatorWorks)

Detailed Description

Tests for tpl_graph_utils.H.

These tests cover:

Depth/breadth traversals (free functions and functors)
Path search (BFS)
Connectivity, reachability, cycle checks
Connected components extraction and mapping
Spanning trees (DFS/BFS) and mapping
Cut nodes / painting / cut graph extraction
Digraph inversion (transpose) and mapping
get_min_path() reconstruction and Total_Cost aggregation

Definition in file tpl_graph_utils_test.cc.

Function Documentation

◆ TEST() [1/32]

TEST	(	GraphUtilsComponents	,
		BuildSubgraphCopiesReachableComponent
	)

Definition at line 545 of file tpl_graph_utils_test.cc.

References Aleph::build_subgraph(), 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(), nodes, GraphCommon< GT, Node, Arc >::reset_arcs(), and GraphCommon< GT, Node, Arc >::reset_nodes().

◆ TEST() [2/32]

TEST	(	GraphUtilsComponents	,
		InconnectedComponentsReturnsMappedSubgraphs
	)

Definition at line 508 of file tpl_graph_utils_test.cc.

References LocateFunctions< Container, Type >::get_it(), GraphCommon< GT, Node, Arc >::get_node_it(), Aleph::inconnected_components(), Aleph::DynList< T >::insert(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::maps(), and nodes.

◆ TEST() [3/32]

TEST	(	GraphUtilsCosts	,
		DftDistConstants
	)

Definition at line 813 of file tpl_graph_utils_test.cc.

References Aleph::maps().

◆ TEST() [4/32]

TEST	(	GraphUtilsCosts	,
		GetMinPathReconstructsCookieChainAndComputesCost
	)

Definition at line 819 of file tpl_graph_utils_test.cc.

References Aleph::maps(), NODE_COOKIE, nodes, Aleph::HTList::size(), and Aleph::Path< GT >::size().

◆ TEST() [5/32]

TEST	(	GraphUtilsCosts	,
		TotalCostSumsArcsAndAccumulatorWorks
	)

Definition at line 852 of file tpl_graph_utils_test.cc.

References Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::maps(), nodes, Aleph::Total_Cost< GT, Distance, SA >::reset(), Aleph::Total_Cost< GT, Distance, SA >::total_cost(), Aleph::traverse_arcs(), and Aleph::Total_Cost< GT, Distance, SA >::value().

◆ TEST() [6/32]

TEST	(	GraphUtilsCutNodes	,
		ComputeCutNodesClearsCookiesAndFindsArticulations
	)

Definition at line 659 of file tpl_graph_utils_test.cc.

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

◆ TEST() [7/32]

TEST	(	GraphUtilsCutNodes	,
		PaintAndExtractBlocksOnStar
	)

Definition at line 711 of file tpl_graph_utils_test.cc.

References Aleph::compute_cut_nodes(), LocateFunctions< Container, Type >::get_it(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::map_cut_graph(), Aleph::map_subgraph(), Aleph::maps(), nodes, and Aleph::paint_subgraphs().

◆ TEST() [8/32]

TEST	(	GraphUtilsCutNodes	,
		PaintAndExtractCutGraphOnChain
	)

Definition at line 685 of file tpl_graph_utils_test.cc.

References Aleph::compute_cut_nodes(), LocateFunctions< Container, Type >::get_it(), Aleph::DynList< T >::insert(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::map_cut_graph(), Aleph::maps(), nodes, and Aleph::paint_subgraphs().

◆ TEST() [9/32]

TEST	(	GraphUtilsDigraph	,
		InvertDigraphFunctorFiltersArcs
	)

Definition at line 780 of file tpl_graph_utils_test.cc.

References ARC_COOKIE, Aleph::maps(), nodes, and Aleph::search_directed_arc().

◆ TEST() [10/32]

TEST	(	GraphUtilsDigraph	,
		InvertDigraphPreservesIsolatedNodesAndMapsArcs
	)

Definition at line 747 of file tpl_graph_utils_test.cc.

References Aleph::invert_digraph(), Aleph::maps(), nodes, and Aleph::search_directed_arc().

◆ TEST() [11/32]

TEST	(	GraphUtilsDigraph	,
		InvertDigraphRejectsUndirectedGraphs
	)

Definition at line 773 of file tpl_graph_utils_test.cc.

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

◆ TEST() [12/32]

TEST	(	GraphUtilsPath	,
		FindPathBreadthFirstFindsShortestByEdges
	)

Definition at line 341 of file tpl_graph_utils_test.cc.

References Aleph::find_path_breadth_first(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::Path< GT >::is_empty(), Aleph::maps(), nodes, Aleph::search_arc(), Aleph::HTList::size(), and Aleph::Path< GT >::size().

◆ TEST() [13/32]

TEST	(	GraphUtilsPath	,
		FindPathBreadthFirstRandomGraphsMatchesReferenceBfs
	)

Definition at line 361 of file tpl_graph_utils_test.cc.

References Aleph::find_path_breadth_first(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::Path< GT >::is_empty(), Aleph::maps(), nodes, rng, Aleph::search_arc(), Aleph::HTList::size(), and Aleph::Path< GT >::size().

◆ TEST() [14/32]

TEST	(	GraphUtilsPath	,
		FindPathBreadthFirstReturnsEmptyPathWhenUnreachable
	)

Definition at line 329 of file tpl_graph_utils_test.cc.

References Aleph::find_path_breadth_first(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::Path< GT >::inside_graph(), Aleph::Path< GT >::is_empty(), Aleph::maps(), and nodes.

◆ TEST() [15/32]

TEST	(	GraphUtilsPath	,
		FindPathBreadthFirstStartEqualsEnd
	)

Definition at line 315 of file tpl_graph_utils_test.cc.

References Aleph::find_path_breadth_first(), Aleph::Path< GT >::get_first_node(), Aleph::Path< GT >::get_last_node(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::Path< GT >::is_empty(), Aleph::maps(), nodes, and Aleph::Path< GT >::size().

◆ TEST() [16/32]

TEST	(	GraphUtilsProperties	,
		AcyclicAndHasCycleAgreement
	)

Definition at line 454 of file tpl_graph_utils_test.cc.

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

◆ TEST() [17/32]

TEST	(	GraphUtilsProperties	,
		AcyclicRejectsDigraphs
	)

Definition at line 473 of file tpl_graph_utils_test.cc.

References Aleph::is_graph_acyclique(), Aleph::maps(), and nodes.

◆ TEST() [18/32]

TEST	(	GraphUtilsProperties	,
		TestConnectivityBasics
	)

Definition at line 413 of file tpl_graph_utils_test.cc.

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

◆ TEST() [19/32]

TEST	(	GraphUtilsProperties	,
		TestConnectivityRejectsDigraphs
	)

Definition at line 432 of file tpl_graph_utils_test.cc.

References Aleph::maps(), nodes, and Aleph::test_connectivity().

◆ TEST() [20/32]

TEST	(	GraphUtilsProperties	,
		TestForCycleBehavior
	)

Definition at line 440 of file tpl_graph_utils_test.cc.

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

◆ TEST() [21/32]

TEST	(	GraphUtilsProperties	,
		TestForPathBasicAndRegression
	)

Definition at line 483 of file tpl_graph_utils_test.cc.

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

◆ TEST() [22/32]

TEST	(	GraphUtilsSpanningTrees	,
		BreadthFirstSpanningTreeIsTreeAndMapped
	)

Definition at line 589 of file tpl_graph_utils_test.cc.

References Aleph::find_breadth_first_spanning_tree(), GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::is_graph_acyclique(), Aleph::maps(), nodes, GraphCommon< GT, Node, Arc >::reset_arcs(), and GraphCommon< GT, Node, Arc >::reset_nodes().

◆ TEST() [23/32]

TEST	(	GraphUtilsSpanningTrees	,
		BuildSpanningTreeFromArcsUsesOneWayMapping
	)

Definition at line 611 of file tpl_graph_utils_test.cc.

References Aleph::DynArray< T >::append(), ARC_COOKIE, arcs, GraphCommon< GT, Node, Arc >::get_node_it(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::maps(), NODE_COOKIE, nodes, GraphCommon< GT, Node, Arc >::reset_arcs(), and GraphCommon< GT, Node, Arc >::reset_nodes().

◆ TEST() [24/32]

TEST	(	GraphUtilsSpanningTrees	,
		DepthFirstSpanningTreeIsTreeAndMapped
	)

Definition at line 569 of file tpl_graph_utils_test.cc.

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

◆ TEST() [25/32]

TEST	(	GraphUtilsTraversal	,
		BreadthFirstTraversalCountsReachableNodes
	)

Definition at line 227 of file tpl_graph_utils_test.cc.

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

◆ TEST() [26/32]

TEST	(	GraphUtilsTraversal	,
		BreadthFirstTraversalFunctorHonorsArcFilter
	)

Definition at line 291 of file tpl_graph_utils_test.cc.

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

◆ TEST() [27/32]

TEST	(	GraphUtilsTraversal	,
		BreadthFirstTraversalProvidesFromArc
	)

Definition at line 245 of file tpl_graph_utils_test.cc.

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

◆ TEST() [28/32]

TEST	(	GraphUtilsTraversal	,
		BreadthFirstTraversalStopsImmediately
	)

Definition at line 256 of file tpl_graph_utils_test.cc.

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

◆ TEST() [29/32]

TEST	(	GraphUtilsTraversal	,
		DepthFirstTraversalCountsReachableNodes
	)

Definition at line 187 of file tpl_graph_utils_test.cc.

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

◆ TEST() [30/32]

TEST	(	GraphUtilsTraversal	,
		DepthFirstTraversalFunctorHonorsArcFilter
	)

Definition at line 271 of file tpl_graph_utils_test.cc.

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

◆ TEST() [31/32]

TEST	(	GraphUtilsTraversal	,
		DepthFirstTraversalProvidesFromArc
	)

Definition at line 205 of file tpl_graph_utils_test.cc.

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

◆ TEST() [32/32]

TEST	(	GraphUtilsTraversal	,
		DepthFirstTraversalStopsImmediately
	)

Definition at line 216 of file tpl_graph_utils_test.cc.

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