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>
20 #include <boost/graph/erdos_renyi_generator.hpp>
21 #include <boost/random/mersenne_twister.hpp>
22 #include <boost/graph/random.hpp>
23 #include <boost/graph/iteration_macros.hpp>
25 #include <boost/version.hpp>
26 #if BOOST_VERSION <= 14601
27 #include <boost/graph/detail/is_same.hpp>
29 #include <boost/type_traits/is_same.hpp>
38 using namespace boost;
43 typedef adjacency_list<vecS, vecS, undirectedS,
44 property<vertex_index_t, std::size_t, property<vertex_color_t, int> >,
45 property<edge_index_t, std::size_t, property<edge_weight_t, int> >,
46 property<graph_name_t, string> > graph_type;
47 typedef subgraph<graph_type> subgraph_type;
48 typedef property<vertex_index_t, std::size_t> VertexId;
49 typedef property<edge_index_t, std::size_t> EdgeID;
50 typedef graph_traits<graph_type>::vertex_descriptor vertex_descriptor;
51 typedef graph_traits<graph_type>::edge_descriptor edge_descriptor;
52 typedef property_map<graph_type, edge_weight_t>::type edge_weight_map_type;
53 typedef property_map<graph_type, vertex_color_t>::type vertex_color_map_type;
61 vertex_descriptor a = boost::add_vertex(g);
62 vertex_descriptor b = boost::add_vertex(g);
63 vertex_descriptor c = boost::add_vertex(g);
64 vertex_descriptor d = boost::add_vertex(g);
65 vertex_descriptor e = boost::add_vertex(g);
66 boost::add_edge(a, b, g);
67 boost::add_edge(a, c, g);
68 boost::add_edge(a, d, g);
69 boost::add_edge(b, c, g);
70 boost::add_edge(b, d, g);
71 boost::add_edge(c, d, g);
72 boost::add_edge(a, e, g);
73 boost::add_edge(c, e, g);
74 boost::add_edge(d, e, g);
76 BOOST_AUTO(edge_weight_map,
get(edge_weight, g));
77 graph_traits<graph_type>::edge_iterator eit, eit_end;
78 for (tie(eit, eit_end) = edges(g); eit != eit_end; ++eit)
80 edge_weight_map[*eit] = 1;
88 printf(
"solved in %u LP iterations\n", lc.
lp_iters());
99 std::vector<vertex_descriptor> vertex_set;
100 std::vector< std::pair<vertex_descriptor, vertex_descriptor> > edge_set;
101 generate_random_graph(g, N, N * 2, gen,
102 std::back_inserter(vertex_set),
103 std::back_inserter(edge_set));
104 BOOST_AUTO(edge_weight_map,
get(edge_weight, g));
106 graph_traits<graph_type>::edge_iterator eit, eit_end;
107 for (tie(eit, eit_end) = edges(g); eit != eit_end; ++eit, ++i)
108 edge_weight_map[*eit] = 1;
115 printf(
"solved in %u LP iterations\n", lc.
lp_iters());
124 ifstream in (filename.c_str());
128 typedef adjacency_list<vecS, vecS, undirectedS,
129 property<vertex_index_t, std::size_t, property<vertex_color_t, int, property<vertex_name_t, std::size_t> > >,
130 property<edge_index_t, std::size_t, property<edge_weight_t, int> >,
131 property<graph_name_t, string> > tmp_graph_type;
133 dynamic_properties tmpdp;
134 tmpdp.property(
"node_id",
get(vertex_name, tmpg));
135 tmpdp.property(
"label",
get(vertex_name, tmpg));
136 tmpdp.property(
"weight",
get(edge_weight, tmpg));
137 tmpdp.property(
"label",
get(edge_weight, tmpg));
138 assert(read_graphviz(in, tmpg, tmpdp,
"node_id"));
141 graph_type g (num_vertices(tmpg));
142 graph_traits<tmp_graph_type>::vertex_iterator vit, vit_end;
143 for (tie(vit, vit_end) = vertices(tmpg); vit != vit_end; ++vit)
145 size_t name =
get(vertex_name, tmpg, *vit);
146 int color =
get(vertex_color, tmpg, *vit);
147 put(vertex_color, g, (vertex_descriptor)name, color);
150 graph_traits<tmp_graph_type>::edge_iterator eit, eit_end;
151 for (tie(eit, eit_end) = edges(tmpg); eit != eit_end; ++eit)
153 size_t s_name =
get(vertex_name, tmpg, source(*eit, tmpg));
154 size_t t_name =
get(vertex_name, tmpg, target(*eit, tmpg));
155 pair<edge_descriptor, bool> pe = add_edge(s_name, t_name, g);
157 int weight =
get(edge_weight, g, *eit);
158 put(edge_weight, g, pe.first, weight);
161 #ifdef DEBUG_LPCOLORING
162 dynamic_properties dp;
163 dp.property(
"id",
get(vertex_index, g));
164 dp.property(
"node_id",
get(vertex_index, g));
165 dp.property(
"label",
get(vertex_index, g));
166 dp.property(
"weight",
get(edge_weight, g));
167 dp.property(
"label",
get(edge_weight, g));
168 ofstream out (
"graph_init.gv");
169 write_graphviz_dp(out, g, dp,
string(
"id"));
171 system(
"dot -Tpdf graph_init.gv -o graph_init.pdf");
179 printf(
"solved in %u LP iterations\n", lc.
lp_iters());
191 int main(
int argc,
char** argv)
201 cout <<
"cost = " << cost << endl;
double real_graph(string const &filename)
int main(int argc, char **argv)
coloring algorithm based on iterative linear programming (LP) and rounding
coloring a graph with saturation degree based heuristics
uint32_t lp_iters() const
virtual void color_num(ColorNumType cn)
return chromatic number of a graph