#include <gtest/gtest.h>
#include <stdexcept>
#include <string>
#include <algorithm>
#include <random>
#include <vector>
#include <Graph_Coloring.H>
#include <tpl_sgraph.H>
#include <tpl_agraph.H>

Include dependency graph for graph_coloring_test.cc:

Typedefs
using	Graph = List_Graph< Graph_Node< std::string >, Graph_Arc< Empty_Class > >

using	DGraph = List_Digraph< Graph_Node< std::string >, Graph_Arc< Empty_Class > >

using	SGraph = List_SGraph< Graph_Snode< int >, Graph_Sarc< Empty_Class > >

using	AGraph = Array_Graph< Graph_Anode< std::string >, Graph_Aarc< Empty_Class > >

Functions
static Graph	build_complete_graph (size_t n)

static Graph	build_cycle (size_t n)

static Graph	build_path (size_t n)

static Graph	build_star (size_t n)

static Graph	build_petersen ()

static Graph	build_wheel (size_t n)

static Graph	build_complete_bipartite (size_t m, size_t n)

static size_t	count_distinct_colors (const DynMapTree< Graph::Node *, size_t > &colors)

	TEST (GraphColoring, EmptyGraph)

	TEST (GraphColoring, SingleNode)

	TEST (GraphColoring, IsolatedNodes)

	TEST (GraphColoring, CompleteK2)

	TEST (GraphColoring, CompleteK3)

	TEST (GraphColoring, CompleteK4)

	TEST (GraphColoring, CompleteK5)

	TEST (GraphColoring, CompleteBipartiteK33)

	TEST (GraphColoring, Path5)

	TEST (GraphColoring, Star6)

	TEST (GraphColoring, TreeChain)

	TEST (GraphColoring, EvenCycle)

	TEST (GraphColoring, OddCycle)

	TEST (GraphColoring, Triangle)

	TEST (GraphColoring, PetersenGraph)

	TEST (GraphColoring, DisconnectedComponents)

	TEST (GraphColoring, DisconnectedMixed)

	TEST (GraphColoring, WheelW5EvenRing)

	TEST (GraphColoring, WheelW6OddRing)

	TEST (GraphColoring, AllAlgorithmsProduceValidColorings)

	TEST (GraphColoring, GreedyBoundDeltaPlusOne)

	TEST (GraphColoring, ValidationRejectsInvalidColoring)

	TEST (GraphColoring, ValidationRejectsMissingNode)

	TEST (GraphColoring, ValidationRejectsForeignKeyedMap)

	TEST (GraphColoring, ValidationRejectsIsolatedNodeMissingFromColors)

	TEST (GraphColoring, ValidationRejectsSelfLoop)

	TEST (GraphColoring, ValidationRejectsParallelEdge)

	TEST (GraphColoring, ChromaticNumberEmptyGraph)

	TEST (GraphColoring, ChromaticNumberIsolatedNodes)

	TEST (GraphColoring, ChromaticNumberK4)

	TEST (GraphColoring, ChromaticNumberPetersen)

	TEST (GraphColoring, ChromaticNumberOddCycle)

	TEST (GraphColoring, ChromaticNumberEvenCycle)

	TEST (GraphColoring, ChromaticNumberBipartite)

	TEST (GraphColoring, ChromaticNumberTooManyNodes)

	TEST (GraphColoring, ChromaticNumber64Nodes)

	TEST (GraphColoring, SGraphBasicColoring)

	TEST (GraphColoring, SGraphGreedy)

	TEST (GraphColoring, DigraphSingleArcUsesTwoColors)

	TEST (GraphColoring, DigraphReverseOrderStillUsesTwoColors)

	TEST (GraphColoring, AGraphTriangle)

	TEST (GraphColoring, FunctorWrappers)

	TEST (GraphColoring, CookiesPreservedAfterColoring)

	TEST (GraphColoring, SouthAmericaMapColoring)

	TEST (GraphColoring, ExamScheduling)

	TEST (GraphColoring, ChromaticNumberWheelEvenRing)

	TEST (GraphColoring, ChromaticNumberWheelOddRing)

	TEST (GraphColoring, RandomGraphsPropertyBased)

Typedef Documentation

◆ AGraph

using AGraph = Array_Graph<Graph_Anode<std::string>, Graph_Aarc<Empty_Class> >

Definition at line 31 of file graph_coloring_test.cc.

◆ DGraph

using DGraph = List_Digraph<Graph_Node<std::string>, Graph_Arc<Empty_Class> >

Definition at line 29 of file graph_coloring_test.cc.

◆ Graph

using Graph = List_Graph<Graph_Node<std::string>, Graph_Arc<Empty_Class> >

Definition at line 28 of file graph_coloring_test.cc.

◆ SGraph

using SGraph = List_SGraph<Graph_Snode<int>, Graph_Sarc<Empty_Class> >

Definition at line 30 of file graph_coloring_test.cc.

Function Documentation

◆ build_complete_bipartite()

static Graph build_complete_bipartite	(	size_t	m,
		size_t	n
	)

static

Definition at line 181 of file graph_coloring_test.cc.

References Aleph::DynList< T >::append(), Aleph::divide_and_conquer_partition_dp(), LocateFunctions< Container, Type >::get_it(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), and m.

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

◆ build_complete_graph()

static Graph build_complete_graph ( size_t n )

static

Definition at line 36 of file graph_coloring_test.cc.

References Aleph::DynList< T >::append(), Aleph::divide_and_conquer_partition_dp(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), and nodes.

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

◆ build_cycle()

static Graph build_cycle ( size_t n )

static

Definition at line 59 of file graph_coloring_test.cc.

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

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

◆ build_path()

static Graph build_path ( size_t n )

static

Definition at line 86 of file graph_coloring_test.cc.

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

Referenced by TEST(), and TEST().

◆ build_petersen()

static Graph build_petersen ( )

static

Definition at line 119 of file graph_coloring_test.cc.

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

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

◆ build_star()

static Graph build_star ( size_t n )

static

Definition at line 103 of file graph_coloring_test.cc.

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

Referenced by TEST().

◆ build_wheel()

static Graph build_wheel ( size_t n )

static

Definition at line 148 of file graph_coloring_test.cc.

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

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

◆ count_distinct_colors()

static size_t count_distinct_colors ( const DynMapTree< Graph::Node *, size_t > & colors )

static

Definition at line 200 of file graph_coloring_test.cc.

References Aleph::divide_and_conquer_partition_dp(), FunctionalMethods< Container, T >::for_each(), Aleph::DynSetTree< Key, Tree, Compare >::insert(), and Aleph::DynSetTree< Key, Tree, Compare >::size().

Referenced by TEST().

◆ TEST() [1/48]

TEST	(	GraphColoring	,
		AGraphTriangle
	)

Definition at line 820 of file graph_coloring_test.cc.

References Aleph::chromatic_number(), Aleph::divide_and_conquer_partition_dp(), Aleph::dsatur_coloring(), Aleph::Array_Graph< __Graph_Node, __Graph_Arc >::insert_arc(), Aleph::Array_Graph< __Graph_Node, __Graph_Arc >::insert_node(), and Aleph::is_valid_coloring().

◆ TEST() [2/48]

TEST	(	GraphColoring	,
		AllAlgorithmsProduceValidColorings
	)

Definition at line 480 of file graph_coloring_test.cc.

References build_petersen(), Aleph::divide_and_conquer_partition_dp(), Aleph::dsatur_coloring(), Aleph::greedy_coloring(), Aleph::is_valid_coloring(), and Aleph::welsh_powell_coloring().

◆ TEST() [3/48]

TEST	(	GraphColoring	,
		ChromaticNumber64Nodes
	)

Definition at line 714 of file graph_coloring_test.cc.

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

◆ TEST() [4/48]

TEST	(	GraphColoring	,
		ChromaticNumberBipartite
	)

Definition at line 695 of file graph_coloring_test.cc.

References build_complete_bipartite(), Aleph::chromatic_number(), Aleph::divide_and_conquer_partition_dp(), and Aleph::is_valid_coloring().

◆ TEST() [5/48]

TEST	(	GraphColoring	,
		ChromaticNumberEmptyGraph
	)

Definition at line 639 of file graph_coloring_test.cc.

References Aleph::chromatic_number(), and Aleph::divide_and_conquer_partition_dp().

◆ TEST() [6/48]

TEST	(	GraphColoring	,
		ChromaticNumberEvenCycle
	)

Definition at line 686 of file graph_coloring_test.cc.

References build_cycle(), Aleph::chromatic_number(), Aleph::divide_and_conquer_partition_dp(), and Aleph::is_valid_coloring().

◆ TEST() [7/48]

TEST	(	GraphColoring	,
		ChromaticNumberIsolatedNodes
	)

Definition at line 647 of file graph_coloring_test.cc.

References Aleph::chromatic_number(), Aleph::divide_and_conquer_partition_dp(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), and Aleph::is_valid_coloring().

◆ TEST() [8/48]

TEST	(	GraphColoring	,
		ChromaticNumberK4
	)

Definition at line 658 of file graph_coloring_test.cc.

References build_complete_graph(), Aleph::chromatic_number(), count_distinct_colors(), Aleph::divide_and_conquer_partition_dp(), and Aleph::is_valid_coloring().

◆ TEST() [9/48]

TEST	(	GraphColoring	,
		ChromaticNumberOddCycle
	)

Definition at line 677 of file graph_coloring_test.cc.

References build_cycle(), Aleph::chromatic_number(), Aleph::divide_and_conquer_partition_dp(), and Aleph::is_valid_coloring().

◆ TEST() [10/48]

TEST	(	GraphColoring	,
		ChromaticNumberPetersen
	)

Definition at line 668 of file graph_coloring_test.cc.

References build_petersen(), Aleph::chromatic_number(), Aleph::divide_and_conquer_partition_dp(), and Aleph::is_valid_coloring().

◆ TEST() [11/48]

TEST	(	GraphColoring	,
		ChromaticNumberTooManyNodes
	)

Definition at line 704 of file graph_coloring_test.cc.

References Aleph::chromatic_number(), Aleph::divide_and_conquer_partition_dp(), and Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node().

◆ TEST() [12/48]

TEST	(	GraphColoring	,
		ChromaticNumberWheelEvenRing
	)

Definition at line 981 of file graph_coloring_test.cc.

References build_wheel(), Aleph::chromatic_number(), Aleph::divide_and_conquer_partition_dp(), and Aleph::is_valid_coloring().

◆ TEST() [13/48]

TEST	(	GraphColoring	,
		ChromaticNumberWheelOddRing
	)

Definition at line 991 of file graph_coloring_test.cc.

References build_wheel(), Aleph::chromatic_number(), Aleph::divide_and_conquer_partition_dp(), and Aleph::is_valid_coloring().

◆ TEST() [14/48]

TEST	(	GraphColoring	,
		CompleteBipartiteK33
	)

Definition at line 314 of file graph_coloring_test.cc.

References build_complete_bipartite(), Aleph::divide_and_conquer_partition_dp(), Aleph::dsatur_coloring(), Aleph::is_valid_coloring(), and k.

◆ TEST() [15/48]

TEST	(	GraphColoring	,
		CompleteK2
	)

Definition at line 265 of file graph_coloring_test.cc.

References build_complete_graph(), Aleph::divide_and_conquer_partition_dp(), Aleph::dsatur_coloring(), Aleph::greedy_coloring(), Aleph::is_valid_coloring(), and Aleph::welsh_powell_coloring().

◆ TEST() [16/48]

TEST	(	GraphColoring	,
		CompleteK3
	)

Definition at line 280 of file graph_coloring_test.cc.

References build_complete_graph(), Aleph::divide_and_conquer_partition_dp(), Aleph::dsatur_coloring(), Aleph::is_valid_coloring(), and k.

◆ TEST() [17/48]

TEST	(	GraphColoring	,
		CompleteK4
	)

Definition at line 290 of file graph_coloring_test.cc.

References build_complete_graph(), Aleph::divide_and_conquer_partition_dp(), Aleph::dsatur_coloring(), Aleph::is_valid_coloring(), and k.

◆ TEST() [18/48]

TEST	(	GraphColoring	,
		CompleteK5
	)

Definition at line 300 of file graph_coloring_test.cc.

References build_complete_graph(), Aleph::divide_and_conquer_partition_dp(), Aleph::dsatur_coloring(), Aleph::is_valid_coloring(), and k.

◆ TEST() [19/48]

TEST	(	GraphColoring	,
		CookiesPreservedAfterColoring
	)

Definition at line 867 of file graph_coloring_test.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::dsatur_coloring(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), and NODE_COOKIE.

◆ TEST() [20/48]

TEST	(	GraphColoring	,
		DigraphReverseOrderStillUsesTwoColors
	)

Definition at line 795 of file graph_coloring_test.cc.

References Aleph::chromatic_number(), Aleph::divide_and_conquer_partition_dp(), Aleph::dsatur_coloring(), Aleph::greedy_coloring(), Aleph::DynMapTree< Key, Data, Tree, Compare >::insert(), Aleph::is_valid_coloring(), and Aleph::welsh_powell_coloring().

◆ TEST() [21/48]

TEST	(	GraphColoring	,
		DigraphSingleArcUsesTwoColors
	)

Definition at line 773 of file graph_coloring_test.cc.

References Aleph::chromatic_number(), Aleph::divide_and_conquer_partition_dp(), Aleph::dsatur_coloring(), Aleph::greedy_coloring(), Aleph::is_valid_coloring(), and Aleph::welsh_powell_coloring().

◆ TEST() [22/48]

TEST	(	GraphColoring	,
		DisconnectedComponents
	)

Definition at line 406 of file graph_coloring_test.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::dsatur_coloring(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), Aleph::is_valid_coloring(), and k.

◆ TEST() [23/48]

TEST	(	GraphColoring	,
		DisconnectedMixed
	)

Definition at line 431 of file graph_coloring_test.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::dsatur_coloring(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), Aleph::is_valid_coloring(), and k.

◆ TEST() [24/48]

TEST	(	GraphColoring	,
		EmptyGraph
	)

Definition at line 212 of file graph_coloring_test.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::dsatur_coloring(), Aleph::greedy_coloring(), Aleph::is_valid_coloring(), and Aleph::welsh_powell_coloring().

◆ TEST() [25/48]

TEST	(	GraphColoring	,
		EvenCycle
	)

Definition at line 358 of file graph_coloring_test.cc.

References build_cycle(), Aleph::divide_and_conquer_partition_dp(), Aleph::dsatur_coloring(), Aleph::is_valid_coloring(), and k.

◆ TEST() [26/48]

TEST	(	GraphColoring	,
		ExamScheduling
	)

Definition at line 948 of file graph_coloring_test.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::dsatur_coloring(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), and Aleph::is_valid_coloring().

◆ TEST() [27/48]

TEST	(	GraphColoring	,
		FunctorWrappers
	)

Definition at line 842 of file graph_coloring_test.cc.

References build_complete_graph(), Aleph::divide_and_conquer_partition_dp(), and Aleph::is_valid_coloring().

◆ TEST() [28/48]

TEST	(	GraphColoring	,
		GreedyBoundDeltaPlusOne
	)

Definition at line 500 of file graph_coloring_test.cc.

References build_complete_bipartite(), Aleph::divide_and_conquer_partition_dp(), Aleph::greedy_coloring(), Aleph::is_valid_coloring(), and k.

◆ TEST() [29/48]

TEST	(	GraphColoring	,
		IsolatedNodes
	)

Definition at line 243 of file graph_coloring_test.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::dsatur_coloring(), Aleph::greedy_coloring(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), Aleph::is_valid_coloring(), and Aleph::welsh_powell_coloring().

◆ TEST() [30/48]

TEST	(	GraphColoring	,
		OddCycle
	)

Definition at line 368 of file graph_coloring_test.cc.

References build_cycle(), Aleph::divide_and_conquer_partition_dp(), Aleph::dsatur_coloring(), Aleph::is_valid_coloring(), and k.

◆ TEST() [31/48]

TEST	(	GraphColoring	,
		Path5
	)

Definition at line 324 of file graph_coloring_test.cc.

References build_path(), Aleph::divide_and_conquer_partition_dp(), Aleph::dsatur_coloring(), Aleph::is_valid_coloring(), and k.

◆ TEST() [32/48]

TEST	(	GraphColoring	,
		PetersenGraph
	)

Definition at line 392 of file graph_coloring_test.cc.

References build_petersen(), Aleph::divide_and_conquer_partition_dp(), Aleph::dsatur_coloring(), Aleph::is_valid_coloring(), and k.

◆ TEST() [33/48]

TEST	(	GraphColoring	,
		RandomGraphsPropertyBased
	)

Definition at line 1005 of file graph_coloring_test.cc.

References build_random_graph(), Aleph::chromatic_number(), Aleph::divide_and_conquer_partition_dp(), Aleph::dsatur_coloring(), GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::greedy_coloring(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), Aleph::is_valid_coloring(), k, nodes, num_nodes, rng, and Aleph::welsh_powell_coloring().

◆ TEST() [34/48]

TEST	(	GraphColoring	,
		SGraphBasicColoring
	)

Definition at line 737 of file graph_coloring_test.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::dsatur_coloring(), Aleph::List_SGraph< __Graph_Node, __Graph_Arc >::insert_arc(), Aleph::List_SGraph< __Graph_Node, __Graph_Arc >::insert_node(), Aleph::is_valid_coloring(), and k.

◆ TEST() [35/48]

TEST	(	GraphColoring	,
		SGraphGreedy
	)

Definition at line 754 of file graph_coloring_test.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::greedy_coloring(), Aleph::List_SGraph< __Graph_Node, __Graph_Arc >::insert_arc(), Aleph::List_SGraph< __Graph_Node, __Graph_Arc >::insert_node(), Aleph::is_valid_coloring(), and k.

◆ TEST() [36/48]

TEST	(	GraphColoring	,
		SingleNode
	)

Definition at line 227 of file graph_coloring_test.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::dsatur_coloring(), Aleph::greedy_coloring(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), Aleph::is_valid_coloring(), and Aleph::welsh_powell_coloring().

◆ TEST() [37/48]

TEST	(	GraphColoring	,
		SouthAmericaMapColoring
	)

Definition at line 892 of file graph_coloring_test.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::dsatur_coloring(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), Aleph::is_valid_coloring(), and k.

◆ TEST() [38/48]

TEST	(	GraphColoring	,
		Star6
	)

Definition at line 334 of file graph_coloring_test.cc.

References build_star(), Aleph::divide_and_conquer_partition_dp(), Aleph::dsatur_coloring(), Aleph::is_valid_coloring(), and k.

◆ TEST() [39/48]

TEST	(	GraphColoring	,
		TreeChain
	)

Definition at line 344 of file graph_coloring_test.cc.

References build_path(), Aleph::divide_and_conquer_partition_dp(), Aleph::greedy_coloring(), and Aleph::is_valid_coloring().

◆ TEST() [40/48]

TEST	(	GraphColoring	,
		Triangle
	)

Definition at line 378 of file graph_coloring_test.cc.

References build_cycle(), Aleph::divide_and_conquer_partition_dp(), Aleph::dsatur_coloring(), Aleph::is_valid_coloring(), and k.

◆ TEST() [41/48]

TEST	(	GraphColoring	,
		ValidationRejectsForeignKeyedMap
	)

Definition at line 545 of file graph_coloring_test.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::DynMapTree< Key, Data, Tree, Compare >::insert(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), and Aleph::is_valid_coloring().

◆ TEST() [42/48]

TEST	(	GraphColoring	,
		ValidationRejectsInvalidColoring
	)

Definition at line 516 of file graph_coloring_test.cc.

References build_complete_graph(), Aleph::divide_and_conquer_partition_dp(), Aleph::DynMapTree< Key, Data, Tree, Compare >::insert(), and Aleph::is_valid_coloring().

◆ TEST() [43/48]

TEST	(	GraphColoring	,
		ValidationRejectsIsolatedNodeMissingFromColors
	)

Definition at line 568 of file graph_coloring_test.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::DynMapTree< Key, Data, Tree, Compare >::insert(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), and Aleph::is_valid_coloring().

◆ TEST() [44/48]

TEST	(	GraphColoring	,
		ValidationRejectsMissingNode
	)

Definition at line 528 of file graph_coloring_test.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::DynMapTree< Key, Data, Tree, Compare >::insert(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), and Aleph::is_valid_coloring().

◆ TEST() [45/48]

TEST	(	GraphColoring	,
		ValidationRejectsParallelEdge
	)

Definition at line 604 of file graph_coloring_test.cc.

References Aleph::chromatic_number(), Aleph::divide_and_conquer_partition_dp(), Aleph::dsatur_coloring(), Aleph::greedy_coloring(), Aleph::DynMapTree< Key, Data, Tree, Compare >::insert(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), Aleph::is_valid_coloring(), and Aleph::welsh_powell_coloring().

◆ TEST() [46/48]

TEST	(	GraphColoring	,
		ValidationRejectsSelfLoop
	)

Definition at line 588 of file graph_coloring_test.cc.

References Aleph::chromatic_number(), Aleph::divide_and_conquer_partition_dp(), Aleph::dsatur_coloring(), Aleph::greedy_coloring(), Aleph::DynMapTree< Key, Data, Tree, Compare >::insert(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), Aleph::is_valid_coloring(), and Aleph::welsh_powell_coloring().

◆ TEST() [47/48]

TEST	(	GraphColoring	,
		WheelW5EvenRing
	)

Definition at line 454 of file graph_coloring_test.cc.

References build_wheel(), Aleph::divide_and_conquer_partition_dp(), Aleph::dsatur_coloring(), Aleph::is_valid_coloring(), and k.

◆ TEST() [48/48]

TEST	(	GraphColoring	,
		WheelW6OddRing
	)

Definition at line 465 of file graph_coloring_test.cc.

References build_wheel(), Aleph::divide_and_conquer_partition_dp(), Aleph::dsatur_coloring(), Aleph::is_valid_coloring(), and k.

Typedefs

Functions

Typedef Documentation

◆ AGraph

◆ DGraph

◆ Graph

◆ SGraph

Function Documentation

◆ build_complete_bipartite()

◆ build_complete_graph()

◆ build_cycle()

◆ build_path()

◆ build_petersen()

◆ build_star()

◆ build_wheel()

◆ count_distinct_colors()

◆ TEST() [1/48]

◆ TEST() [2/48]

◆ TEST() [3/48]

◆ TEST() [4/48]

◆ TEST() [5/48]

◆ TEST() [6/48]

◆ TEST() [7/48]

◆ TEST() [8/48]

◆ TEST() [9/48]

◆ TEST() [10/48]

◆ TEST() [11/48]

◆ TEST() [12/48]

◆ TEST() [13/48]

◆ TEST() [14/48]

◆ TEST() [15/48]

◆ TEST() [16/48]

◆ TEST() [17/48]

◆ TEST() [18/48]

◆ TEST() [19/48]

◆ TEST() [20/48]

◆ TEST() [21/48]

◆ TEST() [22/48]

◆ TEST() [23/48]

◆ TEST() [24/48]

◆ TEST() [25/48]

◆ TEST() [26/48]

◆ TEST() [27/48]

◆ TEST() [28/48]

◆ TEST() [29/48]

◆ TEST() [30/48]

◆ TEST() [31/48]

◆ TEST() [32/48]

◆ TEST() [33/48]

◆ TEST() [34/48]

◆ TEST() [35/48]

◆ TEST() [36/48]

◆ TEST() [37/48]

◆ TEST() [38/48]

◆ TEST() [39/48]

◆ TEST() [40/48]

◆ TEST() [41/48]

◆ TEST() [42/48]

◆ TEST() [43/48]

◆ TEST() [44/48]

◆ TEST() [45/48]

◆ TEST() [46/48]

◆ TEST() [47/48]

◆ TEST() [48/48]