#include <MISColoring.h>

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

Public Types

typedef Coloring< GraphType >	base_type
typedef base_type::EdgeHashType	edge_hash_type
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
	MISColoring (graph_type const &g)
virtual	~MISColoring ()
	destructor
virtual void	precolor (graph_vertex_type, int8_t)
void	write_graph_sol (string const &filename, std::vector< int8_t > const &vVertexExcludeMark, std::vector< graph_vertex_type > const &vMISVertex) const
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 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	computeMIS (std::vector< int8_t > const &vVertexExcludeMark, std::vector< graph_vertex_type > &vMISVertex)
	compute maximum independent set, weight is not supported yet

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::MISColoring< GraphType >

MIS based graph coloring, which means iteratively search for the maximum independent set.
Edge weight is used to differentiate conflict edge and stitch edge. Non-negative weight implies conflict edge, while negative weight implies stitch edge.

Template Parameters

GraphType graph type

Definition at line 54 of file MISColoring.h.

Member Typedef Documentation

◆ base_type

template<typename GraphType>

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

Definition at line 58 of file MISColoring.h.

◆ edge_hash_type

template<typename GraphType>

typedef base_type::EdgeHashType limbo::algorithms::coloring::MISColoring< GraphType >::edge_hash_type

Definition at line 66 of file MISColoring.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

◆ MISColoring()

template<typename GraphType>

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

inline

constructor

Parameters

g graph

Definition at line 75 of file MISColoring.h.

◆ ~MISColoring()

template<typename GraphType>

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

inlinevirtual

destructor

Definition at line 79 of file MISColoring.h.

Member Function Documentation

◆ coloring()

template<typename GraphType>

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

inlineprotectedvirtual

kernel coloring algorithm

Returns: objective value

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

Definition at line 140 of file MISColoring.h.

◆ computeMIS()

template<typename GraphType>

double limbo::algorithms::coloring::MISColoring< GraphType >::computeMIS	(	std::vector< int8_t > const &	vVertexExcludeMark,
		std::vector< graph_vertex_type > &	vMISVertex )

inlineprotected

compute maximum independent set, weight is not supported yet

Parameters

vVertexExcludeMark	marked true for vertices to exclude from graph
vMISVertex	store vertices of maximum independent set

Returns: size of maximum independent set

Definition at line 342 of file MISColoring.h.

◆ precolor()

template<typename GraphType>

virtual void limbo::algorithms::coloring::MISColoring< GraphType >::precolor	(	graph_vertex_type	,
		int8_t	)

inlinevirtual

set precolored vertex, not supported
param v vertex param c color

Reimplemented from limbo::algorithms::coloring::Coloring< GraphType >.

Definition at line 84 of file MISColoring.h.

◆ write_graph_sol()

template<typename GraphType>

void limbo::algorithms::coloring::MISColoring< GraphType >::write_graph_sol	(	string const &	filename,
		std::vector< int8_t > const &	vVertexExcludeMark,
		std::vector< graph_vertex_type > const &	vMISVertex ) const

inline

write raw solution of MIS

Parameters

filename	output file name
vVertexExcludeMark	marked true for vertices to exclude from graph
vMISVertex	vertices of maximum independent set

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

Public Types

Public Member Functions

Protected Member Functions

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ base_type

◆ edge_hash_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

◆ MISColoring()

◆ ~MISColoring()

Member Function Documentation

◆ coloring()

◆ computeMIS()

◆ precolor()

◆ write_graph_sol()