#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
	added by Qi Sun, also get the original edge relationships
void	get_CompVertex (std::vector< std::vector< graph_vertex_type > > &CompVertex)
	added by Qi Sun, to get m_mCompVertex
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	set_isVDDGND (std::set< graph_vertex_type > vdd_set)
	construct m_isVDDGND
void	set_isHiden (std::set< graph_vertex_type > is_hidens)
bool	whether_VDDGND (graph_vertex_type id)
	return whether vertex with 'id' is VDDGND
void	merge_subK4 ()
void	hide_small_degree ()
	hide vertices whose degree is no larger than number of colors - 1
void	biconnected_component ()
	find all articulation points and biconnected components
void	mergeVDD (std::set< graph_vertex_type > vdd_set)
	added by Qi Sun, used to merge VDD nodes
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
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
bool	articulation_point (graph_vertex_type v) const
void	get_articulations (std::vector< graph_vertex_type > &art_vec)

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	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
std::vector< bool >	m_isVDDGND
	used in graph simplification, whether it's VDDGND, added by Qi Sun

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 50 of file GraphSimplification.h.

Member Typedef Documentation

◆ adjacency_iterator

template<typename GraphType>

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

Definition at line 58 of file GraphSimplification.h.

◆ edge_iterator

template<typename GraphType>

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

Definition at line 59 of file GraphSimplification.h.

◆ graph_edge_type

template<typename GraphType>

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

Definition at line 56 of file GraphSimplification.h.

◆ graph_type

template<typename GraphType>

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

Definition at line 54 of file GraphSimplification.h.

◆ graph_vertex_type

template<typename GraphType>

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

Definition at line 55 of file GraphSimplification.h.

◆ vertex_iterator

template<typename GraphType>

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

Definition at line 57 of file GraphSimplification.h.

Member Enumeration Documentation

◆ strategy_type

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 72 of file GraphSimplification.h.

◆ vertex_status_type

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 63 of file GraphSimplification.h.

Constructor & Destructor Documentation

◆ GraphSimplification() [1/2]

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 81 of file GraphSimplification.h.

◆ GraphSimplification() [2/2]

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

◆ articulation_point()

template<typename GraphType>

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

inline

Parameters

v vertex

Returns: true if the point is a articulation point

Definition at line 214 of file GraphSimplification.h.

◆ biconnected_component()

template<typename GraphType>

void limbo::algorithms::coloring::GraphSimplification< GraphType >::biconnected_component ( )

find all articulation points and biconnected components

Definition at line 890 of file GraphSimplification.h.

◆ biconnected_component_recursion()

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 1005 of file GraphSimplification.h.

◆ check_max_merge_level()

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 362 of file GraphSimplification.h.

◆ children()

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.

◆ connected_component()

template<typename GraphType>

void limbo::algorithms::coloring::GraphSimplification< GraphType >::connected_component ( )

protected

compute connected components

Definition at line 1094 of file GraphSimplification.h.

◆ connected_conflict()

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 270 of file GraphSimplification.h.

◆ connected_edge()

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 306 of file GraphSimplification.h.

◆ connected_stitch()

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 288 of file GraphSimplification.h.

◆ get_articulations()

template<typename GraphType>

void limbo::algorithms::coloring::GraphSimplification< GraphType >::get_articulations ( std::vector< graph_vertex_type > & art_vec )

inline

Definition at line 218 of file GraphSimplification.h.

◆ get_CompVertex()

template<typename GraphType>

void limbo::algorithms::coloring::GraphSimplification< GraphType >::get_CompVertex ( std::vector< std::vector< graph_vertex_type > > & CompVertex )

added by Qi Sun, to get m_mCompVertex

Definition at line 449 of file GraphSimplification.h.

◆ good()

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 334 of file GraphSimplification.h.

◆ has_precolored()

template<typename GraphType>

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

inlineprotected

Returns: true if there exist precolored vertices

Definition at line 351 of file GraphSimplification.h.

◆ hidden()

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 340 of file GraphSimplification.h.

◆ hidden_vertices()

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.

◆ hide_small_degree()

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 816 of file GraphSimplification.h.

◆ max_merge_level()

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 153 of file GraphSimplification.h.

◆ merge_subK4()

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 707 of file GraphSimplification.h.

◆ merged()

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 322 of file GraphSimplification.h.

◆ mergeVDD()

template<typename GraphType>

void limbo::algorithms::coloring::GraphSimplification< GraphType >::mergeVDD ( std::set< graph_vertex_type > vdd_set )

added by Qi Sun, used to merge VDD nodes

Definition at line 602 of file GraphSimplification.h.

◆ num_component()

template<typename GraphType>

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

inline

added by Qi Sun, also get the original edge relationships

Returns: number of components

Definition at line 146 of file GraphSimplification.h.

◆ parent() [1/2]

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 248 of file GraphSimplification.h.

◆ parent() [2/2]

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 261 of file GraphSimplification.h.

◆ parents()

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.

◆ precolor()

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.

◆ precolored()

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 346 of file GraphSimplification.h.

◆ recover()

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 668 of file GraphSimplification.h.

◆ recover_biconnected_component()

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

Parameters

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

Definition at line 1229 of file GraphSimplification.h.

◆ recover_hide_small_degree()

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 1346 of file GraphSimplification.h.

◆ recover_merge_subK4()

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 1208 of file GraphSimplification.h.

◆ set_isHiden()

template<typename GraphType>

void limbo::algorithms::coloring::GraphSimplification< GraphType >::set_isHiden ( std::set< graph_vertex_type > is_hidens )

Definition at line 595 of file GraphSimplification.h.

◆ set_isVDDGND()

template<typename GraphType>

void limbo::algorithms::coloring::GraphSimplification< GraphType >::set_isVDDGND ( std::set< graph_vertex_type > vdd_set )

construct m_isVDDGND

Definition at line 588 of file GraphSimplification.h.

◆ simplified_graph()

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 391 of file GraphSimplification.h.

◆ simplified_graph_component()

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 464 of file GraphSimplification.h.

◆ simplify()

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 623 of file GraphSimplification.h.

◆ status()

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.

◆ whether_VDDGND()

template<typename GraphType>

bool limbo::algorithms::coloring::GraphSimplification< GraphType >::whether_VDDGND ( graph_vertex_type id )

return whether vertex with 'id' is VDDGND

Definition at line 458 of file GraphSimplification.h.

◆ write_graph_dot()

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 1403 of file GraphSimplification.h.

◆ write_simplified_graph_dot()

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 1465 of file GraphSimplification.h.

Member Data Documentation

◆ m_color_num

template<typename GraphType>

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

protected

number of colors

Definition at line 367 of file GraphSimplification.h.

◆ m_graph

template<typename GraphType>

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

protected

original graph

Definition at line 366 of file GraphSimplification.h.

◆ m_isVDDGND

template<typename GraphType>

std::vector<bool> limbo::algorithms::coloring::GraphSimplification< GraphType >::m_isVDDGND

protected

used in graph simplification, whether it's VDDGND, added by Qi Sun

Definition at line 385 of file GraphSimplification.h.

◆ m_level

template<typename GraphType>

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

protected

simplification level

Definition at line 368 of file GraphSimplification.h.

◆ m_mArtiPoint

template<typename GraphType>

std::map<graph_vertex_type, std::set<uint32_t> > limbo::algorithms::coloring::GraphSimplification< GraphType >::m_mArtiPoint

protected

map of (vertex of articulation point, set of components split by the vertex)

Definition at line 381 of file GraphSimplification.h.

◆ m_max_merge_level

template<typename GraphType>

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

protected

in MERGE_SUBK4, any merge that results in the children number of a vertex larger than m_max_merge_level is disallowed

Definition at line 369 of file GraphSimplification.h.

◆ m_mCompVertex

template<typename GraphType>

std::vector<std::vector<graph_vertex_type> > limbo::algorithms::coloring::GraphSimplification< GraphType >::m_mCompVertex

protected

group vertices by components

Definition at line 377 of file GraphSimplification.h.

◆ m_vChildren

template<typename GraphType>

std::vector<std::vector<graph_vertex_type> > limbo::algorithms::coloring::GraphSimplification< GraphType >::m_vChildren

protected

children verices of current vertex, a vertex is the child of itself if it is not merged

Definition at line 373 of file GraphSimplification.h.

◆ m_vHiddenVertex

template<typename GraphType>

std::stack<graph_vertex_type> limbo::algorithms::coloring::GraphSimplification< GraphType >::m_vHiddenVertex

protected

a std::stack that keeps a reverse order of vertices hidden, useful for color recovery

Definition at line 375 of file GraphSimplification.h.

◆ m_vParent

template<typename GraphType>

std::vector<graph_vertex_type> limbo::algorithms::coloring::GraphSimplification< GraphType >::m_vParent

protected

parent vertex of current vertex

Definition at line 372 of file GraphSimplification.h.

◆ m_vPrecolor

template<typename GraphType>

std::vector<int8_t> limbo::algorithms::coloring::GraphSimplification< GraphType >::m_vPrecolor

protected

precolor information, if uncolored, std::set to -1

Definition at line 383 of file GraphSimplification.h.

◆ m_vStatus

template<typename GraphType>

std::vector<vertex_status_type> limbo::algorithms::coloring::GraphSimplification< GraphType >::m_vStatus

protected

status of each vertex

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

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

Member Typedef Documentation

◆ adjacency_iterator

◆ edge_iterator

◆ graph_edge_type

◆ graph_type

◆ graph_vertex_type

◆ vertex_iterator

Member Enumeration Documentation

◆ strategy_type

◆ vertex_status_type

Constructor & Destructor Documentation

◆ GraphSimplification() [1/2]

◆ GraphSimplification() [2/2]

Member Function Documentation

◆ articulation_point()

◆ biconnected_component()

◆ biconnected_component_recursion()

◆ check_max_merge_level()

◆ children()

◆ connected_component()

◆ connected_conflict()

◆ connected_edge()

◆ connected_stitch()

◆ get_articulations()

◆ get_CompVertex()

◆ good()

◆ has_precolored()

◆ hidden()

◆ hidden_vertices()

◆ hide_small_degree()

◆ max_merge_level()

◆ merge_subK4()

◆ merged()

◆ mergeVDD()

◆ num_component()

◆ parent() [1/2]

◆ parent() [2/2]

◆ parents()

◆ precolor()

◆ precolored()

◆ recover()

◆ recover_biconnected_component()

◆ recover_hide_small_degree()

◆ recover_merge_subK4()

◆ set_isHiden()

◆ set_isVDDGND()

◆ simplified_graph()

◆ simplified_graph_component()

◆ simplify()

◆ status()

◆ whether_VDDGND()

◆ write_graph_dot()

◆ write_simplified_graph_dot()

Member Data Documentation

◆ m_color_num

◆ m_graph

◆ m_isVDDGND

◆ m_level

◆ m_mArtiPoint

◆ m_max_merge_level

◆ m_mCompVertex

◆ m_vChildren

◆ m_vHiddenVertex

◆ m_vParent

◆ m_vPrecolor

◆ m_vStatus