123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239 |
- <?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">
- <head>
- <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
- <meta name="generator" content="Docutils 0.6: http://docutils.sourceforge.net/" />
- <title>Boost read_graphviz</title>
- <link rel="stylesheet" href="../../../rst.css" type="text/css" />
- </head>
- <body>
- <div class="document" id="logo-read-graphviz">
- <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>
- <!-- Copyright (c) 2005-2009 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) -->
- <pre class="literal-block">
- namespace boost {
- template <typename MutableGraph>
- bool read_graphviz(std::istream& in, MutableGraph& graph,
- dynamic_properties& dp,
- const std::string& node_id = "node_id");
- template <typename MutableGraph>
- bool read_graphviz(std::string& str, MutableGraph& graph,
- dynamic_properties& dp,
- const std::string& node_id = "node_id");
- template <typename InputIterator, typename MutableGraph>
- bool read_graphviz(InputIterator begin, InputIterator end,
- MutableGraph& graph, dynamic_properties& dp,
- const std::string& node_id = "node_id");
- }
- </pre>
- <p>The <tt class="docutils literal"><span class="pre">read_graphviz</span></tt> function interprets a graph described using the
- <a class="reference external" href="http://graphviz.org/">GraphViz</a> DOT language and builds a BGL graph that captures that
- description. Using these functions, you can initialize a graph using
- data stored as text.</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 external" 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 <tt class="docutils literal"><span class="pre">node_id</span></tt>.</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 external" href="MutableGraph.html">Mutable Graph</a> concept.</li>
- <li>The type of the iterator must model the <a class="reference external" href="http://www.boost.org/sgi/stl/InputIterator.html">Input 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">Contents</p>
- <ul class="simple">
- <li><a class="reference internal" href="#where-defined" id="id2">Where Defined</a></li>
- <li><a class="reference internal" href="#exceptions" id="id3">Exceptions</a></li>
- <li><a class="reference internal" href="#example" id="id4">Example</a></li>
- <li><a class="reference internal" href="#building-the-graphviz-readers" id="id5">Building the GraphViz Readers</a></li>
- <li><a class="reference internal" href="#notes" id="id6">Notes</a></li>
- <li><a class="reference internal" href="#see-also" id="id7">See Also</a></li>
- <li><a class="reference internal" href="#future-work" id="id8">Future Work</a></li>
- </ul>
- </div>
- <div class="section" id="where-defined">
- <h1><a class="toc-backref" href="#id2">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">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();
- };
- struct bad_graphviz_syntax: public graph_exception {
- std::string errmsg;
- bad_graphviz_syntax(const std::string&);
- virtual ~bad_graphviz_syntax() 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>
- <p>The <tt class="docutils literal"><span class="pre">bad_graphviz_syntax</span></tt> exception occurs when the graph input is not a
- valid GraphViz graph.</p>
- </div>
- <div class="section" id="example">
- <h1><a class="toc-backref" href="#id4">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">Building the GraphViz Readers</a></h1>
- <p>To use the GraphViz readers, you will need to build and link against
- the "boost_graph" and "boost_regex" libraries. These libraries can be built by following the
- <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>
- </div>
- <div class="section" id="notes">
- <h1><a class="toc-backref" href="#id6">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>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. 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>
- <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>). This is the same behavior as GraphViz.</li>
- </ul>
- </blockquote>
- </div>
- <div class="section" id="see-also">
- <h1><a class="toc-backref" href="#id7">See Also</a></h1>
- <p><a class="reference external" href="write-graphviz.html">write_graphviz</a></p>
- </div>
- <div class="section" id="future-work">
- <h1><a class="toc-backref" href="#id8">Future Work</a></h1>
- <blockquote>
- <ul class="simple">
- <li>Passing port information to BGL.</li>
- <li>Expanding escape codes in the same way GraphViz does.</li>
- <li>Support for optional recognition of subgraphs as distinct entities.</li>
- </ul>
- </blockquote>
- </div>
- </div>
- <div class="footer">
- <hr class="footer" />
- Generated on: 2009-06-12 00:41 UTC.
- 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.
- </div>
- </body>
- </html>
|