1============================
2|(logo)|__ ``read_graphviz``
3============================
4
5.. |(logo)| image:: ../../../boost.png
6   :align: middle
7   :alt: Boost
8
9.. Copyright (c) 2005-2009 Trustees of Indiana University
10    Distributed under the Boost Software License, Version 1.0.
11    (See accompanying file LICENSE_1_0.txt or copy at
12     http://www.boost.org/LICENSE_1_0.txt)
13__ ../../../index.htm
14
15::
16
17  namespace boost {
18
19    template <typename MutableGraph>
20    bool read_graphviz(std::istream& in, MutableGraph& graph,
21                       dynamic_properties& dp,
22                       const std::string& node_id = "node_id");
23
24    template <typename MutableGraph>
25    bool read_graphviz(std::string& str, MutableGraph& graph,
26                       dynamic_properties& dp,
27                       const std::string& node_id = "node_id");
28
29    template <typename InputIterator, typename MutableGraph>
30    bool read_graphviz(InputIterator begin, InputIterator end,
31                       MutableGraph& graph, dynamic_properties& dp,
32                       const std::string& node_id = "node_id");
33
34  }
35
36
37The ``read_graphviz`` function interprets a graph described using the
38GraphViz_ DOT language and builds a BGL graph that captures that
39description.  Using these functions, you can initialize a graph using
40data stored as text.
41
42The DOT language can specify both directed and undirected graphs, and
43``read_graphviz`` differentiates between the two. One must pass
44``read_graphviz`` an undirected graph when reading an undirected graph;
45the same is true for directed graphs. Furthermore, ``read_graphviz``
46will throw an exception if it encounters parallel edges and cannot add
47them to the graph.
48
49To handle properties expressed in the DOT language, ``read_graphviz``
50takes a dynamic_properties_ object and operates on its collection of
51property maps.  The reader passes all the properties encountered to
52this object, using the GraphViz string keys as the property keys.
53Furthermore, ``read_graphviz`` stores node identifier names under the
54vertex property map named ``node_id``.
55
56Requirements:
57 - The type of the graph must model the `Mutable Graph`_ concept.
58 - The type of the iterator must model the `Input Iterator`_
59   concept.
60 - The property map value types must be default-constructible.
61
62
63.. contents::
64
65Where Defined
66-------------
67``<boost/graph/graphviz.hpp>``
68
69Exceptions
70----------
71
72::
73
74  struct graph_exception : public std::exception {
75    virtual ~graph_exception() throw();
76    virtual const char* what() const throw() = 0;
77  };
78
79  struct bad_parallel_edge : public graph_exception {
80    std::string from;
81    std::string to;
82
83    bad_parallel_edge(const std::string&, const std::string&);
84    virtual ~bad_parallel_edge() throw();
85    const char* what() const throw();
86  };
87
88  struct directed_graph_error : public graph_exception {
89    virtual ~directed_graph_error() throw();
90    virtual const char* what() const throw();
91  };
92
93  struct undirected_graph_error : public graph_exception {
94    virtual ~undirected_graph_error() throw();
95    virtual const char* what() const throw();
96  };
97
98  struct bad_graphviz_syntax: public graph_exception {
99    std::string errmsg;
100
101    bad_graphviz_syntax(const std::string&);
102    virtual ~bad_graphviz_syntax() throw();
103    virtual const char* what() const throw();
104  };
105
106Under certain circumstances, ``read_graphviz`` will throw one of the
107above exceptions.  The three concrete exceptions can all be caught
108using the general ``graph_exception`` moniker when greater precision
109is not needed.  In addition, all of the above exceptions derive from
110the standard ``std::exception`` for even more generalized error
111handling.
112
113The ``bad_parallel_edge`` exception is thrown when an attempt to add a
114parallel edge to the supplied MutableGraph fails.  The DOT language
115supports parallel edges, but some BGL-compatible graph types do not.
116One example of such a graph is ``boost::adjacency_list<setS,vecS>``,
117which allows at most one edge can between any two vertices.
118
119
120The ``directed_graph_error`` exception occurs when an undirected graph
121type is passed to ``read_graph`` but the textual representation of the
122graph is directed, as indicated by the ``digraph`` keyword in the DOT
123language.
124
125The ``undirected_graph_error`` exception occurs when a directed graph
126type is passed to ``read_graph`` but the textual representation of the
127graph is undirected, as indicated by the ``graph`` keyword in the DOT
128language.
129
130The ``bad_graphviz_syntax`` exception occurs when the graph input is not a
131valid GraphViz graph.
132
133
134Example
135-------
136The following example illustrates a relatively simple use of the
137GraphViz reader to populate an ``adjacency_list`` graph
138
139::
140
141  // Vertex properties
142  typedef property < vertex_name_t, std::string,
143            property < vertex_color_t, float > > vertex_p;
144  // Edge properties
145  typedef property < edge_weight_t, double > edge_p;
146  // Graph properties
147  typedef property < graph_name_t, std::string > graph_p;
148  // adjacency_list-based type
149  typedef adjacency_list < vecS, vecS, directedS,
150    vertex_p, edge_p, graph_p > graph_t;
151
152  // Construct an empty graph and prepare the dynamic_property_maps.
153  graph_t graph(0);
154  dynamic_properties dp;
155
156  property_map<graph_t, vertex_name_t>::type name =
157    get(vertex_name, graph);
158  dp.property("node_id",name);
159
160  property_map<graph_t, vertex_color_t>::type mass =
161    get(vertex_color, graph);
162  dp.property("mass",mass);
163
164  property_map<graph_t, edge_weight_t>::type weight =
165    get(edge_weight, graph);
166  dp.property("weight",weight);
167
168  // Use ref_property_map to turn a graph property into a property map
169  boost::ref_property_map<graph_t*,std::string>
170    gname(get_property(graph,graph_name));
171  dp.property("name",gname);
172
173  // Sample graph as an std::istream;
174  std::istringstream
175    gvgraph("digraph { graph [name=\"graphname\"]  a  c e [mass = 6.66] }");
176
177  bool status = read_graphviz(gvgraph,graph,dp,"node_id");
178
179
180
181
182Building the GraphViz Readers
183-----------------------------
184To use the GraphViz readers, you will need to build and link against
185the "boost_graph" and "boost_regex" libraries. These libraries can be built by following the
186`Boost Jam Build Instructions`_ for the subdirectories ``libs/graph/build`` and ``libs/regex/build``.
187
188
189Notes
190-----
191
192 - The ``read_graphviz`` function does not use any code from the
193   GraphViz distribution to interpret the DOT Language.  Rather, the
194   implementation was based on documentation found on the GraphViz web
195   site, as well as experiments run using the dot application.  The
196   resulting interpretation may be subtly different from dot for some
197   corner cases that are not well specified.
198
199 - On successful reading of a graph, every vertex and edge will have
200   an associated value for every respective edge and vertex property
201   encountered while interpreting the graph.  These values will be set
202   using the ``dynamic_properties`` object.  Those edges and
203   vertices that are not explicitly given a value for a property (and that
204   property has no default) will be
205   given the default constructed value of the value type.  **Be sure
206   that property map value types are default constructible.**
207
208 - ``read_graphviz`` treats subgraphs as syntactic sugar.  It does not
209   reflect subgraphs as actual entities in the BGL.  Rather, they are
210   used to shorten some edge definitions as well as to give a subset
211   of all nodes or edges certain properties. For example, the
212   DOT graphs ``digraph { a -> subgraph {b -> c} -> e }`` and
213   ``digraph { a -> b -> e ; a -> c -> e ; b -> c}`` are equivalent.
214
215 - Subgraph IDs refer to subgraphs defined earlier in the graph
216   description.  Undefined subgraphs behave as empty subgraphs
217   (``{}``).  This is the same behavior as GraphViz.
218
219See Also
220--------
221
222write_graphviz_
223
224
225Future Work
226-----------
227
228 - Passing port information to BGL.
229
230 - Expanding escape codes in the same way GraphViz does.
231
232 - Support for optional recognition of subgraphs as distinct entities.
233
234
235.. _GraphViz: http://graphviz.org/
236.. _`Mutable Graph`: MutableGraph.html
237.. _`Input Iterator`: http://www.sgi.com/tech/stl/InputIterator.html
238.. _dynamic_properties: ../../property_map/doc/dynamic_property_map.html
239.. _write_graphviz: write-graphviz.html
240.. _Boost Jam Build Instructions: ../../../more/getting_started.html#Build_Install
241