graph_coloring_example.cc File Reference

Graph coloring algorithms in Aleph-w: greedy, Welsh-Powell, DSatur, and exact chromatic number. More...

#include <iostream>
#include <iomanip>
#include <string>
#include <cstdio>
#include <Graph_Coloring.H>
#include <tpl_graph.H>

Include dependency graph for graph_coloring_example.cc:

Go to the source code of this file.

Typedefs
using	G = List_Graph< Graph_Node< string >, Graph_Arc< Empty_Class > >
using	Node = G::Node
using	ColorMap = DynMapTree< Node *, size_t >

Functions
static const char *	color_name (size_t c)
static void	print_coloring (const G &g, const ColorMap &colors, size_t num_colors)
static void	separator (const string &title)
static void	demo_map_coloring ()
	Demonstrates graph coloring as a map-coloring problem.
static void	demo_exam_scheduling ()
	Models exam scheduling as a graph coloring problem.
static void	demo_register_allocation ()
	Models register allocation as graph coloring.
static void	demo_algorithm_comparison ()
	The Petersen graph is a well-known benchmark in graph theory.
static void	demo_cookie_safety ()
	Shows that running one coloring algorithm does not alter cookies that were set previously by user code.
int	main ()

Variables
static const char *	color_names []

Detailed Description

Graph coloring algorithms in Aleph-w: greedy, Welsh-Powell, DSatur, and exact chromatic number.

Overview

Graph coloring assigns a color to each vertex such that no two adjacent vertices share the same color. The minimum number of colors needed is the chromatic number χ(G).

This example demonstrates Aleph-w's Graph_Coloring.H module on four progressively richer scenarios:

1. Map coloring — South American countries as an adjacency graph.
2. Exam scheduling — courses with shared students cannot overlap.
3. Register allocation — variables with overlapping lifetimes need different CPU registers.
4. Algorithm comparison — Greedy vs Welsh-Powell vs DSatur on a classic benchmark graph (Petersen).

Algorithms provided by <tt>Graph_Coloring.H</tt>

Function	Strategy	Complexity
greedy_coloring	First-fit in iteration order	O((V+E) log V)
welsh_powell_coloring	First-fit, decreasing degree order	O((V+E) log V)
dsatur_coloring	Most-saturated vertex first (adaptive)	O(V^2 + E log V)
is_valid_coloring	Validation	O(E log V)
chromatic_number	Exact (branch-and-bound, max 64 nodes)	Exponential

State safety

Coloring algorithms temporarily reuse NODE_COOKIE internally while running, and restore any pre-existing node cookies on exit. However, they are not thread-safe or reentrant with respect to cookie usage: concurrent executions, nested cookie users, or other simultaneous cookie-based algorithms require external synchronization.

Usage

./graph_coloring_example

No command-line options; all scenarios are hard-coded. For Graphviz output, see graph_coloring_graphviz_example.

Author

Leandro Rabindranath León

Definition in file graph_coloring_example.cc.

Typedef Documentation

ColorMap

using ColorMap = DynMapTree<Node *, size_t>

Definition at line 101 of file graph_coloring_example.cc.

G

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

Definition at line 99 of file graph_coloring_example.cc.

Node

using Node = G::Node

Definition at line 100 of file graph_coloring_example.cc.

Function Documentation

color_name()

static const char * color_name ( size_t  c )

static

Definition at line 112 of file graph_coloring_example.cc.

References color_names, and N.

Referenced by print_coloring().

demo_algorithm_comparison()

static void demo_algorithm_comparison ( )

static

The Petersen graph is a well-known benchmark in graph theory.

It is 3-regular, vertex-transitive, and has chromatic number 3.

It is a hard case for greedy algorithms because the result depends on the vertex order.

Definition at line 352 of file graph_coloring_example.cc.

References Aleph::chromatic_number(), Aleph::divide_and_conquer_partition_dp(), Aleph::dsatur_coloring(), GraphCommon< GT, Node, Arc >::get_num_arcs(), 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(), nodes, print_coloring(), separator(), Aleph::to_string(), and Aleph::welsh_powell_coloring().

Referenced by main().

demo_cookie_safety()

static void demo_cookie_safety ( )

static

Shows that running one coloring algorithm does not alter cookies that were set previously by user code.

Definition at line 421 of file graph_coloring_example.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(), k, NODE_COOKIE, and separator().

Referenced by main().

demo_exam_scheduling()

static void demo_exam_scheduling ( )

static

Models exam scheduling as a graph coloring problem.

• Nodes = courses
• Edges = two courses share at least one student (cannot be scheduled at the same time)
• Colors = exam time slots

Minimum coloring = fewest time slots needed.

Definition at line 216 of file graph_coloring_example.cc.

References Aleph::chromatic_number(), Aleph::divide_and_conquer_partition_dp(), Aleph::dsatur_coloring(), GraphCommon< GT, Node, Arc >::get_num_arcs(), 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(), print_coloring(), separator(), and Aleph::welsh_powell_coloring().

Referenced by main().

demo_map_coloring()

static void demo_map_coloring ( )

static

Demonstrates graph coloring as a map-coloring problem.

Each node is a country; each edge means the two countries share a border. The Four Color Theorem guarantees that every planar map needs at most 4 colors.

Definition at line 154 of file graph_coloring_example.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::dsatur_coloring(), 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(), k, print_coloring(), and separator().

Referenced by main().

demo_register_allocation()

static void demo_register_allocation ( )

static

Models register allocation as graph coloring.

In compiler register allocation:

• Nodes = program variables (live ranges)
• Edges = two variables are simultaneously live (cannot share a register)
• Colors = CPU registers

If the chromatic number ≤ number of available registers, no spilling is needed.

Definition at line 282 of file graph_coloring_example.cc.

References Aleph::chromatic_number(), Aleph::divide_and_conquer_partition_dp(), Aleph::dsatur_coloring(), GraphCommon< GT, Node, Arc >::get_node_it(), 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(), Aleph::is_valid_coloring(), k, and separator().

Referenced by main().

main()

int main

(

)

Definition at line 465 of file graph_coloring_example.cc.

References demo_algorithm_comparison(), demo_cookie_safety(), demo_exam_scheduling(), demo_map_coloring(), and demo_register_allocation().

print_coloring()

static void print_coloring ( const G &  g, const ColorMap &  colors, size_t  num_colors  )

static

Definition at line 121 of file graph_coloring_example.cc.

References color_name(), Aleph::divide_and_conquer_partition_dp(), GraphCommon< GT, Node, Arc >::get_node_it(), and Aleph::is_valid_coloring().

Referenced by demo_algorithm_comparison(), demo_exam_scheduling(), and demo_map_coloring().

separator()

static void separator ( const string &  title )

static

Definition at line 136 of file graph_coloring_example.cc.

Referenced by demo_algorithm_comparison(), demo_cookie_safety(), demo_exam_scheduling(), demo_map_coloring(), and demo_register_allocation().

Variable Documentation

color_names

const char* color_names[]

static

Initial value:

= {
  "Red", "Blue", "Green", "Yellow", "Orange",
  "Purple", "Cyan", "Magenta", "Brown", "Gray"
}

Definition at line 107 of file graph_coloring_example.cc.

Referenced by color_name().