geos::graph::RLFGraphColoring Class Reference

Graph coloring implementation using the Recursive Largest First (RLF) algorithm. More...

#include <RLFGraphColoring.hpp>

Inheritance diagram for geos::graph::RLFGraphColoring:

Public Member Functions
	RLFGraphColoring ()
	Constructor.
	~RLFGraphColoring ()
	Destructor.
std::vector< int >	colorGraph (const std::vector< camp::idx_t > &xadj, const std::vector< camp::idx_t > &adjncy) override
	Colors a graph. More...
int	colorGraph (const std::vector< camp::idx_t > &localAdjncy) override
	Colors a graph assuming one node per rank. More...
size_t	getNumberOfColors (const std::vector< int > &colors) const
	Returns the number of distinct colors used. More...
bool	isColoringValid (const std::vector< camp::idx_t > &xadj, const std::vector< camp::idx_t > &adjncy, const std::vector< int > &colors) const
	Validates the coloring of a graph. More...
Public Member Functions inherited from geos::graph::GraphColoringBase
	GraphColoringBase (MPI_Comm comm=MPI_COMM_GEOS)
	Constructor. More...
virtual	~GraphColoringBase ()
	Virtual destructor.

Additional Inherited Members
Static Public Member Functions inherited from geos::graph::GraphColoringBase
static bool	isColoringValid (const std::vector< camp::idx_t > &xadj, const std::vector< camp::idx_t > &adjncy, const std::vector< int > &coloring)
	Checks the validity of the graph coloring. More...
static bool	isColoringValid (const std::vector< camp::idx_t > &adjncy, const int color, MPI_Comm comm)
	Checks the validity of the graph coloring assuming one node per rank. More...
static size_t	getNumberOfColors (const std::vector< int > &colors)
	Counts the number of distinct colors. More...
static size_t	getNumberOfColors (const std::vector< int > &colors, MPI_Comm comm)
	Counts the number of distinct colors (parallel version). More...
static size_t	getNumberOfColors (const int color, MPI_Comm comm)
	Counts the number of distinct colors assuming one node per rank (parallel version). More...
Protected Attributes inherited from geos::graph::GraphColoringBase
MPI_Comm	m_comm

Detailed Description

Graph coloring implementation using the Recursive Largest First (RLF) algorithm.

This class implements the RLF algorithm to assign colors to graph nodes such that no two adjacent nodes share the same color. It supports both full adjacency-based coloring and simplified one-node-per-rank coloring.

Reference: Leighton, F. (1979). "A graph coloring algorithm for large scheduling problems". Journal of Research of the National Bureau of Standards. 84 (6): 489–503.

Definition at line 45 of file RLFGraphColoring.hpp.

Member Function Documentation

colorGraph() [1/2]

int geos::graph::RLFGraphColoring::colorGraph ( const std::vector< camp::idx_t > &  localAdjncy )

overridevirtual

Colors a graph assuming one node per rank.

Parameters

localAdjncy

Local adjacency list.

Returns

Color of the node.

Implements geos::graph::GraphColoringBase.

colorGraph() [2/2]

std::vector< int > geos::graph::RLFGraphColoring::colorGraph ( const std::vector< camp::idx_t > &  xadj, const std::vector< camp::idx_t > &  adjncy  )

overridevirtual

Colors a graph.

Parameters

xadj	Adjacency list offsets.
adjncy	Adjacency list.

Returns

A vector of assigned colors.

Implements geos::graph::GraphColoringBase.

getNumberOfColors()

size_t geos::graph::RLFGraphColoring::getNumberOfColors

(

const std::vector< int > &

colors

)

const

Returns the number of distinct colors used.

Parameters

colors

Vector of color assignments.

Returns

Number of unique colors.

isColoringValid()

bool geos::graph::RLFGraphColoring::isColoringValid	(	const std::vector< camp::idx_t > &	xadj,
		const std::vector< camp::idx_t > &	adjncy,
		const std::vector< int > &	colors
	)		const

Validates the coloring of a graph.

Parameters

xadj	Adjacency list offsets.
adjncy	Adjacency list.
colors	Vector of assigned colors.

Returns

True if coloring is valid, false otherwise.

---

The documentation for this class was generated from the following file:

• coreComponents/mesh/graphs/RLFGraphColoring.hpp