Limbo
|
#include <Coloring.h>
Classes | |
struct | EdgeHashType |
hasher class for graph_edge_type More... | |
Public Types | |
enum | ColorNumType { THREE = 3, FOUR = 4 } |
number of colors | |
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 < typename boost::property_map < graph_type, boost::edge_weight_t > ::const_type >::value_type | edge_weight_type |
typedef boost::property_traits < typename boost::property_map < graph_type, boost::edge_index_t > ::const_type >::value_type | edge_index_type |
Public Member Functions | |
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 |
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 ()=0 |
Protected Attributes | |
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 | |
Base class for all coloring algorithms. All coloring algorithms support 3 and 4 colors.
GraphType | graph type |
Definition at line 114 of file Coloring.h.
limbo::algorithms::coloring::Coloring< GraphType >::Coloring | ( | graph_type const & | g | ) |
|
virtual |
compute cost of coloring solutions
vColor | coloring solutions |
Definition at line 279 of file Coloring.h.
void limbo::algorithms::coloring::Coloring< GraphType >::check_edge_weight | ( | graph_type const & | g, |
edge_weight_type | lb, | ||
edge_weight_type | ub | ||
) | const |
check edge weight within lb and ub
g | graph |
lb | lower bound |
ub | upper bound |
Definition at line 300 of file Coloring.h.
|
inlinevirtual |
retrieve coloring solution
v | vertex |
Definition at line 193 of file Coloring.h.
|
inlinevirtual |
|
inlinevirtual |
|
inlinevirtual |
Definition at line 170 of file Coloring.h.
|
protectedpure virtual |
Implemented in limbo::algorithms::coloring::LPColoring< GraphType >, limbo::algorithms::coloring::MISColoring< GraphType >, limbo::algorithms::coloring::SDPColoringCsdp< GraphType >, limbo::algorithms::coloring::ILPColoringLemonCbc< GraphType >, limbo::algorithms::coloring::ILPColoring< GraphType >, and limbo::algorithms::coloring::BacktrackColoring< GraphType >.
|
inlinevirtual |
|
inlinevirtual |
Definition at line 178 of file Coloring.h.
|
virtual |
|
inlinevirtual |
set precolored vertex
v | vertex |
c | color |
Reimplemented in limbo::algorithms::coloring::MISColoring< GraphType >.
Definition at line 175 of file Coloring.h.
void limbo::algorithms::coloring::Coloring< GraphType >::print_edge_weight | ( | graph_type const & | g | ) | const |
|
inlinevirtual |
Definition at line 181 of file Coloring.h.
|
inlinevirtual |
|
inlinevirtual |
|
virtual |
write graph in graphviz format
filename | output file name |
|
virtual |
write graph in graphviz format
filename | output file name |
g | graph |
vColor | coloring solutions |