11 #include <boost/graph/graphviz.hpp>
12 #include <boost/graph/graph_utility.hpp>
13 #include <boost/graph/adjacency_list.hpp>
14 #include <boost/graph/undirected_graph.hpp>
17 #include <boost/graph/erdos_renyi_generator.hpp>
18 #include <boost/random/mersenne_twister.hpp>
19 #include <boost/graph/random.hpp>
20 #include <boost/graph/iteration_macros.hpp>
22 #include <boost/version.hpp>
23 #if BOOST_VERSION <= 14601
24 #include <boost/graph/detail/is_same.hpp>
26 #include <boost/type_traits/is_same.hpp>
33 using namespace boost;
37 template <
typename GraphType>
52 template <
typename MisType>
53 void mis(MisType
const& is)
55 typename property_map<GraphType, vertex_index_t>::type vertex_index_map =
get(vertex_index, g);
58 if (num_vertices(g) < 20)
60 cout <<
"independent sets" << endl;
61 for (
typename MisType::const_iterator it = is.begin();
64 cout << vertex_index_map[*it] <<
" ";
81 typedef adjacency_list<vecS, vecS, undirectedS,
82 property<vertex_index_t, std::size_t>,
83 property<edge_index_t, std::size_t, property<edge_weight_t, int> >,
84 property<graph_name_t, string> > graph_type;
85 typedef subgraph<graph_type> subgraph_type;
86 typedef property<vertex_index_t, std::size_t> VertexId;
87 typedef property<edge_index_t, std::size_t> EdgeID;
88 typedef typename boost::graph_traits<subgraph_type>::vertex_descriptor vertex_descriptor;
94 std::vector<vertex_descriptor> vertex_set;
95 std::vector< std::pair<vertex_descriptor, vertex_descriptor> > edge_set;
96 generate_random_graph(g, N, N * 2, gen,
97 std::back_inserter(vertex_set),
98 std::back_inserter(edge_set));
103 vertex_descriptor v1 = add_vertex(g);
104 vertex_descriptor v2 = add_vertex(g);
105 vertex_descriptor v3 = add_vertex(g);
106 vertex_descriptor v4 = add_vertex(g);
107 vertex_descriptor v5 = add_vertex(g);
119 property_map<subgraph_type, vertex_index_t>::type vertex_index_map =
get(vertex_index, g);
120 property_map<subgraph_type, edge_index_t>::type edge_index_map =
get(edge_index, g);
122 cout <<
"original graph" << endl;
123 print_edges2(g, vertex_index_map, edge_index_map);
124 print_graph(g, vertex_index_map);
126 dynamic_properties dp;
130 dp.property(
"node_id",
get(vertex_index, g));
131 ofstream out(
"graph.gv");
132 write_graphviz_dp(out, g, dp);
133 system(
"dot -Tpdf graph.gv -o graph.pdf");
138 std::map<vertex_descriptor, vertex_descriptor> mCompG2G;
141 cout <<
"complement graph" << endl;
142 BGL_FORALL_VERTICES_T(v, gp, subgraph_type)
144 cout << vertex_index_map[mCompG2G[v]] <<
" <--> ";
145 boost::graph_traits<subgraph_type>::out_edge_iterator e, e_end;
146 for (boost::tie(e, e_end) = out_edges(v, gp); e != e_end; ++e)
147 cout << vertex_index_map[mCompG2G[target(*e, gp)]] <<
" ";
160 cout <<
"chromatic number = " << lcn(g) << endl;
166 cout <<
"dsat coloring number = " << dc() << endl;
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
MisVisitor(GraphType &g_)
void mis(MisType const &is)
void max_independent_set(GraphType const &g, VisitorType vis, AlgorithmType const &)
coloring a graph with saturation degree based heuristics
MisVisitor(MisVisitor const &rhs)
return chromatic number of a graph