11 #ifndef LIMBO_ALGORITHMS_GRAPHUTILITY_H
12 #define LIMBO_ALGORITHMS_GRAPHUTILITY_H
18 #include <boost/graph/graph_concepts.hpp>
19 #include <boost/graph/iteration_macros.hpp>
33 template <
typename GraphType>
35 std::map<
typename boost::graph_traits<GraphType>::vertex_descriptor,
36 typename boost::graph_traits<GraphType>::vertex_descriptor>& mCompG2G)
38 typedef typename boost::graph_traits<GraphType>::vertex_descriptor vertex_descriptor;
39 std::map<vertex_descriptor, vertex_descriptor> vmap;
41 BGL_FORALL_VERTICES_T(v, g, GraphType)
43 vertex_descriptor u = boost::add_vertex(gp);
48 BGL_FORALL_VERTICES_T(u, g, GraphType)
50 std::vector<vertex_descriptor> neighbors(
51 adjacent_vertices(u, g).first,
52 adjacent_vertices(u, g).second
54 std::sort(neighbors.begin(), neighbors.end());
55 BGL_FORALL_VERTICES_T(v, g, GraphType)
58 if (v != u && !std::binary_search(neighbors.begin(), neighbors.end(), v))
59 boost::add_edge(vmap[u], vmap[v], gp);
66 template <
typename GraphType>
70 typedef GraphType graph_type;
71 typedef typename boost::graph_traits<graph_type>::vertex_descriptor vertex_descriptor;
81 vertex_descriptor
label(vertex_descriptor v)
const {
return v;}
86 template <
typename GraphType>
90 typedef GraphType graph_type;
91 typedef typename boost::graph_traits<graph_type>::edge_descriptor edge_descriptor;
92 typedef typename boost::property_traits<typename boost::property_map<graph_type, boost::edge_weight_t>::const_type>::value_type edge_weight_type;
102 edge_weight_type
label(edge_descriptor e)
const {
return boost::get(boost::edge_weight, g, e);}
104 std::string
color(edge_descriptor )
const {
return "black";}
106 std::string
style(edge_descriptor )
const {
return "solid";}
118 template <
typename GraphType,
typename VertexLabelType,
typename EdgeLabelType>
119 void write_graph(std::ofstream& out, GraphType
const& g, VertexLabelType
const& vl, EdgeLabelType
const& el)
121 out <<
"graph D { \n"
123 <<
" size=\"4, 3\"\n"
124 <<
" ratio=\"fill\"\n"
125 <<
" edge[style=\"bold\",fontsize=200]\n"
126 <<
" node[shape=\"circle\",fontsize=200]\n";
129 uint32_t vertex_num = boost::num_vertices(g);
130 for(uint32_t k = 0; k < vertex_num; ++k)
133 out <<
" " << k <<
"[shape=\"circle\""<<
",label=\"" << vl.label(k) <<
"\"]\n";
137 typename boost::graph_traits<GraphType>::edge_iterator ei, eie;
138 for (boost::tie(ei, eie) = boost::edges(g); ei != eie; ++ei)
140 out <<
" " << boost::source(*ei, g) <<
"--" << boost::target(*ei, g)
141 <<
"[label=" << el.label(*ei) <<
",color=\"" << el.color(*ei) <<
"\",style=\"" << el.style(*ei) <<
"\",penwidth=3]\n";
150 inline void graphviz2pdf(std::string
const& filename,
const char* suffix =
".gv")
153 sprintf(cmd,
"dot -Tpdf %s%s -o %s.pdf", filename.c_str(), suffix, filename.c_str());
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
void write_graph(std::ofstream &out, GraphType const &g, VertexLabelType const &vl, EdgeLabelType const &el)
write graph to graphviz format and convert to pdf. Although Boost.Graph has write_graphviz component...
default EdgeLabelWriter for write_graph
VertexLabelWriter(graph_type const &_g)
EdgeLabelWriter(graph_type const &_g)
graph_type const & g
bind graph object
std::string color(edge_descriptor) const
graph_type const & g
bind graph object
std::string style(edge_descriptor) const
vertex_descriptor label(vertex_descriptor v) const
default VertexLabelWriter for write_graph
edge_weight_type label(edge_descriptor e) const
void graphviz2pdf(std::string const &filename, const char *suffix=".gv")
convert graphviz format to pdf. The input filename should be filename+suffix