#include <Coloring.h>

Inheritance diagram for limbo::algorithms::coloring::Coloring< GraphType >:

Classes
struct	EdgeHashType
	hasher class for graph_edge_type More...

Public Types
enum	ColorNumType { TWO = 2 , THREE = 3 , FOUR = 4 }
	number of colors More...

typedef GraphType	graph_type
typedef boost::graph_traits< graph_type >::vertex_descriptor	graph_vertex_type
typedef boost::graph_traits< graph_type >::edge_descriptor	graph_edge_type
typedef boost::graph_traits< graph_type >::vertex_iterator	vertex_iterator_type
typedef boost::graph_traits< graph_type >::edge_iterator	edge_iterator_type
typedef boost::graph_traits< graph_type >::adjacency_iterator	adjacency_iterator
typedef boost::property_traits< typenameboost::property_map< graph_type, boost::edge_weight_t >::const_type >::value_type	edge_weight_type
typedef boost::property_traits< typenameboost::property_map< graph_type, boost::edge_index_t >::const_type >::value_type	edge_index_type

Public Member Functions
	Coloring (graph_type const &g)
virtual	~Coloring ()
	destructor
virtual double	operator() ()
virtual void	color_num (ColorNumType cn)
virtual void	color_num (int8_t cn)
virtual ColorNumType	color_num () const
virtual void	precolor (graph_vertex_type v, int8_t c)
virtual bool	has_precolored () const
virtual double	stitch_weight () const
virtual void	stitch_weight (double w)
virtual void	threads (int32_t t)
virtual int8_t	color (graph_vertex_type v) const
virtual edge_weight_type	edge_weight (graph_edge_type const &e) const
virtual edge_weight_type	calc_cost (std::vector< int8_t > const &vColor) const
void	check_edge_weight (graph_type const &g, edge_weight_type lb, edge_weight_type ub) const
void	print_edge_weight (graph_type const &g) const
void	depth_first_search_stitch (graph_vertex_type v, std::vector< int32_t > &stitch_relation_set, std::vector< bool > &visited, uint32_t &stitch_edge_num, int32_t stitch_index)
virtual void	write_graph (std::string const &filename) const
virtual void	write_graph (std::string const &filename, graph_type const &g, std::vector< int8_t > const &vColor) const

Protected Member Functions
virtual double	coloring ()=0

Protected Attributes
graph_type const &	m_graph
	initial graph
std::vector< int8_t >	m_vColor
	coloring solutions
ColorNumType	m_color_num
	number of colors
double	m_stitch_weight
	stitch weight
int32_t	m_threads
	control number of threads for ILP solver
bool	m_has_precolored
	whether contain precolored vertices
int32_t	m_stitch_index
int32_t	m_big_edge_num
std::vector< int32_t >	m_stitch_relation_set
std::vector< int32_t >	m_edge_index_vector

Detailed Description

template<typename GraphType>
class limbo::algorithms::coloring::Coloring< GraphType >

Base class for all coloring algorithms.
All coloring algorithms support 3 and 4 colors.

Template Parameters

GraphType graph type

Definition at line 114 of file Coloring.h.

Member Typedef Documentation

◆ adjacency_iterator

template<typename GraphType>

typedef boost::graph_traits<graph_type>::adjacency_iterator limbo::algorithms::coloring::Coloring< GraphType >::adjacency_iterator

Definition at line 123 of file Coloring.h.

◆ edge_index_type

template<typename GraphType>

typedef boost::property_traits<typenameboost::property_map<graph_type,boost::edge_index_t>::const_type>::value_type limbo::algorithms::coloring::Coloring< GraphType >::edge_index_type

Definition at line 129 of file Coloring.h.

◆ edge_iterator_type

template<typename GraphType>

typedef boost::graph_traits<graph_type>::edge_iterator limbo::algorithms::coloring::Coloring< GraphType >::edge_iterator_type

Definition at line 122 of file Coloring.h.

◆ edge_weight_type

template<typename GraphType>

typedef boost::property_traits<typenameboost::property_map<graph_type,boost::edge_weight_t>::const_type>::value_type limbo::algorithms::coloring::Coloring< GraphType >::edge_weight_type

Definition at line 125 of file Coloring.h.

◆ graph_edge_type

template<typename GraphType>

typedef boost::graph_traits<graph_type>::edge_descriptor limbo::algorithms::coloring::Coloring< GraphType >::graph_edge_type

Definition at line 120 of file Coloring.h.

◆ graph_type

template<typename GraphType>

typedef GraphType limbo::algorithms::coloring::Coloring< GraphType >::graph_type

Definition at line 118 of file Coloring.h.

◆ graph_vertex_type

template<typename GraphType>

typedef boost::graph_traits<graph_type>::vertex_descriptor limbo::algorithms::coloring::Coloring< GraphType >::graph_vertex_type

Definition at line 119 of file Coloring.h.

◆ vertex_iterator_type

template<typename GraphType>

typedef boost::graph_traits<graph_type>::vertex_iterator limbo::algorithms::coloring::Coloring< GraphType >::vertex_iterator_type

Definition at line 121 of file Coloring.h.

Member Enumeration Documentation

◆ ColorNumType

template<typename GraphType>

enum limbo::algorithms::coloring::Coloring::ColorNumType

number of colors

Definition at line 134 of file Coloring.h.

Constructor & Destructor Documentation

◆ Coloring()

template<typename GraphType>

limbo::algorithms::coloring::Coloring< GraphType >::Coloring ( graph_type const & g )

constructor

Parameters

g graph

Definition at line 257 of file Coloring.h.

◆ ~Coloring()

template<typename GraphType>

virtual limbo::algorithms::coloring::Coloring< GraphType >::~Coloring ( )

inlinevirtual

destructor

Definition at line 159 of file Coloring.h.

Member Function Documentation

◆ calc_cost()

template<typename GraphType>

Coloring< GraphType >::edge_weight_type limbo::algorithms::coloring::Coloring< GraphType >::calc_cost ( std::vector< int8_t > const & vColor ) const

virtual

compute cost of coloring solutions

Parameters

vColor coloring solutions

Returns: cost with a coloring solution

Definition at line 397 of file Coloring.h.

◆ check_edge_weight()

template<typename GraphType>

void limbo::algorithms::coloring::Coloring< GraphType >::check_edge_weight	(	graph_type const &	g,
		edge_weight_type	lb,
		edge_weight_type	ub ) const

check edge weight within lb and ub

Parameters

g	graph
lb	lower bound
ub	upper bound

Definition at line 422 of file Coloring.h.

◆ color()

template<typename GraphType>

virtual int8_t limbo::algorithms::coloring::Coloring< GraphType >::color ( graph_vertex_type v ) const

inlinevirtual

retrieve coloring solution

Parameters

v vertex

Returns: coloring solution

Definition at line 196 of file Coloring.h.

◆ color_num() [1/3]

template<typename GraphType>

virtual ColorNumType limbo::algorithms::coloring::Coloring< GraphType >::color_num ( ) const

inlinevirtual

Returns: number of colors

Definition at line 173 of file Coloring.h.

◆ color_num() [2/3]

template<typename GraphType>

virtual void limbo::algorithms::coloring::Coloring< GraphType >::color_num ( ColorNumType cn )

inlinevirtual

set number of colors

Parameters

cn	number of colors

Definition at line 168 of file Coloring.h.

◆ color_num() [3/3]

template<typename GraphType>

virtual void limbo::algorithms::coloring::Coloring< GraphType >::color_num ( int8_t cn )

inlinevirtual

set number of colors

Parameters

cn	number of colors

Definition at line 171 of file Coloring.h.

◆ coloring()

template<typename GraphType>

virtual double limbo::algorithms::coloring::Coloring< GraphType >::coloring ( )

protectedpure virtual

Returns: objective value

Implemented in limbo::algorithms::coloring::BacktrackColoring< GraphType >, limbo::algorithms::coloring::ILPColoring< GraphType >, limbo::algorithms::coloring::ILPColoringLemonCbc< GraphType >, limbo::algorithms::coloring::ILPColoringUpdated< GraphType >, limbo::algorithms::coloring::LPColoring< GraphType >, limbo::algorithms::coloring::MISColoring< GraphType >, and limbo::algorithms::coloring::SDPColoringCsdp< GraphType >.

◆ depth_first_search_stitch()

template<typename GraphType>

void limbo::algorithms::coloring::Coloring< GraphType >::depth_first_search_stitch	(	graph_vertex_type	v,
		std::vector< int32_t > &	stitch_relation_set,
		std::vector< bool > &	visited,
		uint32_t &	stitch_edge_num,
		int32_t	stitch_index )

Definition at line 375 of file Coloring.h.

◆ edge_weight()

template<typename GraphType>

virtual edge_weight_type limbo::algorithms::coloring::Coloring< GraphType >::edge_weight ( graph_edge_type const & e ) const

inlinevirtual

get edge weight

Parameters

e edge

Returns: edge weight

Definition at line 202 of file Coloring.h.

◆ has_precolored()

template<typename GraphType>

virtual bool limbo::algorithms::coloring::Coloring< GraphType >::has_precolored ( ) const

inlinevirtual

Returns: true if contain precolored vertices

Definition at line 181 of file Coloring.h.

◆ operator()()

template<typename GraphType>

double limbo::algorithms::coloring::Coloring< GraphType >::operator() ( )

virtual

top API

Returns: objective value

Definition at line 269 of file Coloring.h.

◆ precolor()

template<typename GraphType>

virtual void limbo::algorithms::coloring::Coloring< GraphType >::precolor	(	graph_vertex_type	v,
		int8_t	c )

inlinevirtual

set precolored vertex

Parameters

v	vertex
c	color

Reimplemented in limbo::algorithms::coloring::MISColoring< GraphType >.

Definition at line 178 of file Coloring.h.

◆ print_edge_weight()

template<typename GraphType>

void limbo::algorithms::coloring::Coloring< GraphType >::print_edge_weight ( graph_type const & g ) const

print edge weight

Parameters

g graph

Definition at line 433 of file Coloring.h.

◆ stitch_weight() [1/2]

template<typename GraphType>

virtual double limbo::algorithms::coloring::Coloring< GraphType >::stitch_weight ( ) const

inlinevirtual

Returns: stitch weight

Definition at line 184 of file Coloring.h.

◆ stitch_weight() [2/2]

template<typename GraphType>

virtual void limbo::algorithms::coloring::Coloring< GraphType >::stitch_weight ( double w )

inlinevirtual

set weight of stitch

Parameters

w weight

Definition at line 187 of file Coloring.h.

◆ threads()

template<typename GraphType>

virtual void limbo::algorithms::coloring::Coloring< GraphType >::threads ( int32_t t )

inlinevirtual

set number of threads

Parameters

t	number of threads

Definition at line 191 of file Coloring.h.

◆ write_graph() [1/2]

template<typename GraphType>

virtual void limbo::algorithms::coloring::Coloring< GraphType >::write_graph ( std::string const & filename ) const

virtual

write graph in graphviz format

Parameters

filename output file name

◆ write_graph() [2/2]

template<typename GraphType>

virtual void limbo::algorithms::coloring::Coloring< GraphType >::write_graph	(	std::string const &	filename,
		graph_type const &	g,
		std::vector< int8_t > const &	vColor ) const

virtual

write graph in graphviz format

Parameters

filename	output file name
g	graph
vColor	coloring solutions

Member Data Documentation

◆ m_big_edge_num

template<typename GraphType>

int32_t limbo::algorithms::coloring::Coloring< GraphType >::m_big_edge_num

protected

Definition at line 250 of file Coloring.h.

◆ m_color_num

template<typename GraphType>

ColorNumType limbo::algorithms::coloring::Coloring< GraphType >::m_color_num

protected

number of colors

Definition at line 242 of file Coloring.h.

◆ m_edge_index_vector

template<typename GraphType>

std::vector<int32_t> limbo::algorithms::coloring::Coloring< GraphType >::m_edge_index_vector

protected

Definition at line 253 of file Coloring.h.

◆ m_graph

template<typename GraphType>

graph_type const& limbo::algorithms::coloring::Coloring< GraphType >::m_graph

protected

initial graph

Definition at line 239 of file Coloring.h.

◆ m_has_precolored

template<typename GraphType>

bool limbo::algorithms::coloring::Coloring< GraphType >::m_has_precolored

protected

whether contain precolored vertices

Definition at line 245 of file Coloring.h.

◆ m_stitch_index

template<typename GraphType>

int32_t limbo::algorithms::coloring::Coloring< GraphType >::m_stitch_index

protected

Definition at line 248 of file Coloring.h.

◆ m_stitch_relation_set

template<typename GraphType>

std::vector<int32_t> limbo::algorithms::coloring::Coloring< GraphType >::m_stitch_relation_set

protected

Definition at line 251 of file Coloring.h.

◆ m_stitch_weight

template<typename GraphType>

double limbo::algorithms::coloring::Coloring< GraphType >::m_stitch_weight

protected

stitch weight

Definition at line 243 of file Coloring.h.

◆ m_threads

template<typename GraphType>

int32_t limbo::algorithms::coloring::Coloring< GraphType >::m_threads

protected

control number of threads for ILP solver

Definition at line 244 of file Coloring.h.

◆ m_vColor

template<typename GraphType>

std::vector<int8_t> limbo::algorithms::coloring::Coloring< GraphType >::m_vColor

protected

coloring solutions

Definition at line 240 of file Coloring.h.

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

/home/abuild/rpmbuild/BUILD/limbo-3.5.4-build/limbo-3.5.4/limbo/algorithms/coloring/Coloring.h

Classes

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

Member Typedef Documentation

◆ adjacency_iterator

◆ edge_index_type

◆ edge_iterator_type

◆ edge_weight_type

◆ graph_edge_type

◆ graph_type

◆ graph_vertex_type

◆ vertex_iterator_type

Member Enumeration Documentation

◆ ColorNumType

Constructor & Destructor Documentation

◆ Coloring()

◆ ~Coloring()

Member Function Documentation

◆ calc_cost()

◆ check_edge_weight()

◆ color()

◆ color_num() [1/3]

◆ color_num() [2/3]

◆ color_num() [3/3]

◆ coloring()

◆ depth_first_search_stitch()

◆ edge_weight()

◆ has_precolored()

◆ operator()()

◆ precolor()

◆ print_edge_weight()

◆ stitch_weight() [1/2]

◆ stitch_weight() [2/2]

◆ threads()

◆ write_graph() [1/2]

◆ write_graph() [2/2]

Member Data Documentation

◆ m_big_edge_num

◆ m_color_num

◆ m_edge_index_vector

◆ m_graph

◆ m_has_precolored

◆ m_stitch_index

◆ m_stitch_relation_set

◆ m_stitch_weight

◆ m_threads

◆ m_vColor