boost::dsatur_coloring_helper< VertexListGraph, ColorMap, size_type > Class Template Reference

#include <dsatur_coloring.hpp>

Public Member Functions
	dsatur_coloring_helper (const VertexListGraph &_G, ColorMap &_CM, const size_type _num_node)
size_type	SeqColor ()

Private Types
using	GraphTraits = graph_traits< VertexListGraph >
using	Vertex = typename GraphTraits::vertex_descriptor

Private Attributes
const size_type	num_node
std::vector< dsatur_d_list< size_type > * >	satur_to_list
std::vector< size_type >	vertex_to_satur
std::vector< dsatur_d_list< size_type > * >	vertex_to_iter
std::vector< CustomUnorderedSet< size_type > >	color_set
const VertexListGraph &	G
ColorMap &	CM

Detailed Description

template<typename VertexListGraph, typename ColorMap, typename size_type>
class boost::dsatur_coloring_helper< VertexListGraph, ColorMap, size_type >

Definition at line 133 of file dsatur_coloring.hpp.

Member Typedef Documentation

GraphTraits

template<typename VertexListGraph, typename ColorMap, typename size_type>

using boost::dsatur_coloring_helper< VertexListGraph, ColorMap, size_type >::GraphTraits = graph_traits<VertexListGraph>

private

Definition at line 136 of file dsatur_coloring.hpp.

Vertex

template<typename VertexListGraph, typename ColorMap, typename size_type>

using boost::dsatur_coloring_helper< VertexListGraph, ColorMap, size_type >::Vertex = typename GraphTraits::vertex_descriptor

private

Definition at line 137 of file dsatur_coloring.hpp.

Constructor & Destructor Documentation

dsatur_coloring_helper()

template<typename VertexListGraph, typename ColorMap, typename size_type>

boost::dsatur_coloring_helper< VertexListGraph, ColorMap, size_type >::dsatur_coloring_helper ( const VertexListGraph &  _G, ColorMap &  _CM, const size_type  _num_node  )

inline

Definition at line 147 of file dsatur_coloring.hpp.

References boost::dsatur_d_list< size_type >::next.

Member Function Documentation

SeqColor()

template<typename VertexListGraph, typename ColorMap, typename size_type>

size_type boost::dsatur_coloring_helper< VertexListGraph, ColorMap, size_type >::SeqColor ( )

inline

color each vertex

scan for maximum saturation list

v is vertex to color, remove from list

assign minimum color not adjacent to v

update neighbors saturation

color not previously adjacent to w

mark color in colorset

remove vertex from satur list

increase saturation and check max

add a new empty list

insert w into new list

Definition at line 182 of file dsatur_coloring.hpp.

References boost::dsatur_degree_compare_functor< size_type, VertexListGraph >::G, boost::dsatur_d_list< size_type >::next, and boost::dsatur_d_list< size_type >::prev.

Referenced by boost::dsatur_coloring().

Here is the caller graph for this function:

Field Documentation

CM

template<typename VertexListGraph, typename ColorMap, typename size_type>

ColorMap& boost::dsatur_coloring_helper< VertexListGraph, ColorMap, size_type >::CM

private

Definition at line 144 of file dsatur_coloring.hpp.

color_set

template<typename VertexListGraph, typename ColorMap, typename size_type>

std::vector<CustomUnorderedSet<size_type> > boost::dsatur_coloring_helper< VertexListGraph, ColorMap, size_type >::color_set

private

Definition at line 142 of file dsatur_coloring.hpp.

G

template<typename VertexListGraph, typename ColorMap, typename size_type>

const VertexListGraph& boost::dsatur_coloring_helper< VertexListGraph, ColorMap, size_type >::G

private

Definition at line 143 of file dsatur_coloring.hpp.

num_node

template<typename VertexListGraph, typename ColorMap, typename size_type>

const size_type boost::dsatur_coloring_helper< VertexListGraph, ColorMap, size_type >::num_node

private

Definition at line 138 of file dsatur_coloring.hpp.

satur_to_list

template<typename VertexListGraph, typename ColorMap, typename size_type>

std::vector<dsatur_d_list<size_type>*> boost::dsatur_coloring_helper< VertexListGraph, ColorMap, size_type >::satur_to_list

private

Definition at line 139 of file dsatur_coloring.hpp.

vertex_to_iter

template<typename VertexListGraph, typename ColorMap, typename size_type>

std::vector<dsatur_d_list<size_type>*> boost::dsatur_coloring_helper< VertexListGraph, ColorMap, size_type >::vertex_to_iter

private

Definition at line 141 of file dsatur_coloring.hpp.

vertex_to_satur

template<typename VertexListGraph, typename ColorMap, typename size_type>

std::vector<size_type> boost::dsatur_coloring_helper< VertexListGraph, ColorMap, size_type >::vertex_to_satur

private

Definition at line 140 of file dsatur_coloring.hpp.

---

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

• /workspace/src/algorithms/clique_covering/dsatur_coloring.hpp