Export colored graphs to Graphviz DOT for visual comparison. More...

#include <fstream>
#include <iostream>
#include <string>
#include <ah-errors.H>
#include <Graph_Coloring.H>
#include <tpl_graph.H>

Include dependency graph for graph_coloring_graphviz_example.cc:

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

using	Node = Graph::Node

using	ColorMap = DynMapTree< Node *, size_t >

Functions
static constexpr size_t	palette_size ()

static string	color_name (size_t c)

static string	color_legend (size_t num_colors)

static void	build_crown_graph (Graph &g, Node left[Crown_Size], Node right[Crown_Size])

static void	locate_node (Node node, Node left[Crown_Size], Node *right[Crown_Size], bool &is_left, size_t &index)

static void	write_colored_node (ostream &out, const string &dot_id, const string &label, const char *pos, size_t color)

static void	write_coloring_dot (const string &filename, const string &title, const Graph &g, Node left[Crown_Size], Node right[Crown_Size], const ColorMap &colors, size_t num_colors)

template<class Coloring >
static void	export_variant (const string &prefix, const string &suffix, const string &title, const Graph &g, Node left[Crown_Size], Node right[Crown_Size], Coloring coloring)

int	main (int argc, char **argv)

Variables
static constexpr size_t	Crown_Size = 5

static const char *	fill_palette [] = {"#f94144", "#277da1", "#90be6d", "#f8961e", "#7b2cbf", "#577590"}

static const char *	font_palette [] = {"#ffffff", "#ffffff", "#111111", "#111111", "#ffffff", "#ffffff"}

static const char *	palette_names [] = {"coral", "ocean", "sage", "amber", "violet", "slate"}

static const char *	left_positions [Crown_Size] = {"0,8!", "0,6!", "0,4!", "0,2!", "0,0!"}

static const char *	right_positions [Crown_Size] = {"5,8!", "5,6!", "5,4!", "5,2!", "5,0!"}

Detailed Description

Export colored graphs to Graphviz DOT for visual comparison.

This example builds a crown graph H_5, colors it with several algorithms from Graph_Coloring.H, and writes one DOT file per algorithm. The node order is intentionally adversarial for greedy coloring, so the visual output shows why DSatur and the exact solver can be much better than a naive first-fit pass.

Generated files:

<prefix>_greedy.dot
<prefix>_welsh_powell.dot
<prefix>_dsatur.dot
<prefix>_exact.dot

Usage:

./graph_coloring_graphviz_example
./graph_coloring_graphviz_example /tmp/crown
neato -n -Tsvg /tmp/crown_dsatur.dot -o /tmp/crown_dsatur.svg

Definition in file graph_coloring_graphviz_example.cc.

Typedef Documentation

◆ ColorMap

using ColorMap = DynMapTree<Node *, size_t>

Definition at line 69 of file graph_coloring_graphviz_example.cc.

◆ Graph

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

Definition at line 67 of file graph_coloring_graphviz_example.cc.

◆ Node

using Node = Graph::Node

Definition at line 68 of file graph_coloring_graphviz_example.cc.

Function Documentation

◆ build_crown_graph()

static void build_crown_graph	(	Graph &	g,
		Node *	left[Crown_Size],
		Node *	right[Crown_Size]
	)

static

Definition at line 108 of file graph_coloring_graphviz_example.cc.

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

Referenced by main().

◆ color_legend()

static string color_legend ( size_t num_colors )

static

Definition at line 93 of file graph_coloring_graphviz_example.cc.

References color_name(), Aleph::divide_and_conquer_partition_dp(), and Aleph::to_string().

Referenced by write_coloring_dot().

◆ color_name()

static string color_name ( size_t c )

static

Definition at line 88 of file graph_coloring_graphviz_example.cc.

References palette_names, and palette_size().

Referenced by color_legend().

◆ export_variant()

template<class Coloring >

static void export_variant	(	const string &	prefix,
		const string &	suffix,
		const string &	title,
		const Graph &	g,
		Node *	left[Crown_Size],
		Node *	right[Crown_Size],
		Coloring	coloring
	)

static

Definition at line 207 of file graph_coloring_graphviz_example.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::prefix(), Aleph::suffix(), and write_coloring_dot().

Referenced by main().

◆ locate_node()

static void locate_node	(	Node *	node,
		Node *	left[Crown_Size],
		Node *	right[Crown_Size],
		bool &	is_left,
		size_t &	index
	)

static

Definition at line 122 of file graph_coloring_graphviz_example.cc.

References ah_runtime_error, and Crown_Size.

Referenced by write_coloring_dot().

◆ main()

int main	(	int	argc,
		char **	argv
	)

Definition at line 219 of file graph_coloring_graphviz_example.cc.

References build_crown_graph(), Aleph::chromatic_number(), Crown_Size, Aleph::divide_and_conquer_partition_dp(), Aleph::dsatur_coloring(), export_variant(), GraphCommon< GT, Node, Arc >::get_num_arcs(), GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::greedy_coloring(), Aleph::prefix(), and Aleph::welsh_powell_coloring().

◆ palette_size()

static constexpr size_t palette_size ( )

staticconstexpr

Definition at line 83 of file graph_coloring_graphviz_example.cc.

References fill_palette.

Referenced by color_name(), Aleph::nonplanar_certificate_to_dot(), and write_colored_node().

◆ write_colored_node()

static void write_colored_node	(	ostream &	out,
		const string &	dot_id,
		const string &	label,
		const char *	pos,
		size_t	color
	)

static

Definition at line 144 of file graph_coloring_graphviz_example.cc.

References Aleph::color(), Aleph::divide_and_conquer_partition_dp(), fill_palette, font_palette, and palette_size().

Referenced by write_coloring_dot().

◆ write_coloring_dot()

static void write_coloring_dot	(	const string &	filename,
		const string &	title,
		const Graph &	g,
		Node *	left[Crown_Size],
		Node *	right[Crown_Size],
		const ColorMap &	colors,
		size_t	num_colors
	)