8 #ifndef LIMBO_ALGORITHMS_COLORING_CHROMATICNUMBER
9 #define LIMBO_ALGORITHMS_COLORING_CHROMATICNUMBER
14 #include <boost/graph/graph_concepts.hpp>
15 #include <boost/graph/subgraph.hpp>
51 template <
typename GraphType>
56 typedef GraphType graph_type;
57 typedef boost::subgraph<graph_type> subgraph_type;
58 typedef typename boost::graph_traits<graph_type>::vertex_descriptor graph_vertex_type;
77 template <
typename MisType>
78 void mis(MisType
const& is)
81 if (!mMisNode.empty())
83 if (mMisNode.front().size() < is.size())
85 else if (mMisNode.front().size() > is.size())
89 mMisNode.push_back(set<graph_vertex_type>());
90 for (
typename MisType::const_iterator it = is.begin();
92 mMisNode.back().insert(*it);
112 int cn = boost::num_vertices(g);
115 if (cn <= 1)
return cn;
118 BGL_FORALL_EDGES_T(e, g, subgraph_type)
121 if (boost::source(e, g) != boost::target(e, g))
128 vector<set<graph_vertex_type> > mMisNode;
131 #ifdef DEBUG_CHROMATICNUMBER
133 typename boost::property_map<subgraph_type, boost::vertex_index_t>::type vertex_index_map = boost::get(boost::vertex_index, g);
135 for (
typename vector<set<graph_vertex_type> >::const_iterator it1 = mMisNode.begin();
136 it1 != mMisNode.end(); ++it1)
138 set<graph_vertex_type>
const& sMisNode = *it1;
140 for (
typename set<graph_vertex_type>::const_iterator it2 = sMisNode.begin();
141 it2 != sMisNode.end(); ++it2)
142 cout << vertex_index_map[*it2] <<
" ";
148 for (
typename vector<set<graph_vertex_type> >::const_iterator it1 = mMisNode.begin();
149 it1 != mMisNode.end(); ++it1)
151 set<graph_vertex_type>
const& sMisNode = *it1;
152 subgraph_type& g_s = g.create_subgraph();
154 BGL_FORALL_VERTICES_T(v, g, subgraph_type)
156 if (!sMisNode.count(v))
157 boost::add_vertex(v, g_s);
160 #ifdef DEBUG_CHROMATICNUMBER
166 if (cn > comp_cn) cn = comp_cn;
173 if (boost::num_vertices(g_s) == 0
174 || (boost::num_vertices(g_s) > 0 && cn == 1))
solve maximum independent sets with maximum cliques
int operator()(subgraph_type g) const
void mis(MisType const &is)
vector< set< graph_vertex_type > > & mMisNode
bind mis nodes
int chromatic_number(subgraph_type &g) const
void max_independent_set(GraphType const &g, VisitorType vis, AlgorithmType const &)
mis_visitor_type(mis_visitor_type const &rhs)
mis_visitor_type(vector< set< graph_vertex_type > > &mMisNode_)