Limbo
|
#include <MISColoring.h>
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 < typename boost::property_map < graph_type, boost::edge_weight_t > ::const_type >::value_type | edge_weight_type |
enum | ColorNumType |
number of colors | |
Public Types inherited from limbo::algorithms::coloring::Coloring< GraphType > | |
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 | |
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 |
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 More... | |
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 | |
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.
GraphType | graph type |
Definition at line 54 of file MISColoring.h.
|
inline |
|
inlineprotectedvirtual |
kernel coloring algorithm
Implements limbo::algorithms::coloring::Coloring< GraphType >.
Definition at line 140 of file MISColoring.h.
|
inlineprotected |
compute maximum independent set, weight is not supported yet
vVertexExcludeMark | marked true for vertices to exclude from graph |
vMISVertex | store vertices of maximum independent set |
Definition at line 342 of file MISColoring.h.
|
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.
|
inline |
write raw solution of MIS
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.