]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | ||
37 | The ``read_graphviz`` function interprets a graph described using the | |
38 | GraphViz_ DOT language and builds a BGL graph that captures that | |
39 | description. Using these functions, you can initialize a graph using | |
40 | data stored as text. | |
41 | ||
42 | The 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; | |
45 | the same is true for directed graphs. Furthermore, ``read_graphviz`` | |
46 | will throw an exception if it encounters parallel edges and cannot add | |
47 | them to the graph. | |
48 | ||
49 | To handle properties expressed in the DOT language, ``read_graphviz`` | |
50 | takes a dynamic_properties_ object and operates on its collection of | |
51 | property maps. The reader passes all the properties encountered to | |
52 | this object, using the GraphViz string keys as the property keys. | |
53 | Furthermore, ``read_graphviz`` stores node identifier names under the | |
54 | vertex property map named ``node_id``. | |
55 | ||
56 | Requirements: | |
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 | ||
65 | Where Defined | |
66 | ------------- | |
67 | ``<boost/graph/graphviz.hpp>`` | |
68 | ||
69 | Exceptions | |
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 | ||
106 | Under certain circumstances, ``read_graphviz`` will throw one of the | |
107 | above exceptions. The three concrete exceptions can all be caught | |
108 | using the general ``graph_exception`` moniker when greater precision | |
109 | is not needed. In addition, all of the above exceptions derive from | |
110 | the standard ``std::exception`` for even more generalized error | |
111 | handling. | |
112 | ||
113 | The ``bad_parallel_edge`` exception is thrown when an attempt to add a | |
114 | parallel edge to the supplied MutableGraph fails. The DOT language | |
115 | supports parallel edges, but some BGL-compatible graph types do not. | |
116 | One example of such a graph is ``boost::adjacency_list<setS,vecS>``, | |
117 | which allows at most one edge can between any two vertices. | |
118 | ||
119 | ||
120 | The ``directed_graph_error`` exception occurs when an undirected graph | |
121 | type is passed to ``read_graph`` but the textual representation of the | |
122 | graph is directed, as indicated by the ``digraph`` keyword in the DOT | |
123 | language. | |
124 | ||
125 | The ``undirected_graph_error`` exception occurs when a directed graph | |
126 | type is passed to ``read_graph`` but the textual representation of the | |
127 | graph is undirected, as indicated by the ``graph`` keyword in the DOT | |
128 | language. | |
129 | ||
130 | The ``bad_graphviz_syntax`` exception occurs when the graph input is not a | |
131 | valid GraphViz graph. | |
132 | ||
133 | ||
134 | Example | |
135 | ------- | |
136 | The following example illustrates a relatively simple use of the | |
137 | GraphViz 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 | ||
182 | Building the GraphViz Readers | |
183 | ----------------------------- | |
184 | To use the GraphViz readers, you will need to build and link against | |
185 | the "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 | ||
189 | Notes | |
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 | ||
219 | See Also | |
220 | -------- | |
221 | ||
222 | write_graphviz_ | |
223 | ||
224 | ||
225 | Future 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 |