Graph_Coloring.H File Reference

Graph coloring algorithms and heuristics. More...

#include <tpl_graph.H>
#include <tpl_array.H>
#include <tpl_dynMapTree.H>
#include <tpl_dynSetTree.H>
#include <tpl_sort_utils.H>
#include <cookie_guard.H>
#include <ah-errors.H>

Include dependency graph for Graph_Coloring.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	Aleph::Greedy_Coloring< GT, SA >
	Functor wrapper for greedy_coloring. More...
class	Aleph::Welsh_Powell_Coloring< GT, SA >
	Functor wrapper for welsh_powell_coloring. More...
class	Aleph::DSatur_Coloring< GT, SA >
	Functor wrapper for dsatur_coloring. More...

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.
namespace	Aleph::graph_coloring_detail

Functions
void *	Aleph::graph_coloring_detail::encode_color (size_t c) noexcept
bool	Aleph::graph_coloring_detail::is_colored (void *cookie) noexcept
size_t	Aleph::graph_coloring_detail::decode_color (void *cookie) noexcept
size_t	Aleph::graph_coloring_detail::smallest_available (const DynSetTree< size_t > &used)
template<class GT , class SA >
void	Aleph::graph_coloring_detail::build_undirected_adj (const GT &g, DynMapTree< typename GT::Node *, DynList< typename GT::Node * > > &adj)
	Internal helper to pre-build undirected adjacency lists.
template<class GT , class SA = Dft_Show_Arc<GT>>
void	Aleph::graph_coloring_detail::validate_no_self_loops (const GT &g)
template<class GT , class SA = Dft_Show_Arc<GT>>
size_t	Aleph::greedy_coloring (const GT &g, DynMapTree< typename GT::Node *, size_t > &colors)
	Greedy graph coloring in iteration order.
template<class GT , class SA = Dft_Show_Arc<GT>>
size_t	Aleph::welsh_powell_coloring (const GT &g, DynMapTree< typename GT::Node *, size_t > &colors)
	Welsh-Powell graph coloring.
template<class GT , class SA = Dft_Show_Arc<GT>>
size_t	Aleph::dsatur_coloring (const GT &g, DynMapTree< typename GT::Node *, size_t > &colors)
	DSatur graph coloring (saturation-degree heuristic).
template<class GT , class SA = Dft_Show_Arc<GT>>
bool	Aleph::is_valid_coloring (const GT &g, const DynMapTree< typename GT::Node *, size_t > &colors)
	Validates a graph coloring.
template<class GT , class SA = Dft_Show_Arc<GT>>
size_t	Aleph::chromatic_number (const GT &g, DynMapTree< typename GT::Node *, size_t > &colors)
	Computes the exact chromatic number of a small graph.

Detailed Description

Graph coloring algorithms and heuristics.

This file provides a collection of algorithms for the vertex coloring problem, which aims to assign a color to each node such that no two adjacent nodes share the same color.

Consistency across Directed and Undirected Graphs

Graph coloring is fundamentally an undirected problem. All algorithms in this module treat directed arcs as bidirectional constraints: if there is an arc \(u \to v\), then \(u\) and \(v\) cannot have the same color.

Included Algorithms:

• Greedy Coloring: Processes nodes in their natural iteration order. Complexity: \(O((V+E) \log V)\).
• Welsh-Powell: Sorts nodes by decreasing degree before coloring. Complexity: \(O((V+E) \log V)\).
• DSatur (Degree of Saturation): Adaptive heuristic that prioritizes nodes with the most distinct colors in their neighborhood. Complexity: \(O(V^2 + E \log V)\).
• Chromatic Number: Exact minimum colors ( \(\chi(G)\)) for small graphs (up to 64 nodes) via backtracking. Complexity: Exponential.

Implementation Details

All algorithms use the NODE_COOKIE field of graph nodes for O(1) color lookups. Aleph::Cookie_Saver ensures pre-existing cookies are restored upon exit.

Author

Leandro Rabindranath León

Definition in file Graph_Coloring.H.