1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
|
<?xml version="1.0" encoding="utf-8" ?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
<!--
-- Copyright (c) 2005 Trustees of Indiana University
--
-- Distributed under the Boost Software License, Version 1.0.
-- (See accompanying file LICENSE_1_0.txt or copy at
-- http://www.boost.org/LICENSE_1_0.txt)
-->
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<meta name="generator" content="Docutils 0.3.8: http://docutils.sourceforge.net/" />
<title>Boost read_graphviz</title>
<link rel="stylesheet" href="default.css" type="text/css" />
</head>
<body>
<div class="document" id="logo-read-graphviz">
<h1 class="title"><a class="reference" href="../../../index.htm"><img align="middle" alt="Boost" src="../../../boost.png" /></a> <tt class="docutils literal"><span class="pre">read_graphviz</span></tt></h1>
<pre class="literal-block">
template <typename MutableGraph>
bool read_graphviz(std::istream& in, MutableGraph& graph,
dynamic_properties& dp,
const std::string& node_id = "node_id");
// Only available if BOOST_GRAPH_READ_GRAPHVIZ_ITERATORS is defined
template <typename MultiPassIterator, typename MutableGraph>
bool read_graphviz(MultiPassIterator begin, MultiPassIterator end,
MutableGraph& graph, dynamic_properties& dp,
const std::string& node_id = "node_id");
// Deprecated GraphViz readers
void read_graphviz(const std::string& file, GraphvizDigraph& g);
void read_graphviz(FILE* file, GraphvizDigraph& g);
void read_graphviz(const std::string& file, GraphvizGraph& g);
void read_graphviz(FILE* file, GraphvizGraph& g);
</pre>
<p>The <tt class="docutils literal"><span class="pre">read_graphviz</span></tt> function interprets a graph described using the
<a class="reference" href="http://graphviz.org/">GraphViz</a> DOT language and builds a BGL graph that captures that
description. Using this function, you can initialize a graph using
data stored as text. To use the iterator version of <tt class="docutils literal"><span class="pre">read_graphviz</span></tt>,
you will need to define the macro BOOST_GRAPH_READ_GRAPHVIZ_ITERATORS
before including the header <tt class="docutils literal"><span class="pre"><boost/graph/graphviz.hpp></span></tt>. Doing so
may greatly increase the amount of time required to compile the
GraphViz reader.</p>
<p>The DOT language can specify both directed and undirected graphs, and
<tt class="docutils literal"><span class="pre">read_graphviz</span></tt> differentiates between the two. One must pass
<tt class="docutils literal"><span class="pre">read_graphviz</span></tt> an undirected graph when reading an undirected graph;
the same is true for directed graphs. Furthermore, <tt class="docutils literal"><span class="pre">read_graphviz</span></tt>
will throw an exception if it encounters parallel edges and cannot add
them to the graph.</p>
<p>To handle properties expressed in the DOT language, <tt class="docutils literal"><span class="pre">read_graphviz</span></tt>
takes a <a class="reference" href="../../property_map/doc/dynamic_property_map.html">dynamic_properties</a> object and operates on its collection of
property maps. The reader passes all the properties encountered to
this object, using the GraphViz string keys as the property keys.
Furthermore, <tt class="docutils literal"><span class="pre">read_graphviz</span></tt> stores node identifier names under the
vertex property map named node_id.</p>
<dl class="docutils">
<dt>Requirements:</dt>
<dd><ul class="first last simple">
<li>The type of the graph must model the <a class="reference" href="MutableGraph.html">Mutable Graph</a> concept.</li>
<li>The type of the iterator must model the <a class="reference" href="../../iterator/index.html">Multi-Pass Iterator</a>
concept.</li>
<li>The property map value types must be default-constructible.</li>
</ul>
</dd>
</dl>
<div class="contents topic" id="contents">
<p class="topic-title first"><a name="contents">Contents</a></p>
<ul class="simple">
<li><a class="reference" href="#where-defined" id="id2" name="id2">Where Defined</a></li>
<li><a class="reference" href="#exceptions" id="id3" name="id3">Exceptions</a></li>
<li><a class="reference" href="#example" id="id4" name="id4">Example</a></li>
<li><a class="reference" href="#building-the-graphviz-readers" id="id5" name="id5">Building the GraphViz Readers</a></li>
<li><a class="reference" href="#deprecated-readers" id="id6" name="id6">Deprecated Readers</a></li>
<li><a class="reference" href="#notes" id="id7" name="id7">Notes</a></li>
<li><a class="reference" href="#see-also" id="id8" name="id8">See Also</a></li>
<li><a class="reference" href="#future-work" id="id9" name="id9">Future Work</a></li>
</ul>
</div>
<div class="section" id="where-defined">
<h1><a class="toc-backref" href="#id2" name="where-defined">Where Defined</a></h1>
<p><tt class="docutils literal"><span class="pre"><boost/graph/graphviz.hpp></span></tt></p>
</div>
<div class="section" id="exceptions">
<h1><a class="toc-backref" href="#id3" name="exceptions">Exceptions</a></h1>
<pre class="literal-block">
struct graph_exception : public std::exception {
virtual ~graph_exception() throw();
virtual const char* what() const throw() = 0;
};
struct bad_parallel_edge : public graph_exception {
std::string from;
std::string to;
bad_parallel_edge(const std::string&, const std::string&);
virtual ~bad_parallel_edge() throw();
const char* what() const throw();
};
struct directed_graph_error : public graph_exception {
virtual ~directed_graph_error() throw();
virtual const char* what() const throw();
};
struct undirected_graph_error : public graph_exception {
virtual ~undirected_graph_error() throw();
virtual const char* what() const throw();
};
</pre>
<p>Under certain circumstances, <tt class="docutils literal"><span class="pre">read_graphviz</span></tt> will throw one of the
above exceptions. The three concrete exceptions can all be caught
using the general <tt class="docutils literal"><span class="pre">graph_exception</span></tt> moniker when greater precision
is not needed. In addition, all of the above exceptions derive from
the standard <tt class="docutils literal"><span class="pre">std::exception</span></tt> for even more generalized error
handling.</p>
<p>The <tt class="docutils literal"><span class="pre">bad_parallel_edge</span></tt> exception is thrown when an attempt to add a
parallel edge to the supplied MutableGraph fails. The DOT language
supports parallel edges, but some BGL-compatible graph types do not.
One example of such a graph is <tt class="docutils literal"><span class="pre">boost::adjacency_list<setS,vecS></span></tt>,
which allows at most one edge can between any two vertices.</p>
<p>The <tt class="docutils literal"><span class="pre">directed_graph_error</span></tt> exception occurs when an undirected graph
type is passed to <tt class="docutils literal"><span class="pre">read_graph</span></tt> but the textual representation of the
graph is directed, as indicated by the <tt class="docutils literal"><span class="pre">digraph</span></tt> keyword in the DOT
language.</p>
<p>The <tt class="docutils literal"><span class="pre">undirected_graph_error</span></tt> exception occurs when a directed graph
type is passed to <tt class="docutils literal"><span class="pre">read_graph</span></tt> but the textual representation of the
graph is undirected, as indicated by the <tt class="docutils literal"><span class="pre">graph</span></tt> keyword in the DOT
language.</p>
</div>
<div class="section" id="example">
<h1><a class="toc-backref" href="#id4" name="example">Example</a></h1>
<p>The following example illustrates a relatively simple use of the
GraphViz reader to populate an <tt class="docutils literal"><span class="pre">adjacency_list</span></tt> graph</p>
<pre class="literal-block">
// Vertex properties
typedef property < vertex_name_t, std::string,
property < vertex_color_t, float > > vertex_p;
// Edge properties
typedef property < edge_weight_t, double > edge_p;
// Graph properties
typedef property < graph_name_t, std::string > graph_p;
// adjacency_list-based type
typedef adjacency_list < vecS, vecS, directedS,
vertex_p, edge_p, graph_p > graph_t;
// Construct an empty graph and prepare the dynamic_property_maps.
graph_t graph(0);
dynamic_properties dp;
property_map<graph_t, vertex_name_t>::type name =
get(vertex_name, graph);
dp.property("node_id",name);
property_map<graph_t, vertex_color_t>::type mass =
get(vertex_color, graph);
dp.property("mass",mass);
property_map<graph_t, edge_weight_t>::type weight =
get(edge_weight, graph);
dp.property("weight",weight);
// Use ref_property_map to turn a graph property into a property map
boost::ref_property_map<graph_t*,std::string>
gname(get_property(graph,graph_name));
dp.property("name",gname);
// Sample graph as an std::istream;
std::istringstream
gvgraph("digraph { graph [name=\"graphname\"] a c e [mass = 6.66] }");
bool status = read_graphviz(gvgraph,graph,dp,"node_id");
</pre>
</div>
<div class="section" id="building-the-graphviz-readers">
<h1><a class="toc-backref" href="#id5" name="building-the-graphviz-readers">Building the GraphViz Readers</a></h1>
<p>To use the GraphViz readers, you will need to build and link against
the "boost_graph" library. The library can be built by following the
<a class="reference" href="../../../doc/html/bbv2/installation.html">Boost Jam Build Instructions</a> for the subdirectory <tt class="docutils literal"><span class="pre">libs/graph/build</span></tt>.</p>
</div>
<div class="section" id="deprecated-readers">
<h1><a class="toc-backref" href="#id6" name="deprecated-readers">Deprecated Readers</a></h1>
<p>The deprecated readers do not provide exceptions on error (they
abort), they require the use of one of the predefined graph types
(<tt class="docutils literal"><span class="pre">GraphvizDigraph</span></tt> or <tt class="docutils literal"><span class="pre">GraphvizGraph</span></tt>), and they do not support
arbitrary properties. They will be removed in a future Boost version.</p>
</div>
<div class="section" id="notes">
<h1><a class="toc-backref" href="#id7" name="notes">Notes</a></h1>
<blockquote>
<ul class="simple">
<li>The <tt class="docutils literal"><span class="pre">read_graphviz</span></tt> function does not use any code from the
GraphViz distribution to interpret the DOT Language. Rather, the
implementation was based on documentation found on the GraphViz web
site, as well as experiments run using the dot application. The
resulting interpretation may be subtly different from dot for some
corner cases that are not well specified.</li>
<li><tt class="docutils literal"><span class="pre">read_graphviz</span></tt> treats subgraphs as syntactic sugar. It does not
reflect subgraphs as actual entities in the BGL. Rather, they are
used to shorten some edge definitions as well as to give a subset
of all nodes or edges certain properties. For example, the
DOT graphs <tt class="docutils literal"><span class="pre">digraph</span> <span class="pre">{</span> <span class="pre">a</span> <span class="pre">-></span> <span class="pre">subgraph</span> <span class="pre">{b</span> <span class="pre">-></span> <span class="pre">c}</span> <span class="pre">-></span> <span class="pre">e</span> <span class="pre">}</span></tt> and
<tt class="docutils literal"><span class="pre">digraph</span> <span class="pre">{</span> <span class="pre">a</span> <span class="pre">-></span> <span class="pre">b</span> <span class="pre">-></span> <span class="pre">e</span> <span class="pre">;</span> <span class="pre">a</span> <span class="pre">-></span> <span class="pre">c</span> <span class="pre">-></span> <span class="pre">e</span> <span class="pre">;</span> <span class="pre">b</span> <span class="pre">-></span> <span class="pre">c}</span></tt> are equivalent.</li>
<li>Subgraph IDs refer to subgraphs defined earlier in the graph
description. Undefined subgraphs behave as empty subgraphs
(<tt class="docutils literal"><span class="pre">{}</span></tt>).</li>
<li>On successful reading of a graph, every vertex and edge will have
an associated value for every respective edge and vertex property
encountered while interpreting the graph. These values will be set
using the <tt class="docutils literal"><span class="pre">dynamic_properties</span></tt> object. Some properties may be
<tt class="docutils literal"><span class="pre">put</span></tt> multiple times during the course of reading in order to
ensure the same semantics as the GraphViz tools. Those edges and
vertices that are not explicitly given a value for a property (and that
property has no default) will be
given the default constructed value of the value type. <strong>Be sure
that property map value types are default constructible.</strong></li>
</ul>
</blockquote>
</div>
<div class="section" id="see-also">
<h1><a class="toc-backref" href="#id8" name="see-also">See Also</a></h1>
<p><a class="reference" href="write-graphviz.html">write_graphviz</a></p>
</div>
<div class="section" id="future-work">
<h1><a class="toc-backref" href="#id9" name="future-work">Future Work</a></h1>
<blockquote>
<ul class="simple">
<li>The parser currently does not handle continuation lines as defined
in the DOT Language. Some more sophisticated parsing of
identifier(so-called "ID" in the source) is required to support this.</li>
<li>Support for optional recognition of subgraphs as distinct entities.</li>
</ul>
</blockquote>
</div>
</div>
</body>
</html>
|
