#include <BacktrackColoring.h>

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

Public Types

typedef Coloring< GraphType >	base_type
typedef boost::graph_traits< graph_type >::adjacency_iterator	adjacency_iterator_type
typedef boost::graph_traits< graph_type >::edge_descriptor	edge_descriptor
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::property_traits< typenameboost::property_map< graph_type, boost::edge_weight_t >::const_type >::value_type	edge_weight_type
enum	ColorNumType
	number of colors More...
Public Types inherited from limbo::algorithms::coloring::Coloring< GraphType >
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
	BacktrackColoring (graph_type const &g)
virtual	~BacktrackColoring ()
	destructor
Public Member Functions inherited from limbo::algorithms::coloring::Coloring< GraphType >
	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 ()
double	init_coloring (vector< int8_t > &vColor) const
void	coloring_kernel (vector< int8_t > &vBestColor, vector< int8_t > &vColor, double &best_cost, double &cur_cost, graph_vertex_type v, double cost_lb, double cost_ub) const

Additional Inherited Members
Protected Attributes inherited from limbo::algorithms::coloring::Coloring< GraphType >
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::BacktrackColoring< GraphType >

Solve graph coloring with backtracking

Template Parameters

GraphType graph type

Definition at line 28 of file BacktrackColoring.h.

Member Typedef Documentation

◆ adjacency_iterator_type

template<typename GraphType>

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

Definition at line 40 of file BacktrackColoring.h.

◆ base_type

template<typename GraphType>

typedef Coloring<GraphType> limbo::algorithms::coloring::BacktrackColoring< GraphType >::base_type

Definition at line 32 of file BacktrackColoring.h.

◆ edge_descriptor

template<typename GraphType>

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

Definition at line 41 of file BacktrackColoring.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

◆ BacktrackColoring()

template<typename GraphType>

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

inline

constructor

Parameters

g graph

Definition at line 46 of file BacktrackColoring.h.

◆ ~BacktrackColoring()

template<typename GraphType>

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

inlinevirtual

destructor

Definition at line 50 of file BacktrackColoring.h.

Member Function Documentation

◆ coloring()

template<typename GraphType>

double limbo::algorithms::coloring::BacktrackColoring< GraphType >::coloring ( )

protectedvirtual

Returns: objective value

Implements limbo::algorithms::coloring::Coloring< GraphType >.

Definition at line 70 of file BacktrackColoring.h.

◆ coloring_kernel()

template<typename GraphType>

void limbo::algorithms::coloring::BacktrackColoring< GraphType >::coloring_kernel	(	vector< int8_t > &	vBestColor,
		vector< int8_t > &	vColor,
		double &	best_cost,
		double &	cur_cost,
		graph_vertex_type	v,
		double	cost_lb,
		double	cost_ub ) const

protected

kernel function for recursive backtracking

Parameters

vBestColor	best coloring solution assignment
vColor	current coloring solution assignment
best_cost	best cost
cur_cost	current cost
v	current vertex
cost_lb	cost lower bound
cost_ub	cost upper bound

Definition at line 161 of file BacktrackColoring.h.

◆ init_coloring()

template<typename GraphType>

double limbo::algorithms::coloring::BacktrackColoring< GraphType >::init_coloring ( vector< int8_t > & vColor ) const

protected

initial color assignment by greedy approach

Parameters

vColor array to store coloring solution

Returns: cost

Definition at line 138 of file BacktrackColoring.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/BacktrackColoring.h

Public Types

Public Member Functions

Protected Member Functions

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ adjacency_iterator_type

◆ base_type

◆ edge_descriptor

◆ edge_iterator_type

◆ edge_weight_type

◆ graph_edge_type

◆ graph_type

◆ graph_vertex_type

◆ vertex_iterator_type

Member Enumeration Documentation

◆ ColorNumType

Constructor & Destructor Documentation

◆ BacktrackColoring()

◆ ~BacktrackColoring()

Member Function Documentation

◆ coloring()

◆ coloring_kernel()

◆ init_coloring()