limbo::algorithms::coloring::GraphSimplification< GraphType > Class Template Reference

#include <GraphSimplification.h>

Public Types
enum	vertex_status_type { GOOD, HIDDEN, MERGED }
	status of vertex. More...
enum	strategy_type { NONE = 0, HIDE_SMALL_DEGREE = 1, MERGE_SUBK4 = 2, BICONNECTED_COMPONENT = 4 }
	simplification strategies available. These strategies are order-sensitive. It is recommended to call simplify(), e.g. simplify(HIDE_SMALL_DEGREE | BICONNECTED_COMPONENT) 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
typedef boost::graph_traits < graph_type > ::adjacency_iterator	adjacency_iterator
typedef boost::graph_traits < graph_type >::edge_iterator	edge_iterator

Public Member Functions
	GraphSimplification (graph_type const &g, uint32_t color_num)
	GraphSimplification (GraphSimplification const &rhs)
template<typename Iterator >
void	precolor (Iterator first, Iterator last)
std::vector < vertex_status_type > const &	status () const
std::vector< graph_vertex_type > const &	parents () const
std::vector< std::vector < graph_vertex_type > > const &	children () const
std::stack< graph_vertex_type > const &	hidden_vertices () const
std::pair< graph_type, std::map< graph_vertex_type, graph_vertex_type > >	simplified_graph () const
bool	simplified_graph_component (uint32_t comp_id, graph_type &sg, std::vector< graph_vertex_type > &vSimpl2Orig) const
uint32_t	num_component () const
void	max_merge_level (int32_t l)
void	simplify (uint32_t level)
void	recover (std::vector< int8_t > &vColorFlat, std::vector< std::vector< int8_t > > &mColor, std::vector< std::vector< graph_vertex_type > > const &mSimpl2Orig) const
void	merge_subK4 ()
void	hide_small_degree ()
	hide vertices whose degree is no larger than number of colors - 1 More...
void	biconnected_component ()
	find all articulation points and biconnected components
void	recover_merge_subK4 (std::vector< int8_t > &vColor) const
void	recover_biconnected_component (std::vector< std::vector< int8_t > > &mColor, std::vector< std::vector< graph_vertex_type > > const &mSimpl2Orig) const
	recover color for biconnected components More...
void	recover_hide_small_degree (std::vector< int8_t > &vColor)
void	write_graph_dot (std::string const &filename) const
void	write_simplified_graph_dot (std::string const &filename) const

Protected Member Functions
void	biconnected_component_recursion (graph_vertex_type v, std::deque< bool > &vVisited, std::vector< uint32_t > &vDisc, std::vector< uint32_t > &vLow, std::vector< graph_vertex_type > &vParent, uint32_t &visit_time, std::stack< std::pair< graph_vertex_type, graph_vertex_type > > &vEdge, std::list< std::pair< graph_vertex_type, std::set< graph_vertex_type > > > &mCompVertex) const
void	connected_component ()
	compute connected components
graph_vertex_type	parent (graph_vertex_type v) const
graph_vertex_type	parent (uint32_t v, std::vector< uint32_t > const &vParent) const
bool	connected_conflict (graph_vertex_type v1, graph_vertex_type v2) const
bool	connected_stitch (graph_vertex_type v1, graph_vertex_type v2) const
std::pair< graph_edge_type, bool >	connected_edge (graph_vertex_type v1, graph_vertex_type v2) const
bool	merged (graph_vertex_type v1) const
bool	good (graph_vertex_type v1) const
bool	hidden (graph_vertex_type v1) const
bool	precolored (graph_vertex_type v1) const
bool	articulation_point (graph_vertex_type v) const
bool	has_precolored () const
bool	check_max_merge_level (uint32_t l) const

Protected Attributes
graph_type const &	m_graph
	original graph
uint32_t	m_color_num
	number of colors
uint32_t	m_level
	simplification level
uint32_t	m_max_merge_level
	in MERGE_SUBK4, any merge that results in the children number of a vertex larger than m_max_merge_level is disallowed
std::vector< vertex_status_type >	m_vStatus
	status of each vertex
std::vector< graph_vertex_type >	m_vParent
	parent vertex of current vertex
std::vector< std::vector < graph_vertex_type > >	m_vChildren
	children verices of current vertex, a vertex is the child of itself if it is not merged
std::stack< graph_vertex_type >	m_vHiddenVertex
	a std::stack that keeps a reverse order of vertices hidden, useful for color recovery
std::vector< std::vector < graph_vertex_type > >	m_mCompVertex
	group vertices by components
std::map< graph_vertex_type, std::set< uint32_t > >	m_mArtiPoint
	map of (vertex of articulation point, set of components split by the vertex)
std::vector< int8_t >	m_vPrecolor
	precolor information, if uncolored, std::set to -1

Detailed Description

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

Various graph simplification techniques for graph coloring.

Template Parameters

GraphType

graph type

Definition at line 51 of file GraphSimplification.h.

Member Enumeration Documentation

template<typename GraphType>

enum limbo::algorithms::coloring::GraphSimplification::strategy_type

simplification strategies available. These strategies are order-sensitive. It is recommended to call simplify(), e.g. simplify(HIDE_SMALL_DEGREE | BICONNECTED_COMPONENT)

Enumerator
NONE	no simplification
HIDE_SMALL_DEGREE	hide vertices whose degree is smaller than number of colors available
MERGE_SUBK4	merge 4-clique structures, no longer optimal
BICONNECTED_COMPONENT	divide graph by biconnected components

Definition at line 73 of file GraphSimplification.h.

template<typename GraphType>

enum limbo::algorithms::coloring::GraphSimplification::vertex_status_type

status of vertex.

Enumerator
GOOD	still in graph
HIDDEN	vertex is hidden by simplification
MERGED	vertex is merged to other vertex

Definition at line 64 of file GraphSimplification.h.

Constructor & Destructor Documentation

template<typename GraphType>

limbo::algorithms::coloring::GraphSimplification< GraphType >::GraphSimplification ( graph_type const &  g, uint32_t  color_num  )

inline

constructor

Parameters

g	graph
color_num	number of colors

Definition at line 82 of file GraphSimplification.h.

template<typename GraphType>

limbo::algorithms::coloring::GraphSimplification< GraphType >::GraphSimplification

(

GraphSimplification< GraphType > const &

rhs

)

copy constructor is not allowed

Parameters

rhs	a GraphSimplification object

Member Function Documentation

template<typename GraphType>

bool limbo::algorithms::coloring::GraphSimplification< GraphType >::articulation_point ( graph_vertex_type  v ) const

inlineprotected

Parameters

v

vertex

Returns

true if the point is a articulation point

Definition at line 320 of file GraphSimplification.h.

template<typename GraphType >

void limbo::algorithms::coloring::GraphSimplification< GraphType >::biconnected_component_recursion ( graph_vertex_type  v, std::deque< bool > &  vVisited, std::vector< uint32_t > &  vDisc, std::vector< uint32_t > &  vLow, std::vector< graph_vertex_type > &  vParent, uint32_t &  visit_time, std::stack< std::pair< graph_vertex_type, graph_vertex_type > > &  vEdge, std::list< std::pair< graph_vertex_type, std::set< graph_vertex_type > > > &  mCompVertex  ) const

protected

recursive implementation of computing biconnected components

Parameters

v	current vertex
vVisited	an array records whether a vertex has been visited
vDisc	discovery time of vertices
vLow	low values of vertices
vParent	parents of vertices
visit_time	records current visiting time
vEdge	a stack of edges for DFS
mCompVertex	vertices arranged by independent components

Definition at line 832 of file GraphSimplification.h.

template<typename GraphType>

bool limbo::algorithms::coloring::GraphSimplification< GraphType >::check_max_merge_level ( uint32_t  l ) const

inlineprotected

Parameters

l	merge level

Returns

true if the vertex satisfies maximum merge level constraint

Definition at line 336 of file GraphSimplification.h.

template<typename GraphType>

std::vector<std::vector<graph_vertex_type> > const& limbo::algorithms::coloring::GraphSimplification< GraphType >::children ( ) const

inline

Returns

children map of vertices

Definition at line 129 of file GraphSimplification.h.

template<typename GraphType>

bool limbo::algorithms::coloring::GraphSimplification< GraphType >::connected_conflict ( graph_vertex_type  v1, graph_vertex_type  v2  ) const

inlineprotected

Parameters

v1	vertex
v2	vertex

Returns

true if two vertices (parents) are connected by conflict edges

Definition at line 238 of file GraphSimplification.h.

template<typename GraphType>

std::pair<graph_edge_type, bool> limbo::algorithms::coloring::GraphSimplification< GraphType >::connected_edge ( graph_vertex_type  v1, graph_vertex_type  v2  ) const

inlineprotected

Parameters

v1	vertex
v2	vertex

Returns

the edge of two vertices (parents)

Definition at line 274 of file GraphSimplification.h.

template<typename GraphType>

bool limbo::algorithms::coloring::GraphSimplification< GraphType >::connected_stitch ( graph_vertex_type  v1, graph_vertex_type  v2  ) const

inlineprotected

Parameters

v1	vertex
v2	vertex

Returns

true if two vertices (parents) are connected by stitch edges

Definition at line 256 of file GraphSimplification.h.

template<typename GraphType>

bool limbo::algorithms::coloring::GraphSimplification< GraphType >::good ( graph_vertex_type  v1 ) const

inlineprotected

Parameters

v1

vertex

Returns

true if current vertex is still in graph

Definition at line 302 of file GraphSimplification.h.

template<typename GraphType>

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

inlineprotected

Returns

true if there exist precolored vertices

Definition at line 325 of file GraphSimplification.h.

template<typename GraphType>

bool limbo::algorithms::coloring::GraphSimplification< GraphType >::hidden ( graph_vertex_type  v1 ) const

inlineprotected

Parameters

v1

vertex

Returns

true if current vertex is hidden

Definition at line 308 of file GraphSimplification.h.

template<typename GraphType>

std::stack<graph_vertex_type> const& limbo::algorithms::coloring::GraphSimplification< GraphType >::hidden_vertices ( ) const

inline

Returns

hidden vertex array of vertices

Definition at line 131 of file GraphSimplification.h.

template<typename GraphType >

void limbo::algorithms::coloring::GraphSimplification< GraphType >::hide_small_degree

(

)

hide vertices whose degree is no larger than number of colors - 1

hide vertices whose degree is no larger than color_num-1

Definition at line 678 of file GraphSimplification.h.

template<typename GraphType>

void limbo::algorithms::coloring::GraphSimplification< GraphType >::max_merge_level ( int32_t  l )

inline

set maximum merge level

Parameters

l

level

Definition at line 146 of file GraphSimplification.h.

template<typename GraphType >

void limbo::algorithms::coloring::GraphSimplification< GraphType >::merge_subK4

(

)

For a structure of K4 with one fewer edge, suppose we have 4 vertices 1, 2, 3, 4, edges 1–2, 1–3, 2–3, 2–4, 3–4. Vertex 4 is merged to 1. This strategy only works for 3-coloring. It cannot guarantee minimal conflicts, but it can be used in a native conflict checker.

for a structure of K4 with one fewer edge suppose we have 4 vertices 1, 2, 3, 4 1–2, 1–3, 2–3, 2–4, 3–4, vertex 4 is merged to 1 this strategy only works for 3-coloring it cannot guarantee minimal conflicts but it can be used in a native conflict checker

Definition at line 569 of file GraphSimplification.h.

template<typename GraphType>

bool limbo::algorithms::coloring::GraphSimplification< GraphType >::merged ( graph_vertex_type  v1 ) const

inlineprotected

Parameters

v1

vertex

Returns

true if current vertex is merged

Definition at line 290 of file GraphSimplification.h.

template<typename GraphType>

uint32_t limbo::algorithms::coloring::GraphSimplification< GraphType >::num_component ( ) const

inline

Returns

number of components

Definition at line 142 of file GraphSimplification.h.

template<typename GraphType>

graph_vertex_type limbo::algorithms::coloring::GraphSimplification< GraphType >::parent ( graph_vertex_type  v ) const

inlineprotected

Parameters

v

vertex

Returns

the root parent i.e. the vertex that is not merged

Definition at line 216 of file GraphSimplification.h.

template<typename GraphType>

graph_vertex_type limbo::algorithms::coloring::GraphSimplification< GraphType >::parent ( uint32_t  v, std::vector< uint32_t > const &  vParent  ) const

inlineprotected

Parameters

v	vertex
vParent	parent array of vertices

Returns

the root parent generalized version

Definition at line 229 of file GraphSimplification.h.

template<typename GraphType>

std::vector<graph_vertex_type> const& limbo::algorithms::coloring::GraphSimplification< GraphType >::parents ( ) const

inline

Returns

parent array of vertices

Definition at line 127 of file GraphSimplification.h.

template<typename GraphType>

template<typename Iterator >

void limbo::algorithms::coloring::GraphSimplification< GraphType >::precolor ( Iterator  first, Iterator  last  )

inline

set precolored vertices

Template Parameters

Iterator

iterator type

Parameters

first,last

begin and end of the precolored vertex array

Definition at line 116 of file GraphSimplification.h.

template<typename GraphType>

bool limbo::algorithms::coloring::GraphSimplification< GraphType >::precolored ( graph_vertex_type  v1 ) const

inlineprotected

Parameters

v1

vertex

Returns

true if current vertex is precolored

Definition at line 314 of file GraphSimplification.h.

template<typename GraphType >

void limbo::algorithms::coloring::GraphSimplification< GraphType >::recover	(	std::vector< int8_t > &	vColorFlat,
		std::vector< std::vector< int8_t > > &	mColor,
		std::vector< std::vector< graph_vertex_type > > const &	mSimpl2Orig
	)		const

API to recover coloring solutions from color assignment of simplified graph

Parameters

vColorFlat	flatten coloring solutions for original graph
mColor	coloring solutions arranged by components
mSimpl2Orig	mapping from simplified graph components to original graph

Definition at line 530 of file GraphSimplification.h.

template<typename GraphType >

void limbo::algorithms::coloring::GraphSimplification< GraphType >::recover_biconnected_component	(	std::vector< std::vector< int8_t > > &	mColor,
		std::vector< std::vector< graph_vertex_type > > const &	mSimpl2Orig
	)		const

recover color for biconnected components

recover color for biconnected components

Parameters

mColor	coloring solutions arranged by components
mSimpl2Orig	mapping from simplified graph components to original graph

Definition at line 1054 of file GraphSimplification.h.

template<typename GraphType >

void limbo::algorithms::coloring::GraphSimplification< GraphType >::recover_hide_small_degree

(

std::vector< int8_t > &

vColor

)

recover color for hidden vertices need to be called manually, no density balance considered this function is mutable because it pops out elements in m_vHiddenVertex

Parameters

vColor

coloring solutions, it must be partially assigned colors except simplified vertices

Definition at line 1163 of file GraphSimplification.h.

template<typename GraphType >

void limbo::algorithms::coloring::GraphSimplification< GraphType >::recover_merge_subK4

(

std::vector< int8_t > &

vColor

)

const

recover merged vertices

Parameters

vColor

must be partially assigned colors except simplified vertices

Definition at line 1033 of file GraphSimplification.h.

template<typename GraphType >

std::pair< typename GraphSimplification< GraphType >::graph_type, std::map< typename GraphSimplification< GraphType >::graph_vertex_type, typename GraphSimplification< GraphType >::graph_vertex_type > > limbo::algorithms::coloring::GraphSimplification< GraphType >::simplified_graph

(

)

const

Returns

simplified graph and a std::map from merged graph vertices to original graph vertices

Definition at line 363 of file GraphSimplification.h.

template<typename GraphType>

bool limbo::algorithms::coloring::GraphSimplification< GraphType >::simplified_graph_component	(	uint32_t	comp_id,
		graph_type &	sg,
		std::vector< graph_vertex_type > &	vSimpl2Orig
	)		const

extract a component from simplified graph

Parameters

comp_id	component id
sg	component of simplified graph
vSimpl2Orig	mapping from simplified graph to original graph

Returns

true if succeed

Definition at line 422 of file GraphSimplification.h.

template<typename GraphType >

void limbo::algorithms::coloring::GraphSimplification< GraphType >::simplify

(

uint32_t

level

)

API to run the simplification algorithm

Parameters

level

simplification level, can be combination of items in limbo::algorithms::coloring::GraphSimplification::strategy_type

Definition at line 497 of file GraphSimplification.h.

template<typename GraphType>

std::vector<vertex_status_type> const& limbo::algorithms::coloring::GraphSimplification< GraphType >::status ( ) const

inline

Returns

status array of vertices

Definition at line 125 of file GraphSimplification.h.

template<typename GraphType >

void limbo::algorithms::coloring::GraphSimplification< GraphType >::write_graph_dot

(

std::string const &

filename

)

const

write graph in graphviz format

Parameters

filename

output file name

Definition at line 1194 of file GraphSimplification.h.

template<typename GraphType >

void limbo::algorithms::coloring::GraphSimplification< GraphType >::write_simplified_graph_dot

(

std::string const &

filename

)

const

write simplified graph in graphviz format

Parameters

filename

output file name

Definition at line 1256 of file GraphSimplification.h.

---

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

• /Users/yibolin/Documents/Projects/Limbo/limbo/algorithms/coloring/GraphSimplification.h