ceph/src/boost/libs/graph/doc/read_graphviz.html

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