14 #ifndef LIMBO_ALGORITHMS_COLORING_GREEDYCOLORING
15 #define LIMBO_ALGORITHMS_COLORING_GREEDYCOLORING
21 #include <boost/graph/graph_concepts.hpp>
41 template <
typename GraphType>
46 typedef GraphType graph_type;
47 typedef typename boost::graph_traits<graph_type>::vertex_descriptor graph_vertex_type;
65 typename boost::graph_traits<graph_type>::out_edge_iterator ite, ite_end;
66 for (boost::tie(ite, ite_end) = boost::out_edges(v,
m_dc.
m_graph);
67 ite != ite_end; ++ite)
71 int color = found->second;
82 bool operator()(graph_vertex_type
const& v1, graph_vertex_type
const& v2)
const
95 BGL_FORALL_VERTICES_T(v, g, graph_type)
107 int color(graph_vertex_type v)
const
109 BOOST_AUTO(found,
m_mColor.find(v));
110 if (found ==
m_mColor.end())
return -1;
111 else return found->second;
125 vector<graph_vertex_type> vNode;
126 vNode.reserve(boost::num_vertices(
m_graph));
127 BGL_FORALL_VERTICES_T(v,
m_graph, graph_type)
134 while (!vNode.empty())
137 typename vector<graph_vertex_type>::iterator itv = std::max_element(vNode.begin(), vNode.end(),
saturation_degree_type(*
this));
141 typename boost::graph_traits<graph_type>::out_edge_iterator ite, ite_end;
142 for (boost::tie(ite, ite_end) = boost::out_edges(*itv,
m_graph);
143 ite != ite_end; ++ite)
146 sUsedColor.insert(color);
148 for (
int i = 0; i < color_cnt+1; ++i)
150 if (!sUsedColor.count(i))
map< graph_vertex_type, int > const & color_map() const
int saturation_degree(graph_vertex_type const &v) const
map< graph_vertex_type, int > m_mColor
color map
bool operator()(graph_vertex_type const &v1, graph_vertex_type const &v2) const
saturation_degree_type(DsatColoring const &dc)
std::iterator_traits< Iterator >::value_type max(Iterator first, Iterator last)
get max of an array
DsatColoring const & m_dc
bind DsatColoring class
graph_type const & m_graph
graph
DsatColoring(graph_type const &g)
int color(graph_vertex_type v) const