9 #include <boost/graph/graphviz.hpp>
10 #include <boost/graph/graph_utility.hpp>
11 #include <boost/graph/adjacency_list.hpp>
12 #include <boost/graph/undirected_graph.hpp>
14 #include <boost/version.hpp>
15 #if BOOST_VERSION <= 14601
16 #include <boost/graph/detail/is_same.hpp>
18 #include <boost/type_traits/is_same.hpp>
27 using namespace boost;
32 typedef adjacency_list<vecS, vecS, undirectedS,
33 property<vertex_index_t, std::size_t, property<vertex_color_t, int> >,
34 property<edge_index_t, std::size_t, property<edge_weight_t, int> >,
35 property<graph_name_t, string> > graph_type;
36 typedef subgraph<graph_type> subgraph_type;
37 typedef property<vertex_index_t, std::size_t> VertexId;
38 typedef property<edge_index_t, std::size_t> EdgeID;
39 typedef graph_traits<graph_type>::vertex_descriptor vertex_descriptor;
40 typedef graph_traits<graph_type>::edge_descriptor edge_descriptor;
41 typedef property_map<graph_type, edge_weight_t>::type edge_weight_map_type;
42 typedef property_map<graph_type, vertex_color_t>::type vertex_color_map_type;
49 ifstream in (filename.c_str());
53 typedef adjacency_list<vecS, vecS, undirectedS,
54 property<vertex_index_t, std::size_t, property<vertex_color_t, int, property<vertex_name_t, std::size_t> > >,
55 property<edge_index_t, std::size_t, property<edge_weight_t, int> >,
56 property<graph_name_t, string> > tmp_graph_type;
58 dynamic_properties tmpdp;
59 tmpdp.property(
"node_id",
get(vertex_name, tmpg));
60 tmpdp.property(
"label",
get(vertex_name, tmpg));
61 tmpdp.property(
"weight",
get(edge_weight, tmpg));
62 tmpdp.property(
"label",
get(edge_weight, tmpg));
63 assert(read_graphviz(in, tmpg, tmpdp,
"node_id"));
66 graph_type g (num_vertices(tmpg));
67 graph_traits<tmp_graph_type>::vertex_iterator vit, vit_end;
68 for (tie(vit, vit_end) = vertices(tmpg); vit != vit_end; ++vit)
70 size_t name =
get(vertex_name, tmpg, *vit);
71 int color =
get(vertex_color, tmpg, *vit);
72 put(vertex_color, g, (vertex_descriptor)name, color);
75 graph_traits<tmp_graph_type>::edge_iterator eit, eit_end;
76 for (tie(eit, eit_end) = edges(tmpg); eit != eit_end; ++eit)
78 size_t s_name =
get(vertex_name, tmpg, source(*eit, tmpg));
79 size_t t_name =
get(vertex_name, tmpg, target(*eit, tmpg));
80 pair<edge_descriptor, bool> pe = add_edge(s_name, t_name, g);
82 int weight =
get(edge_weight, g, *eit);
83 put(edge_weight, g, pe.first, weight);
86 #ifdef DEBUG_GRAPHSIMPLIFICATION
87 dynamic_properties dp;
88 dp.property(
"id",
get(vertex_index, g));
89 dp.property(
"node_id",
get(vertex_index, g));
90 dp.property(
"label",
get(vertex_index, g));
91 dp.property(
"weight",
get(edge_weight, g));
92 dp.property(
"label",
get(edge_weight, g));
93 ofstream out (
"graph_init.gv");
94 write_graphviz_dp(out, g, dp,
string(
"id"));
96 system(
"dot -Tpdf graph_init.gv -o graph_init.pdf");
101 simplification_type gs (g, 3);
102 std::vector<int> vPrecolor (num_vertices(g), -1);
103 if (vPrecolor.size() > 0) vPrecolor[0] = 0;
104 if (vPrecolor.size() > 3) vPrecolor[3] = 0;
105 if (vPrecolor.size() > 4) vPrecolor[4] = 0;
106 gs.precolor(vPrecolor.begin(), vPrecolor.end());
108 gs.hide_small_degree();
109 gs.write_graph_dot(
"graph_simpl1");
111 gs.biconnected_component();
114 gs.simplify(simplification_type::HIDE_SMALL_DEGREE | simplification_type::BICONNECTED_COMPONENT);
116 gs.write_graph_dot(
"graph_simpl3");
117 gs.write_simplified_graph_dot(
"graph_simpl_merge");
127 int main(
int argc,
char** argv)
int main(int argc, char **argv)
Various graph simplification techniques for graph coloring. Some of them can also be used in other ap...
void realGraph(string const &filename)