8 #ifndef LIMBO_ALGORITHMS_COLORING_COLORING
9 #define LIMBO_ALGORITHMS_COLORING_COLORING
13 #include <boost/cstdint.hpp>
14 #include <boost/functional/hash.hpp>
15 #include <boost/graph/graph_concepts.hpp>
16 #include <boost/graph/adjacency_list.hpp>
17 #include <boost/property_map/property_map.hpp>
31 using boost::uint32_t;
39 template <
typename GraphType>
43 typedef GraphType graph_type;
45 typedef typename base_type::vertex_descriptor vertex_descriptor;
58 std::string
label(vertex_descriptor v)
const
60 std::ostringstream oss;
61 oss << v <<
":" << (int32_t)vColor[v];
68 template <
typename GraphType>
72 typedef GraphType graph_type;
74 typedef typename base_type::edge_descriptor edge_descriptor;
75 typedef typename base_type::edge_weight_type edge_weight_type;
76 typedef typename boost::graph_traits<graph_type>::vertex_descriptor vertex_descriptor;
89 edge_weight_type
label(edge_descriptor e)
const {
return boost::get(boost::edge_weight, this->
g, e);}
93 std::string
color(edge_descriptor e)
const
95 vertex_descriptor s = boost::source(e, this->
g);
96 vertex_descriptor t = boost::target(e, this->
g);
97 edge_weight_type w = boost::get(boost::edge_weight, this->
g, e);
98 bool conflict_flag = (vColor[s] >= 0 && vColor[s] == vColor[t]);
99 if (w >= 0 && conflict_flag)
106 std::string
style(edge_descriptor e)
const {
return (boost::get(boost::edge_weight, this->
g, e) >= 0)?
"solid" :
"dashed";}
113 template <
typename GraphType>
118 typedef GraphType graph_type;
119 typedef typename boost::graph_traits<graph_type>::vertex_descriptor graph_vertex_type;
120 typedef typename boost::graph_traits<graph_type>::edge_descriptor graph_edge_type;
121 typedef typename boost::graph_traits<graph_type>::vertex_iterator vertex_iterator_type;
122 typedef typename boost::graph_traits<graph_type>::edge_iterator edge_iterator_type;
124 typedef typename boost::property_traits<typename boost::property_map<graph_type, boost::edge_weight_t>::const_type>::value_type edge_weight_type;
128 typedef typename boost::property_traits<typename boost::property_map<graph_type, boost::edge_index_t>::const_type>::value_type edge_index_type;
138 struct EdgeHashType : std::unary_function<graph_edge_type, std::size_t>
144 std::size_t seed = 0;
145 boost::hash_combine(seed, e.m_source);
146 boost::hash_combine(seed, e.m_target);
199 inline virtual edge_weight_type
edge_weight(graph_edge_type
const& e)
const {
return boost::get(boost::edge_weight,
m_graph, e);}
204 virtual edge_weight_type
calc_cost(std::vector<int8_t>
const& vColor)
const;
210 void check_edge_weight(graph_type
const& g, edge_weight_type lb, edge_weight_type ub)
const;
219 virtual void write_graph(std::string
const& filename)
const;
224 virtual void write_graph(std::string
const& filename, graph_type
const& g, std::vector<int8_t>
const& vColor)
const;
238 template <
typename GraphType>
241 , m_vColor(
boost::num_vertices(g), -1)
243 , m_stitch_weight(0.1)
244 , m_threads(std::numeric_limits<int32_t>::
max())
245 , m_has_precolored(false)
248 template <
typename GraphType>
251 if (boost::num_vertices(m_graph) <= color_num())
254 bool unusedColors[4] = {
true,
true,
true,
true};
255 if (color_num() == THREE)
256 unusedColors[3] =
false;
257 for (int32_t i = 0, ie = m_vColor.size(); i != ie; ++i)
261 for (int8_t c = 0; c != 4; ++c)
269 assert(m_vColor[i] >= 0);
270 unusedColors[m_vColor[i]] =
false;
272 return calc_cost(m_vColor);
275 return this->coloring();
278 template <
typename GraphType>
281 assert(vColor.size() == boost::num_vertices(this->m_graph));
283 edge_iterator_type ei, eie;
284 for (boost::tie(ei, eie) = boost::edges(m_graph); ei != eie; ++ei)
286 edge_weight_type w = boost::get(boost::edge_weight, m_graph, *ei);
287 graph_vertex_type s = boost::source(*ei, m_graph);
288 graph_vertex_type t = boost::target(*ei, m_graph);
292 cost += (vColor[s] == vColor[t])*w;
294 cost += (vColor[s] != vColor[t])*w;
299 template <
typename GraphType>
300 void Coloring<GraphType>::check_edge_weight(
typename Coloring<GraphType>::graph_type
const& g,
typename Coloring<GraphType>::edge_weight_type lb,
typename Coloring<GraphType>::edge_weight_type ub)
const
302 edge_iterator_type ei, eie;
303 for (boost::tie(ei, eie) = boost::edges(g); ei != eie; ++ei)
305 edge_weight_type w = boost::get(boost::edge_weight, m_graph, *ei);
306 assert_msg(w >= lb && w <= ub,
"edge weight out of range: " << w);
310 template <
typename GraphType>
313 edge_iterator_type ei, eie;
314 for (boost::tie(ei, eie) = boost::edges(g); ei != eie; ++ei)
316 edge_weight_type w = boost::get(boost::edge_weight, m_graph, *ei);
317 std::cout << w <<
" ";
324 template <
typename GraphType>
330 template <
typename GraphType>
333 std::ofstream out ((filename+
".gv").c_str());
334 la::write_graph(out, g, ColoringVertexLabelWriter<graph_type>(g, vColor), ColoringEdgeLabelWriter<graph_type>(g, vColor));
hasher class for graph_edge_type
Coloring(graph_type const &g)
virtual edge_weight_type calc_cost(std::vector< int8_t > const &vColor) const
ColorNumType
number of colors
void write_graph(std::ofstream &out, GraphType const &g, VertexLabelType const &vl, EdgeLabelType const &el)
write graph to graphviz format and convert to pdf. Although Boost.Graph has write_graphviz component...
default EdgeLabelWriter for write_graph
virtual void precolor(graph_vertex_type v, int8_t c)
int32_t m_threads
control number of threads for ILP solver
virtual double stitch_weight() const
some graph utilities such as compute complement graph and graphviz writer.
ColoringVertexLabelWriter(graph_type const &g, std::vector< int8_t > const &vc)
virtual ~Coloring()
destructor
virtual edge_weight_type edge_weight(graph_edge_type const &e) const
virtual bool has_precolored() const
virtual double operator()()
bool m_has_precolored
whether contain precolored vertices
graph_type const & g
bind graph object
void print_edge_weight(graph_type const &g) const
virtual void threads(int32_t t)
virtual double coloring()=0
std::vector< int8_t > m_vColor
coloring solutions
virtual void color_num(int8_t cn)
std::vector< int8_t > const & vColor
coloring solutions
std::iterator_traits< Iterator >::value_type max(Iterator first, Iterator last)
get max of an array
graph_type const & m_graph
initial graph
std::string label(vertex_descriptor v) const
graph_type const & g
bind graph object
virtual void write_graph(std::string const &filename) const
std::size_t operator()(graph_edge_type const &e) const
virtual ColorNumType color_num() const
namespace for Limbo.algorithms
void check_edge_weight(graph_type const &g, edge_weight_type lb, edge_weight_type ub) const
virtual void color_num(ColorNumType cn)
ColorNumType m_color_num
number of colors
std::string style(edge_descriptor e) const
default VertexLabelWriter for write_graph
std::vector< int8_t > const & vColor
coloring solutions
edge_weight_type label(edge_descriptor e) const
ColoringEdgeLabelWriter(graph_type const &g, std::vector< int8_t > const &vc)
virtual int8_t color(graph_vertex_type v) const
std::string color(edge_descriptor e) const
virtual void stitch_weight(double w)
double m_stitch_weight
stitch weight
void graphviz2pdf(std::string const &filename, const char *suffix=".gv")
convert graphviz format to pdf. The input filename should be filename+suffix
#define assert_msg(condition, message)
assertion with message