williamr@2
|
1 |
//=======================================================================
|
williamr@2
|
2 |
// Copyright 2001 University of Notre Dame.
|
williamr@2
|
3 |
// Copyright 2003 Jeremy Siek
|
williamr@2
|
4 |
// Authors: Lie-Quan Lee and Jeremy Siek
|
williamr@2
|
5 |
//
|
williamr@2
|
6 |
// Distributed under the Boost Software License, Version 1.0. (See
|
williamr@2
|
7 |
// accompanying file LICENSE_1_0.txt or copy at
|
williamr@2
|
8 |
// http://www.boost.org/LICENSE_1_0.txt)
|
williamr@2
|
9 |
//=======================================================================
|
williamr@2
|
10 |
#ifndef BOOST_GRAPHVIZ_HPP
|
williamr@2
|
11 |
#define BOOST_GRAPHVIZ_HPP
|
williamr@2
|
12 |
|
williamr@2
|
13 |
#include <boost/config.hpp>
|
williamr@2
|
14 |
#include <string>
|
williamr@2
|
15 |
#include <map>
|
williamr@2
|
16 |
#include <iostream>
|
williamr@2
|
17 |
#include <fstream>
|
williamr@2
|
18 |
#include <stdio.h> // for FILE
|
williamr@2
|
19 |
#include <boost/property_map.hpp>
|
williamr@2
|
20 |
#include <boost/tuple/tuple.hpp>
|
williamr@2
|
21 |
#include <boost/graph/graph_traits.hpp>
|
williamr@2
|
22 |
#include <boost/graph/properties.hpp>
|
williamr@2
|
23 |
#include <boost/graph/subgraph.hpp>
|
williamr@2
|
24 |
#include <boost/graph/adjacency_list.hpp>
|
williamr@2
|
25 |
#include <boost/dynamic_property_map.hpp>
|
williamr@2
|
26 |
|
williamr@2
|
27 |
#ifdef BOOST_HAS_DECLSPEC
|
williamr@2
|
28 |
# if defined(BOOST_ALL_DYN_LINK) || defined(BOOST_GRAPH_DYN_LINK)
|
williamr@2
|
29 |
# ifdef BOOST_GRAPH_SOURCE
|
williamr@2
|
30 |
# define BOOST_GRAPH_DECL __declspec(dllexport)
|
williamr@2
|
31 |
# else
|
williamr@2
|
32 |
# define BOOST_GRAPH_DECL __declspec(dllimport)
|
williamr@2
|
33 |
# endif // BOOST_GRAPH_SOURCE
|
williamr@2
|
34 |
# endif // DYN_LINK
|
williamr@2
|
35 |
#endif // BOOST_HAS_DECLSPEC
|
williamr@2
|
36 |
|
williamr@2
|
37 |
#ifndef BOOST_GRAPH_DECL
|
williamr@2
|
38 |
# define BOOST_GRAPH_DECL
|
williamr@2
|
39 |
#endif
|
williamr@2
|
40 |
|
williamr@2
|
41 |
namespace boost {
|
williamr@2
|
42 |
|
williamr@2
|
43 |
template <typename directed_category>
|
williamr@2
|
44 |
struct graphviz_io_traits {
|
williamr@2
|
45 |
static std::string name() {
|
williamr@2
|
46 |
return "digraph";
|
williamr@2
|
47 |
}
|
williamr@2
|
48 |
static std::string delimiter() {
|
williamr@2
|
49 |
return "->";
|
williamr@2
|
50 |
} };
|
williamr@2
|
51 |
|
williamr@2
|
52 |
template <>
|
williamr@2
|
53 |
struct graphviz_io_traits <undirected_tag> {
|
williamr@2
|
54 |
static std::string name() {
|
williamr@2
|
55 |
return "graph";
|
williamr@2
|
56 |
}
|
williamr@2
|
57 |
static std::string delimiter() {
|
williamr@2
|
58 |
return "--";
|
williamr@2
|
59 |
}
|
williamr@2
|
60 |
};
|
williamr@2
|
61 |
|
williamr@2
|
62 |
struct default_writer {
|
williamr@2
|
63 |
void operator()(std::ostream&) const {
|
williamr@2
|
64 |
}
|
williamr@2
|
65 |
template <class VorE>
|
williamr@2
|
66 |
void operator()(std::ostream&, const VorE&) const {
|
williamr@2
|
67 |
}
|
williamr@2
|
68 |
};
|
williamr@2
|
69 |
|
williamr@2
|
70 |
template <class Name>
|
williamr@2
|
71 |
class label_writer {
|
williamr@2
|
72 |
public:
|
williamr@2
|
73 |
label_writer(Name _name) : name(_name) {}
|
williamr@2
|
74 |
template <class VertexOrEdge>
|
williamr@2
|
75 |
void operator()(std::ostream& out, const VertexOrEdge& v) const {
|
williamr@2
|
76 |
out << "[label=\"" << get(name, v) << "\"]";
|
williamr@2
|
77 |
}
|
williamr@2
|
78 |
private:
|
williamr@2
|
79 |
Name name;
|
williamr@2
|
80 |
};
|
williamr@2
|
81 |
template <class Name>
|
williamr@2
|
82 |
inline label_writer<Name>
|
williamr@2
|
83 |
make_label_writer(Name n) {
|
williamr@2
|
84 |
return label_writer<Name>(n);
|
williamr@2
|
85 |
}
|
williamr@2
|
86 |
|
williamr@2
|
87 |
enum edge_attribute_t { edge_attribute = 1111 };
|
williamr@2
|
88 |
enum vertex_attribute_t { vertex_attribute = 2222 };
|
williamr@2
|
89 |
enum graph_graph_attribute_t { graph_graph_attribute = 3333 };
|
williamr@2
|
90 |
enum graph_vertex_attribute_t { graph_vertex_attribute = 4444 };
|
williamr@2
|
91 |
enum graph_edge_attribute_t { graph_edge_attribute = 5555 };
|
williamr@2
|
92 |
|
williamr@2
|
93 |
BOOST_INSTALL_PROPERTY(edge, attribute);
|
williamr@2
|
94 |
BOOST_INSTALL_PROPERTY(vertex, attribute);
|
williamr@2
|
95 |
BOOST_INSTALL_PROPERTY(graph, graph_attribute);
|
williamr@2
|
96 |
BOOST_INSTALL_PROPERTY(graph, vertex_attribute);
|
williamr@2
|
97 |
BOOST_INSTALL_PROPERTY(graph, edge_attribute);
|
williamr@2
|
98 |
|
williamr@2
|
99 |
|
williamr@2
|
100 |
template <class Attribute>
|
williamr@2
|
101 |
inline void write_attributes(const Attribute& attr, std::ostream& out) {
|
williamr@2
|
102 |
typename Attribute::const_iterator i, iend;
|
williamr@2
|
103 |
i = attr.begin();
|
williamr@2
|
104 |
iend = attr.end();
|
williamr@2
|
105 |
|
williamr@2
|
106 |
while ( i != iend ) {
|
williamr@2
|
107 |
out << i->first << "=\"" << i->second << "\"";
|
williamr@2
|
108 |
++i;
|
williamr@2
|
109 |
if ( i != iend )
|
williamr@2
|
110 |
out << ", ";
|
williamr@2
|
111 |
}
|
williamr@2
|
112 |
}
|
williamr@2
|
113 |
|
williamr@2
|
114 |
template<typename Attributes>
|
williamr@2
|
115 |
inline void write_all_attributes(Attributes attributes,
|
williamr@2
|
116 |
const std::string& name,
|
williamr@2
|
117 |
std::ostream& out)
|
williamr@2
|
118 |
{
|
williamr@2
|
119 |
typename Attributes::const_iterator i = attributes.begin(),
|
williamr@2
|
120 |
end = attributes.end();
|
williamr@2
|
121 |
if (i != end) {
|
williamr@2
|
122 |
out << name << " [\n";
|
williamr@2
|
123 |
write_attributes(attributes, out);
|
williamr@2
|
124 |
out << "];\n";
|
williamr@2
|
125 |
}
|
williamr@2
|
126 |
}
|
williamr@2
|
127 |
|
williamr@2
|
128 |
inline void write_all_attributes(detail::error_property_not_found,
|
williamr@2
|
129 |
const std::string&,
|
williamr@2
|
130 |
std::ostream&)
|
williamr@2
|
131 |
{
|
williamr@2
|
132 |
// Do nothing - no attributes exist
|
williamr@2
|
133 |
}
|
williamr@2
|
134 |
|
williamr@2
|
135 |
|
williamr@2
|
136 |
|
williamr@2
|
137 |
|
williamr@2
|
138 |
template <typename GraphGraphAttributes,
|
williamr@2
|
139 |
typename GraphNodeAttributes,
|
williamr@2
|
140 |
typename GraphEdgeAttributes>
|
williamr@2
|
141 |
struct graph_attributes_writer
|
williamr@2
|
142 |
{
|
williamr@2
|
143 |
graph_attributes_writer(GraphGraphAttributes gg,
|
williamr@2
|
144 |
GraphNodeAttributes gn,
|
williamr@2
|
145 |
GraphEdgeAttributes ge)
|
williamr@2
|
146 |
: g_attributes(gg), n_attributes(gn), e_attributes(ge) { }
|
williamr@2
|
147 |
|
williamr@2
|
148 |
void operator()(std::ostream& out) const {
|
williamr@2
|
149 |
write_all_attributes(g_attributes, "graph", out);
|
williamr@2
|
150 |
write_all_attributes(n_attributes, "node", out);
|
williamr@2
|
151 |
write_all_attributes(e_attributes, "edge", out);
|
williamr@2
|
152 |
}
|
williamr@2
|
153 |
GraphGraphAttributes g_attributes;
|
williamr@2
|
154 |
GraphNodeAttributes n_attributes;
|
williamr@2
|
155 |
GraphEdgeAttributes e_attributes;
|
williamr@2
|
156 |
};
|
williamr@2
|
157 |
|
williamr@2
|
158 |
template <typename GAttrMap, typename NAttrMap, typename EAttrMap>
|
williamr@2
|
159 |
graph_attributes_writer<GAttrMap, NAttrMap, EAttrMap>
|
williamr@2
|
160 |
make_graph_attributes_writer(const GAttrMap& g_attr, const NAttrMap& n_attr,
|
williamr@2
|
161 |
const EAttrMap& e_attr) {
|
williamr@2
|
162 |
return graph_attributes_writer<GAttrMap, NAttrMap, EAttrMap>
|
williamr@2
|
163 |
(g_attr, n_attr, e_attr);
|
williamr@2
|
164 |
}
|
williamr@2
|
165 |
|
williamr@2
|
166 |
|
williamr@2
|
167 |
template <typename Graph>
|
williamr@2
|
168 |
graph_attributes_writer
|
williamr@2
|
169 |
<typename graph_property<Graph, graph_graph_attribute_t>::type,
|
williamr@2
|
170 |
typename graph_property<Graph, graph_vertex_attribute_t>::type,
|
williamr@2
|
171 |
typename graph_property<Graph, graph_edge_attribute_t>::type>
|
williamr@2
|
172 |
make_graph_attributes_writer(const Graph& g)
|
williamr@2
|
173 |
{
|
williamr@2
|
174 |
typedef typename graph_property<Graph, graph_graph_attribute_t>::type
|
williamr@2
|
175 |
GAttrMap;
|
williamr@2
|
176 |
typedef typename graph_property<Graph, graph_vertex_attribute_t>::type
|
williamr@2
|
177 |
NAttrMap;
|
williamr@2
|
178 |
typedef typename graph_property<Graph, graph_edge_attribute_t>::type
|
williamr@2
|
179 |
EAttrMap;
|
williamr@2
|
180 |
GAttrMap gam = get_property(g, graph_graph_attribute);
|
williamr@2
|
181 |
NAttrMap nam = get_property(g, graph_vertex_attribute);
|
williamr@2
|
182 |
EAttrMap eam = get_property(g, graph_edge_attribute);
|
williamr@2
|
183 |
graph_attributes_writer<GAttrMap, NAttrMap, EAttrMap> writer(gam, nam, eam);
|
williamr@2
|
184 |
return writer;
|
williamr@2
|
185 |
}
|
williamr@2
|
186 |
|
williamr@2
|
187 |
template <typename AttributeMap>
|
williamr@2
|
188 |
struct attributes_writer {
|
williamr@2
|
189 |
attributes_writer(AttributeMap attr)
|
williamr@2
|
190 |
: attributes(attr) { }
|
williamr@2
|
191 |
|
williamr@2
|
192 |
template <class VorE>
|
williamr@2
|
193 |
void operator()(std::ostream& out, const VorE& e) const {
|
williamr@2
|
194 |
this->write_attribute(out, attributes[e]);
|
williamr@2
|
195 |
}
|
williamr@2
|
196 |
|
williamr@2
|
197 |
private:
|
williamr@2
|
198 |
template<typename AttributeSequence>
|
williamr@2
|
199 |
void write_attribute(std::ostream& out,
|
williamr@2
|
200 |
const AttributeSequence& seq) const
|
williamr@2
|
201 |
{
|
williamr@2
|
202 |
if (!seq.empty()) {
|
williamr@2
|
203 |
out << "[";
|
williamr@2
|
204 |
write_attributes(seq, out);
|
williamr@2
|
205 |
out << "]";
|
williamr@2
|
206 |
}
|
williamr@2
|
207 |
}
|
williamr@2
|
208 |
|
williamr@2
|
209 |
void write_attribute(std::ostream&,
|
williamr@2
|
210 |
detail::error_property_not_found) const
|
williamr@2
|
211 |
{
|
williamr@2
|
212 |
}
|
williamr@2
|
213 |
AttributeMap attributes;
|
williamr@2
|
214 |
};
|
williamr@2
|
215 |
|
williamr@2
|
216 |
template <typename Graph>
|
williamr@2
|
217 |
attributes_writer
|
williamr@2
|
218 |
<typename property_map<Graph, edge_attribute_t>::const_type>
|
williamr@2
|
219 |
make_edge_attributes_writer(const Graph& g)
|
williamr@2
|
220 |
{
|
williamr@2
|
221 |
typedef typename property_map<Graph, edge_attribute_t>::const_type
|
williamr@2
|
222 |
EdgeAttributeMap;
|
williamr@2
|
223 |
return attributes_writer<EdgeAttributeMap>(get(edge_attribute, g));
|
williamr@2
|
224 |
}
|
williamr@2
|
225 |
|
williamr@2
|
226 |
template <typename Graph>
|
williamr@2
|
227 |
attributes_writer
|
williamr@2
|
228 |
<typename property_map<Graph, vertex_attribute_t>::const_type>
|
williamr@2
|
229 |
make_vertex_attributes_writer(const Graph& g)
|
williamr@2
|
230 |
{
|
williamr@2
|
231 |
typedef typename property_map<Graph, vertex_attribute_t>::const_type
|
williamr@2
|
232 |
VertexAttributeMap;
|
williamr@2
|
233 |
return attributes_writer<VertexAttributeMap>(get(vertex_attribute, g));
|
williamr@2
|
234 |
}
|
williamr@2
|
235 |
|
williamr@2
|
236 |
template <typename Graph, typename VertexPropertiesWriter,
|
williamr@2
|
237 |
typename EdgePropertiesWriter, typename GraphPropertiesWriter,
|
williamr@2
|
238 |
typename VertexID>
|
williamr@2
|
239 |
inline void write_graphviz(std::ostream& out, const Graph& g,
|
williamr@2
|
240 |
VertexPropertiesWriter vpw,
|
williamr@2
|
241 |
EdgePropertiesWriter epw,
|
williamr@2
|
242 |
GraphPropertiesWriter gpw,
|
williamr@2
|
243 |
VertexID vertex_id)
|
williamr@2
|
244 |
{
|
williamr@2
|
245 |
typedef typename graph_traits<Graph>::directed_category cat_type;
|
williamr@2
|
246 |
typedef graphviz_io_traits<cat_type> Traits;
|
williamr@2
|
247 |
std::string name = "G";
|
williamr@2
|
248 |
out << Traits::name() << " " << name << " {" << std::endl;
|
williamr@2
|
249 |
|
williamr@2
|
250 |
gpw(out); //print graph properties
|
williamr@2
|
251 |
|
williamr@2
|
252 |
typename graph_traits<Graph>::vertex_iterator i, end;
|
williamr@2
|
253 |
|
williamr@2
|
254 |
for(tie(i,end) = vertices(g); i != end; ++i) {
|
williamr@2
|
255 |
out << get(vertex_id, *i);
|
williamr@2
|
256 |
vpw(out, *i); //print vertex attributes
|
williamr@2
|
257 |
out << ";" << std::endl;
|
williamr@2
|
258 |
}
|
williamr@2
|
259 |
typename graph_traits<Graph>::edge_iterator ei, edge_end;
|
williamr@2
|
260 |
for(tie(ei, edge_end) = edges(g); ei != edge_end; ++ei) {
|
williamr@2
|
261 |
out << get(vertex_id, source(*ei, g)) << Traits::delimiter() << get(vertex_id, target(*ei, g)) << " ";
|
williamr@2
|
262 |
epw(out, *ei); //print edge attributes
|
williamr@2
|
263 |
out << ";" << std::endl;
|
williamr@2
|
264 |
}
|
williamr@2
|
265 |
out << "}" << std::endl;
|
williamr@2
|
266 |
}
|
williamr@2
|
267 |
|
williamr@2
|
268 |
template <typename Graph, typename VertexPropertiesWriter,
|
williamr@2
|
269 |
typename EdgePropertiesWriter, typename GraphPropertiesWriter>
|
williamr@2
|
270 |
inline void write_graphviz(std::ostream& out, const Graph& g,
|
williamr@2
|
271 |
VertexPropertiesWriter vpw,
|
williamr@2
|
272 |
EdgePropertiesWriter epw,
|
williamr@2
|
273 |
GraphPropertiesWriter gpw)
|
williamr@2
|
274 |
{ write_graphviz(out, g, vpw, epw, gpw, get(vertex_index, g)); }
|
williamr@2
|
275 |
|
williamr@2
|
276 |
#if !defined(BOOST_MSVC) || BOOST_MSVC > 1300
|
williamr@2
|
277 |
// ambiguous overload problem with VC++
|
williamr@2
|
278 |
template <typename Graph>
|
williamr@2
|
279 |
inline void
|
williamr@2
|
280 |
write_graphviz(std::ostream& out, const Graph& g) {
|
williamr@2
|
281 |
default_writer dw;
|
williamr@2
|
282 |
default_writer gw;
|
williamr@2
|
283 |
write_graphviz(out, g, dw, dw, gw);
|
williamr@2
|
284 |
}
|
williamr@2
|
285 |
#endif
|
williamr@2
|
286 |
|
williamr@2
|
287 |
template <typename Graph, typename VertexWriter>
|
williamr@2
|
288 |
inline void
|
williamr@2
|
289 |
write_graphviz(std::ostream& out, const Graph& g, VertexWriter vw) {
|
williamr@2
|
290 |
default_writer dw;
|
williamr@2
|
291 |
default_writer gw;
|
williamr@2
|
292 |
write_graphviz(out, g, vw, dw, gw);
|
williamr@2
|
293 |
}
|
williamr@2
|
294 |
|
williamr@2
|
295 |
template <typename Graph, typename VertexWriter, typename EdgeWriter>
|
williamr@2
|
296 |
inline void
|
williamr@2
|
297 |
write_graphviz(std::ostream& out, const Graph& g,
|
williamr@2
|
298 |
VertexWriter vw, EdgeWriter ew) {
|
williamr@2
|
299 |
default_writer gw;
|
williamr@2
|
300 |
write_graphviz(out, g, vw, ew, gw);
|
williamr@2
|
301 |
}
|
williamr@2
|
302 |
|
williamr@2
|
303 |
namespace detail {
|
williamr@2
|
304 |
|
williamr@2
|
305 |
template <class Graph_, class RandomAccessIterator, class VertexID>
|
williamr@2
|
306 |
void write_graphviz_subgraph (std::ostream& out,
|
williamr@2
|
307 |
const subgraph<Graph_>& g,
|
williamr@2
|
308 |
RandomAccessIterator vertex_marker,
|
williamr@2
|
309 |
RandomAccessIterator edge_marker,
|
williamr@2
|
310 |
VertexID vertex_id)
|
williamr@2
|
311 |
{
|
williamr@2
|
312 |
typedef subgraph<Graph_> Graph;
|
williamr@2
|
313 |
typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
|
williamr@2
|
314 |
typedef typename graph_traits<Graph>::directed_category cat_type;
|
williamr@2
|
315 |
typedef graphviz_io_traits<cat_type> Traits;
|
williamr@2
|
316 |
|
williamr@2
|
317 |
typedef typename graph_property<Graph, graph_name_t>::type NameType;
|
williamr@2
|
318 |
const NameType& g_name = get_property(g, graph_name);
|
williamr@2
|
319 |
|
williamr@2
|
320 |
if ( g.is_root() )
|
williamr@2
|
321 |
out << Traits::name() ;
|
williamr@2
|
322 |
else
|
williamr@2
|
323 |
out << "subgraph";
|
williamr@2
|
324 |
|
williamr@2
|
325 |
out << " " << g_name << " {" << std::endl;
|
williamr@2
|
326 |
|
williamr@2
|
327 |
typename Graph::const_children_iterator i_child, j_child;
|
williamr@2
|
328 |
|
williamr@2
|
329 |
//print graph/node/edge attributes
|
williamr@2
|
330 |
#if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
|
williamr@2
|
331 |
typedef typename graph_property<Graph, graph_graph_attribute_t>::type
|
williamr@2
|
332 |
GAttrMap;
|
williamr@2
|
333 |
typedef typename graph_property<Graph, graph_vertex_attribute_t>::type
|
williamr@2
|
334 |
NAttrMap;
|
williamr@2
|
335 |
typedef typename graph_property<Graph, graph_edge_attribute_t>::type
|
williamr@2
|
336 |
EAttrMap;
|
williamr@2
|
337 |
GAttrMap gam = get_property(g, graph_graph_attribute);
|
williamr@2
|
338 |
NAttrMap nam = get_property(g, graph_vertex_attribute);
|
williamr@2
|
339 |
EAttrMap eam = get_property(g, graph_edge_attribute);
|
williamr@2
|
340 |
graph_attributes_writer<GAttrMap, NAttrMap, EAttrMap> writer(gam, nam, eam);
|
williamr@2
|
341 |
writer(out);
|
williamr@2
|
342 |
#else
|
williamr@2
|
343 |
make_graph_attributes_writer(g)(out);
|
williamr@2
|
344 |
#endif
|
williamr@2
|
345 |
|
williamr@2
|
346 |
//print subgraph
|
williamr@2
|
347 |
for ( tie(i_child,j_child) = g.children();
|
williamr@2
|
348 |
i_child != j_child; ++i_child )
|
williamr@2
|
349 |
write_graphviz_subgraph(out, *i_child, vertex_marker, edge_marker,
|
williamr@2
|
350 |
vertex_id);
|
williamr@2
|
351 |
|
williamr@2
|
352 |
// Print out vertices and edges not in the subgraphs.
|
williamr@2
|
353 |
|
williamr@2
|
354 |
typename graph_traits<Graph>::vertex_iterator i, end;
|
williamr@2
|
355 |
typename graph_traits<Graph>::edge_iterator ei, edge_end;
|
williamr@2
|
356 |
|
williamr@2
|
357 |
for(tie(i,end) = vertices(g); i != end; ++i) {
|
williamr@2
|
358 |
Vertex v = g.local_to_global(*i);
|
williamr@2
|
359 |
int pos = get(vertex_id, v);
|
williamr@2
|
360 |
if ( vertex_marker[pos] ) {
|
williamr@2
|
361 |
vertex_marker[pos] = false;
|
williamr@2
|
362 |
out << pos;
|
williamr@2
|
363 |
#if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
|
williamr@2
|
364 |
typedef typename property_map<Graph, vertex_attribute_t>::const_type
|
williamr@2
|
365 |
VertexAttributeMap;
|
williamr@2
|
366 |
attributes_writer<VertexAttributeMap> vawriter(get(vertex_attribute,
|
williamr@2
|
367 |
g.root()));
|
williamr@2
|
368 |
vawriter(out, v);
|
williamr@2
|
369 |
#else
|
williamr@2
|
370 |
make_vertex_attributes_writer(g.root())(out, v);
|
williamr@2
|
371 |
#endif
|
williamr@2
|
372 |
out << ";" << std::endl;
|
williamr@2
|
373 |
}
|
williamr@2
|
374 |
}
|
williamr@2
|
375 |
|
williamr@2
|
376 |
for (tie(ei, edge_end) = edges(g); ei != edge_end; ++ei) {
|
williamr@2
|
377 |
Vertex u = g.local_to_global(source(*ei,g)),
|
williamr@2
|
378 |
v = g.local_to_global(target(*ei, g));
|
williamr@2
|
379 |
int pos = get(get(edge_index, g.root()), g.local_to_global(*ei));
|
williamr@2
|
380 |
if ( edge_marker[pos] ) {
|
williamr@2
|
381 |
edge_marker[pos] = false;
|
williamr@2
|
382 |
out << get(vertex_id, u) << " " << Traits::delimiter()
|
williamr@2
|
383 |
<< " " << get(vertex_id, v);
|
williamr@2
|
384 |
#if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
|
williamr@2
|
385 |
typedef typename property_map<Graph, edge_attribute_t>::const_type
|
williamr@2
|
386 |
EdgeAttributeMap;
|
williamr@2
|
387 |
attributes_writer<EdgeAttributeMap> eawriter(get(edge_attribute, g));
|
williamr@2
|
388 |
eawriter(out, *ei);
|
williamr@2
|
389 |
#else
|
williamr@2
|
390 |
make_edge_attributes_writer(g)(out, *ei); //print edge properties
|
williamr@2
|
391 |
#endif
|
williamr@2
|
392 |
out << ";" << std::endl;
|
williamr@2
|
393 |
}
|
williamr@2
|
394 |
}
|
williamr@2
|
395 |
out << "}" << std::endl;
|
williamr@2
|
396 |
}
|
williamr@2
|
397 |
} // namespace detail
|
williamr@2
|
398 |
|
williamr@2
|
399 |
// requires graph_name graph property
|
williamr@2
|
400 |
template <typename Graph>
|
williamr@2
|
401 |
void write_graphviz(std::ostream& out, const subgraph<Graph>& g) {
|
williamr@2
|
402 |
std::vector<bool> edge_marker(num_edges(g), true);
|
williamr@2
|
403 |
std::vector<bool> vertex_marker(num_vertices(g), true);
|
williamr@2
|
404 |
|
williamr@2
|
405 |
detail::write_graphviz_subgraph(out, g,
|
williamr@2
|
406 |
vertex_marker.begin(),
|
williamr@2
|
407 |
edge_marker.begin(),
|
williamr@2
|
408 |
get(vertex_index, g));
|
williamr@2
|
409 |
}
|
williamr@2
|
410 |
|
williamr@2
|
411 |
template <typename Graph>
|
williamr@2
|
412 |
void write_graphviz(const std::string& filename, const subgraph<Graph>& g) {
|
williamr@2
|
413 |
std::ofstream out(filename.c_str());
|
williamr@2
|
414 |
std::vector<bool> edge_marker(num_edges(g), true);
|
williamr@2
|
415 |
std::vector<bool> vertex_marker(num_vertices(g), true);
|
williamr@2
|
416 |
|
williamr@2
|
417 |
detail::write_graphviz_subgraph(out, g,
|
williamr@2
|
418 |
vertex_marker.begin(),
|
williamr@2
|
419 |
edge_marker.begin(),
|
williamr@2
|
420 |
get(vertex_index, g));
|
williamr@2
|
421 |
}
|
williamr@2
|
422 |
|
williamr@2
|
423 |
template <typename Graph, typename VertexID>
|
williamr@2
|
424 |
void write_graphviz(std::ostream& out, const subgraph<Graph>& g,
|
williamr@2
|
425 |
VertexID vertex_id)
|
williamr@2
|
426 |
{
|
williamr@2
|
427 |
std::vector<bool> edge_marker(num_edges(g), true);
|
williamr@2
|
428 |
std::vector<bool> vertex_marker(num_vertices(g), true);
|
williamr@2
|
429 |
|
williamr@2
|
430 |
detail::write_graphviz_subgraph(out, g,
|
williamr@2
|
431 |
vertex_marker.begin(),
|
williamr@2
|
432 |
edge_marker.begin(),
|
williamr@2
|
433 |
vertex_id);
|
williamr@2
|
434 |
}
|
williamr@2
|
435 |
|
williamr@2
|
436 |
template <typename Graph, typename VertexID>
|
williamr@2
|
437 |
void write_graphviz(const std::string& filename, const subgraph<Graph>& g,
|
williamr@2
|
438 |
VertexID vertex_id)
|
williamr@2
|
439 |
{
|
williamr@2
|
440 |
std::ofstream out(filename.c_str());
|
williamr@2
|
441 |
std::vector<bool> edge_marker(num_edges(g), true);
|
williamr@2
|
442 |
std::vector<bool> vertex_marker(num_vertices(g), true);
|
williamr@2
|
443 |
|
williamr@2
|
444 |
detail::write_graphviz_subgraph(out, g,
|
williamr@2
|
445 |
vertex_marker.begin(),
|
williamr@2
|
446 |
edge_marker.begin(),
|
williamr@2
|
447 |
vertex_id);
|
williamr@2
|
448 |
}
|
williamr@2
|
449 |
|
williamr@2
|
450 |
typedef std::map<std::string, std::string> GraphvizAttrList;
|
williamr@2
|
451 |
|
williamr@2
|
452 |
typedef property<vertex_attribute_t, GraphvizAttrList>
|
williamr@2
|
453 |
GraphvizVertexProperty;
|
williamr@2
|
454 |
|
williamr@2
|
455 |
typedef property<edge_attribute_t, GraphvizAttrList,
|
williamr@2
|
456 |
property<edge_index_t, int> >
|
williamr@2
|
457 |
GraphvizEdgeProperty;
|
williamr@2
|
458 |
|
williamr@2
|
459 |
typedef property<graph_graph_attribute_t, GraphvizAttrList,
|
williamr@2
|
460 |
property<graph_vertex_attribute_t, GraphvizAttrList,
|
williamr@2
|
461 |
property<graph_edge_attribute_t, GraphvizAttrList,
|
williamr@2
|
462 |
property<graph_name_t, std::string> > > >
|
williamr@2
|
463 |
GraphvizGraphProperty;
|
williamr@2
|
464 |
|
williamr@2
|
465 |
typedef subgraph<adjacency_list<vecS,
|
williamr@2
|
466 |
vecS, directedS,
|
williamr@2
|
467 |
GraphvizVertexProperty,
|
williamr@2
|
468 |
GraphvizEdgeProperty,
|
williamr@2
|
469 |
GraphvizGraphProperty> >
|
williamr@2
|
470 |
GraphvizDigraph;
|
williamr@2
|
471 |
|
williamr@2
|
472 |
typedef subgraph<adjacency_list<vecS,
|
williamr@2
|
473 |
vecS, undirectedS,
|
williamr@2
|
474 |
GraphvizVertexProperty,
|
williamr@2
|
475 |
GraphvizEdgeProperty,
|
williamr@2
|
476 |
GraphvizGraphProperty> >
|
williamr@2
|
477 |
GraphvizGraph;
|
williamr@2
|
478 |
|
williamr@2
|
479 |
|
williamr@2
|
480 |
// These four require linking the BGL-Graphviz library: libbgl-viz.a
|
williamr@2
|
481 |
// from the /src directory.
|
williamr@2
|
482 |
extern void read_graphviz(const std::string& file, GraphvizDigraph& g);
|
williamr@2
|
483 |
extern void read_graphviz(FILE* file, GraphvizDigraph& g);
|
williamr@2
|
484 |
|
williamr@2
|
485 |
extern void read_graphviz(const std::string& file, GraphvizGraph& g);
|
williamr@2
|
486 |
extern void read_graphviz(FILE* file, GraphvizGraph& g);
|
williamr@2
|
487 |
|
williamr@2
|
488 |
class dynamic_properties_writer
|
williamr@2
|
489 |
{
|
williamr@2
|
490 |
public:
|
williamr@2
|
491 |
dynamic_properties_writer(const dynamic_properties& dp) : dp(&dp) { }
|
williamr@2
|
492 |
|
williamr@2
|
493 |
template<typename Descriptor>
|
williamr@2
|
494 |
void operator()(std::ostream& out, Descriptor key) const
|
williamr@2
|
495 |
{
|
williamr@2
|
496 |
bool first = true;
|
williamr@2
|
497 |
for (dynamic_properties::const_iterator i = dp->begin();
|
williamr@2
|
498 |
i != dp->end(); ++i) {
|
williamr@2
|
499 |
if (typeid(key) == i->second->key()) {
|
williamr@2
|
500 |
if (first) out << " [";
|
williamr@2
|
501 |
else out << ", ";
|
williamr@2
|
502 |
first = false;
|
williamr@2
|
503 |
|
williamr@2
|
504 |
out << i->first << "=\"" << i->second->get_string(key) << "\"";
|
williamr@2
|
505 |
}
|
williamr@2
|
506 |
}
|
williamr@2
|
507 |
|
williamr@2
|
508 |
if (!first) out << "]";
|
williamr@2
|
509 |
}
|
williamr@2
|
510 |
|
williamr@2
|
511 |
private:
|
williamr@2
|
512 |
const dynamic_properties* dp;
|
williamr@2
|
513 |
};
|
williamr@2
|
514 |
|
williamr@2
|
515 |
class dynamic_vertex_properties_writer
|
williamr@2
|
516 |
{
|
williamr@2
|
517 |
public:
|
williamr@2
|
518 |
dynamic_vertex_properties_writer(const dynamic_properties& dp,
|
williamr@2
|
519 |
const std::string& node_id)
|
williamr@2
|
520 |
: dp(&dp), node_id(&node_id) { }
|
williamr@2
|
521 |
|
williamr@2
|
522 |
template<typename Descriptor>
|
williamr@2
|
523 |
void operator()(std::ostream& out, Descriptor key) const
|
williamr@2
|
524 |
{
|
williamr@2
|
525 |
bool first = true;
|
williamr@2
|
526 |
for (dynamic_properties::const_iterator i = dp->begin();
|
williamr@2
|
527 |
i != dp->end(); ++i) {
|
williamr@2
|
528 |
if (typeid(key) == i->second->key()
|
williamr@2
|
529 |
&& i->first != *node_id) {
|
williamr@2
|
530 |
if (first) out << " [";
|
williamr@2
|
531 |
else out << ", ";
|
williamr@2
|
532 |
first = false;
|
williamr@2
|
533 |
|
williamr@2
|
534 |
out << i->first << "=\"" << i->second->get_string(key) << "\"";
|
williamr@2
|
535 |
}
|
williamr@2
|
536 |
}
|
williamr@2
|
537 |
|
williamr@2
|
538 |
if (!first) out << "]";
|
williamr@2
|
539 |
}
|
williamr@2
|
540 |
|
williamr@2
|
541 |
private:
|
williamr@2
|
542 |
const dynamic_properties* dp;
|
williamr@2
|
543 |
const std::string* node_id;
|
williamr@2
|
544 |
};
|
williamr@2
|
545 |
|
williamr@2
|
546 |
namespace graph { namespace detail {
|
williamr@2
|
547 |
|
williamr@2
|
548 |
template<typename Vertex>
|
williamr@2
|
549 |
struct node_id_property_map
|
williamr@2
|
550 |
{
|
williamr@2
|
551 |
typedef std::string value_type;
|
williamr@2
|
552 |
typedef value_type reference;
|
williamr@2
|
553 |
typedef Vertex key_type;
|
williamr@2
|
554 |
typedef readable_property_map_tag category;
|
williamr@2
|
555 |
|
williamr@2
|
556 |
node_id_property_map() {}
|
williamr@2
|
557 |
|
williamr@2
|
558 |
node_id_property_map(const dynamic_properties& dp,
|
williamr@2
|
559 |
const std::string& node_id)
|
williamr@2
|
560 |
: dp(&dp), node_id(&node_id) { }
|
williamr@2
|
561 |
|
williamr@2
|
562 |
const dynamic_properties* dp;
|
williamr@2
|
563 |
const std::string* node_id;
|
williamr@2
|
564 |
};
|
williamr@2
|
565 |
|
williamr@2
|
566 |
template<typename Vertex>
|
williamr@2
|
567 |
inline std::string
|
williamr@2
|
568 |
get(node_id_property_map<Vertex> pm,
|
williamr@2
|
569 |
typename node_id_property_map<Vertex>::key_type v)
|
williamr@2
|
570 |
{ return get(*pm.node_id, *pm.dp, v); }
|
williamr@2
|
571 |
|
williamr@2
|
572 |
} } // end namespace graph::detail
|
williamr@2
|
573 |
|
williamr@2
|
574 |
template<typename Graph>
|
williamr@2
|
575 |
inline void
|
williamr@2
|
576 |
write_graphviz(std::ostream& out, const Graph& g,
|
williamr@2
|
577 |
const dynamic_properties& dp,
|
williamr@2
|
578 |
const std::string& node_id = "node_id")
|
williamr@2
|
579 |
{
|
williamr@2
|
580 |
typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
|
williamr@2
|
581 |
write_graphviz(out, g, dp, node_id,
|
williamr@2
|
582 |
graph::detail::node_id_property_map<Vertex>(dp, node_id));
|
williamr@2
|
583 |
}
|
williamr@2
|
584 |
|
williamr@2
|
585 |
template<typename Graph, typename VertexID>
|
williamr@2
|
586 |
void
|
williamr@2
|
587 |
write_graphviz(std::ostream& out, const Graph& g,
|
williamr@2
|
588 |
const dynamic_properties& dp, const std::string& node_id,
|
williamr@2
|
589 |
VertexID id)
|
williamr@2
|
590 |
{
|
williamr@2
|
591 |
write_graphviz
|
williamr@2
|
592 |
(out, g,
|
williamr@2
|
593 |
/*vertex_writer=*/dynamic_vertex_properties_writer(dp, node_id),
|
williamr@2
|
594 |
/*edge_writer=*/dynamic_properties_writer(dp),
|
williamr@2
|
595 |
/*graph_writer=*/default_writer(),
|
williamr@2
|
596 |
id);
|
williamr@2
|
597 |
}
|
williamr@2
|
598 |
|
williamr@2
|
599 |
/////////////////////////////////////////////////////////////////////////////
|
williamr@2
|
600 |
// Graph reader exceptions
|
williamr@2
|
601 |
/////////////////////////////////////////////////////////////////////////////
|
williamr@2
|
602 |
struct graph_exception : public std::exception {
|
williamr@2
|
603 |
virtual ~graph_exception() throw() {}
|
williamr@2
|
604 |
virtual const char* what() const throw() = 0;
|
williamr@2
|
605 |
};
|
williamr@2
|
606 |
|
williamr@2
|
607 |
struct bad_parallel_edge : public graph_exception {
|
williamr@2
|
608 |
std::string from;
|
williamr@2
|
609 |
std::string to;
|
williamr@2
|
610 |
mutable std::string statement;
|
williamr@2
|
611 |
bad_parallel_edge(const std::string& i, const std::string& j) :
|
williamr@2
|
612 |
from(i), to(j) {}
|
williamr@2
|
613 |
|
williamr@2
|
614 |
virtual ~bad_parallel_edge() throw() {}
|
williamr@2
|
615 |
const char* what() const throw() {
|
williamr@2
|
616 |
if(statement.empty())
|
williamr@2
|
617 |
statement =
|
williamr@2
|
618 |
std::string("Failed to add parallel edge: (")
|
williamr@2
|
619 |
+ from + "," + to + ")\n";
|
williamr@2
|
620 |
|
williamr@2
|
621 |
return statement.c_str();
|
williamr@2
|
622 |
}
|
williamr@2
|
623 |
};
|
williamr@2
|
624 |
|
williamr@2
|
625 |
struct directed_graph_error : public graph_exception {
|
williamr@2
|
626 |
virtual ~directed_graph_error() throw() {}
|
williamr@2
|
627 |
virtual const char* what() const throw() {
|
williamr@2
|
628 |
return
|
williamr@2
|
629 |
"read_graphviz: "
|
williamr@2
|
630 |
"Tried to read a directed graph into an undirected graph.";
|
williamr@2
|
631 |
}
|
williamr@2
|
632 |
};
|
williamr@2
|
633 |
|
williamr@2
|
634 |
struct undirected_graph_error : public graph_exception {
|
williamr@2
|
635 |
virtual ~undirected_graph_error() throw() {}
|
williamr@2
|
636 |
virtual const char* what() const throw() {
|
williamr@2
|
637 |
return
|
williamr@2
|
638 |
"read_graphviz: "
|
williamr@2
|
639 |
"Tried to read an undirected graph into a directed graph.";
|
williamr@2
|
640 |
}
|
williamr@2
|
641 |
};
|
williamr@2
|
642 |
|
williamr@2
|
643 |
namespace detail { namespace graph {
|
williamr@2
|
644 |
|
williamr@2
|
645 |
typedef std::string id_t;
|
williamr@2
|
646 |
typedef id_t node_t;
|
williamr@2
|
647 |
|
williamr@2
|
648 |
// edges are not uniquely determined by adjacent nodes
|
williamr@2
|
649 |
class edge_t {
|
williamr@2
|
650 |
int idx_;
|
williamr@2
|
651 |
explicit edge_t(int i) : idx_(i) {}
|
williamr@2
|
652 |
public:
|
williamr@2
|
653 |
static edge_t new_edge() {
|
williamr@2
|
654 |
static int idx = 0;
|
williamr@2
|
655 |
return edge_t(idx++);
|
williamr@2
|
656 |
};
|
williamr@2
|
657 |
|
williamr@2
|
658 |
bool operator==(const edge_t& rhs) const {
|
williamr@2
|
659 |
return idx_ == rhs.idx_;
|
williamr@2
|
660 |
}
|
williamr@2
|
661 |
bool operator<(const edge_t& rhs) const {
|
williamr@2
|
662 |
return idx_ < rhs.idx_;
|
williamr@2
|
663 |
}
|
williamr@2
|
664 |
};
|
williamr@2
|
665 |
|
williamr@2
|
666 |
class mutate_graph
|
williamr@2
|
667 |
{
|
williamr@2
|
668 |
public:
|
williamr@2
|
669 |
virtual ~mutate_graph() {}
|
williamr@2
|
670 |
virtual bool is_directed() const = 0;
|
williamr@2
|
671 |
virtual void do_add_vertex(const node_t& node) = 0;
|
williamr@2
|
672 |
|
williamr@2
|
673 |
virtual void
|
williamr@2
|
674 |
do_add_edge(const edge_t& edge, const node_t& source, const node_t& target)
|
williamr@2
|
675 |
= 0;
|
williamr@2
|
676 |
|
williamr@2
|
677 |
virtual void
|
williamr@2
|
678 |
set_node_property(const id_t& key, const node_t& node, const id_t& value) = 0;
|
williamr@2
|
679 |
|
williamr@2
|
680 |
virtual void
|
williamr@2
|
681 |
set_edge_property(const id_t& key, const edge_t& edge, const id_t& value) = 0;
|
williamr@2
|
682 |
};
|
williamr@2
|
683 |
|
williamr@2
|
684 |
template<typename MutableGraph>
|
williamr@2
|
685 |
class mutate_graph_impl : public mutate_graph
|
williamr@2
|
686 |
{
|
williamr@2
|
687 |
typedef typename graph_traits<MutableGraph>::vertex_descriptor bgl_vertex_t;
|
williamr@2
|
688 |
typedef typename graph_traits<MutableGraph>::edge_descriptor bgl_edge_t;
|
williamr@2
|
689 |
|
williamr@2
|
690 |
public:
|
williamr@2
|
691 |
mutate_graph_impl(MutableGraph& graph, dynamic_properties& dp,
|
williamr@2
|
692 |
std::string node_id_prop)
|
williamr@2
|
693 |
: graph_(graph), dp_(dp), node_id_prop_(node_id_prop) { }
|
williamr@2
|
694 |
|
williamr@2
|
695 |
~mutate_graph_impl() {}
|
williamr@2
|
696 |
|
williamr@2
|
697 |
bool is_directed() const
|
williamr@2
|
698 |
{
|
williamr@2
|
699 |
return
|
williamr@2
|
700 |
boost::is_convertible<
|
williamr@2
|
701 |
typename boost::graph_traits<MutableGraph>::directed_category,
|
williamr@2
|
702 |
boost::directed_tag>::value;
|
williamr@2
|
703 |
}
|
williamr@2
|
704 |
|
williamr@2
|
705 |
virtual void do_add_vertex(const node_t& node)
|
williamr@2
|
706 |
{
|
williamr@2
|
707 |
// Add the node to the graph.
|
williamr@2
|
708 |
bgl_vertex_t v = add_vertex(graph_);
|
williamr@2
|
709 |
|
williamr@2
|
710 |
// Set up a mapping from name to BGL vertex.
|
williamr@2
|
711 |
bgl_nodes.insert(std::make_pair(node, v));
|
williamr@2
|
712 |
|
williamr@2
|
713 |
// node_id_prop_ allows the caller to see the real id names for nodes.
|
williamr@2
|
714 |
put(node_id_prop_, dp_, v, node);
|
williamr@2
|
715 |
}
|
williamr@2
|
716 |
|
williamr@2
|
717 |
void
|
williamr@2
|
718 |
do_add_edge(const edge_t& edge, const node_t& source, const node_t& target)
|
williamr@2
|
719 |
{
|
williamr@2
|
720 |
std::pair<bgl_edge_t, bool> result =
|
williamr@2
|
721 |
add_edge(bgl_nodes[source], bgl_nodes[target], graph_);
|
williamr@2
|
722 |
|
williamr@2
|
723 |
if(!result.second) {
|
williamr@2
|
724 |
// In the case of no parallel edges allowed
|
williamr@2
|
725 |
throw bad_parallel_edge(source, target);
|
williamr@2
|
726 |
} else {
|
williamr@2
|
727 |
bgl_edges.insert(std::make_pair(edge, result.first));
|
williamr@2
|
728 |
}
|
williamr@2
|
729 |
}
|
williamr@2
|
730 |
|
williamr@2
|
731 |
void
|
williamr@2
|
732 |
set_node_property(const id_t& key, const node_t& node, const id_t& value)
|
williamr@2
|
733 |
{
|
williamr@2
|
734 |
put(key, dp_, bgl_nodes[node], value);
|
williamr@2
|
735 |
}
|
williamr@2
|
736 |
|
williamr@2
|
737 |
void
|
williamr@2
|
738 |
set_edge_property(const id_t& key, const edge_t& edge, const id_t& value)
|
williamr@2
|
739 |
{
|
williamr@2
|
740 |
put(key, dp_, bgl_edges[edge], value);
|
williamr@2
|
741 |
}
|
williamr@2
|
742 |
|
williamr@2
|
743 |
protected:
|
williamr@2
|
744 |
MutableGraph& graph_;
|
williamr@2
|
745 |
dynamic_properties& dp_;
|
williamr@2
|
746 |
std::string node_id_prop_;
|
williamr@2
|
747 |
std::map<node_t, bgl_vertex_t> bgl_nodes;
|
williamr@2
|
748 |
std::map<edge_t, bgl_edge_t> bgl_edges;
|
williamr@2
|
749 |
};
|
williamr@2
|
750 |
|
williamr@2
|
751 |
BOOST_GRAPH_DECL
|
williamr@2
|
752 |
bool read_graphviz(std::istream& in, mutate_graph& graph);
|
williamr@2
|
753 |
|
williamr@2
|
754 |
} } // end namespace detail::graph
|
williamr@2
|
755 |
|
williamr@2
|
756 |
// Parse the passed stream as a GraphViz dot file.
|
williamr@2
|
757 |
template <typename MutableGraph>
|
williamr@2
|
758 |
bool read_graphviz(std::istream& in, MutableGraph& graph,
|
williamr@2
|
759 |
dynamic_properties& dp,
|
williamr@2
|
760 |
std::string const& node_id = "node_id")
|
williamr@2
|
761 |
{
|
williamr@2
|
762 |
detail::graph::mutate_graph_impl<MutableGraph> m_graph(graph, dp, node_id);
|
williamr@2
|
763 |
return detail::graph::read_graphviz(in, m_graph);
|
williamr@2
|
764 |
}
|
williamr@2
|
765 |
|
williamr@2
|
766 |
} // namespace boost
|
williamr@2
|
767 |
|
williamr@2
|
768 |
#ifdef BOOST_GRAPH_READ_GRAPHVIZ_ITERATORS
|
williamr@2
|
769 |
# include <boost/graph/detail/read_graphviz_spirit.hpp>
|
williamr@2
|
770 |
#endif // BOOST_GRAPH_READ_GRAPHVIZ_ITERATORS
|
williamr@2
|
771 |
|
williamr@2
|
772 |
#endif // BOOST_GRAPHVIZ_HPP
|