11 #ifndef LIMBO_ALGORITHMS_MAXINDEPENDENTSET_H
12 #define LIMBO_ALGORITHMS_MAXINDEPENDENTSET_H
15 #include <boost/graph/bron_kerbosch_all_cliques.hpp>
18 namespace limbo {
namespace algorithms {
29 template <
typename GraphType,
typename MisVisitorType>
33 typedef GraphType graph_type;
34 typedef MisVisitorType mis_visitor_type;
35 typedef typename boost::graph_traits<graph_type>::vertex_descriptor vertex_descriptor_type;
36 typedef std::map<vertex_descriptor_type, vertex_descriptor_type> map_type;
53 template <
typename CliqueType>
54 void clique(CliqueType
const& c, graph_type
const& cg)
57 typedef CliqueType clique_type;
61 if (boost::num_vertices(cg) > 0)
64 for (
typename clique_type::const_iterator it = c.begin();
66 is.push_back(mCompG2G[*it]);
81 template <
typename GraphType,
typename VisitorType,
typename AlgorithmType>
92 template <
typename GraphType,
typename MisVisitorType>
95 typedef typename boost::graph_traits<GraphType>::vertex_descriptor vertex_descriptor_type;
97 std::map<vertex_descriptor_type, vertex_descriptor_type> mCompG2G;
clique_visitor_type(mis_visitor_type &mv, map_type &mCG2G)
void complement_graph(GraphType const &g, GraphType &gp, std::map< typename boost::graph_traits< GraphType >::vertex_descriptor, typename boost::graph_traits< GraphType >::vertex_descriptor > &mCompG2G)
get the complement graph of original graph
clique_visitor_type(clique_visitor_type const &rhs)
some graph utilities such as compute complement graph and graphviz writer.
map_type & mCompG2G
bind vertex mapping from complement graph to original graph
void max_independent_set(GraphType const &g, VisitorType vis, AlgorithmType const &)
void clique(CliqueType const &c, graph_type const &cg)
MisVisitorType & mis_visitor
bind mis visitor
callback for boost::bron_kerbosch_all_cliques