Subject: [Boost-commit] svn:boost r53092 - in trunk: boost/graph boost/graph/detail libs/graph/doc libs/graph/src libs/graph/test
From: jewillco_at_[hidden]
Date: 2009-05-18 13:27:16
Author: jewillco
Date: 2009-05-18 13:27:15 EDT (Mon, 18 May 2009)
New Revision: 53092
URL: http://svn.boost.org/trac/boost/changeset/53092
Log:
Added new Graphviz parser (recursive descent); does not support subgraphs in edges yet
Added:
trunk/boost/graph/detail/read_graphviz_new.hpp (contents, props changed)
Text files modified:
trunk/boost/graph/graphviz.hpp | 17 +
trunk/libs/graph/doc/read_graphviz.html | 420 ++++++++++++++++++++++++++++++++-------
trunk/libs/graph/doc/read_graphviz.rst | 98 ++++----
trunk/libs/graph/src/read_graphviz_spirit.cpp | 26 --
trunk/libs/graph/test/Jamfile.v2 | 5
trunk/libs/graph/test/graphviz_test.cpp | 56 +++--
6 files changed, 447 insertions(+), 175 deletions(-)
Added: trunk/boost/graph/detail/read_graphviz_new.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/graph/detail/read_graphviz_new.hpp 2009-05-18 13:27:15 EDT (Mon, 18 May 2009)
@@ -0,0 +1,699 @@
+// Copyright 2004-9 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)
+
+//
+// read_graphviz_new.hpp -
+// Initialize a model of the BGL's MutableGraph concept and an associated
+// collection of property maps using a graph expressed in the GraphViz
+// DOT Language.
+//
+// Based on the grammar found at:
+// http://www.graphviz.org/cvs/doc/info/lang.html
+//
+// Jeremiah rewrite used grammar found at:
+// http://www.graphviz.org/doc/info/lang.html
+// and page 34 or http://www.graphviz.org/pdf/dotguide.pdf
+//
+// See documentation for this code at:
+// http://www.boost.org/libs/graph/doc/read-graphviz.html
+//
+
+// Author: Jeremiah Willcock
+// Ronald Garcia
+//
+
+#ifndef BOOST_READ_GRAPHVIZ_NEW_HPP
+#define BOOST_READ_GRAPHVIZ_NEW_HPP
+
+#include <boost/ref.hpp>
+#include <boost/function/function2.hpp>
+#include <boost/property_map/dynamic_property_map.hpp>
+#include <boost/graph/graph_traits.hpp>
+#include <boost/detail/workaround.hpp>
+#include <boost/algorithm/string/case_conv.hpp>
+#include <algorithm>
+#include <exception> // for std::exception
+#include <string>
+#include <vector>
+#include <set>
+#include <utility>
+#include <map>
+#include <iostream>
+#include <cstdlib>
+#include <boost/graph/graphviz.hpp>
+#include <boost/throw_exception.hpp>
+#include <boost/regex.hpp>
+#include <boost/function.hpp>
+#include <boost/bind.hpp>
+
+namespace boost {
+
+namespace read_graphviz_detail {
+ struct token {
+ enum token_type {
+ kw_strict,
+ kw_graph,
+ kw_digraph,
+ kw_node,
+ kw_edge,
+ kw_subgraph,
+ left_brace,
+ right_brace,
+ semicolon,
+ equal,
+ left_bracket,
+ right_bracket,
+ comma,
+ colon,
+ dash_greater,
+ dash_dash,
+ plus,
+ left_paren,
+ right_paren,
+ at,
+ identifier,
+ quoted_string, // Only used internally in tokenizer
+ eof,
+ invalid
+ } type;
+ std::string normalized_value; // May have double-quotes removed and/or some escapes replaced
+ token(token_type type, const std::string& normalized_value)
+ : type(type), normalized_value(normalized_value) {}
+ token(): type(invalid), normalized_value("") {}
+ friend std::ostream& operator<<(std::ostream& o, const token& t) {
+ switch (t.type) {
+ case token::kw_strict: o << "<strict>"; break;
+ case token::kw_graph: o << "<graph>"; break;
+ case token::kw_digraph: o << "<digraph>"; break;
+ case token::kw_node: o << "<node>"; break;
+ case token::kw_edge: o << "<edge>"; break;
+ case token::kw_subgraph: o << "<subgraph>"; break;
+ case token::left_brace: o << "<left_brace>"; break;
+ case token::right_brace: o << "<right_brace>"; break;
+ case token::semicolon: o << "<semicolon>"; break;
+ case token::equal: o << "<equal>"; break;
+ case token::left_bracket: o << "<left_bracket>"; break;
+ case token::right_bracket: o << "<right_bracket>"; break;
+ case token::comma: o << "<comma>"; break;
+ case token::colon: o << "<colon>"; break;
+ case token::dash_greater: o << "<dash-greater>"; break;
+ case token::dash_dash: o << "<dash-dash>"; break;
+ case token::plus: o << "<plus>"; break;
+ case token::left_paren: o << "<left_paren>"; break;
+ case token::right_paren: o << "<right_paren>"; break;
+ case token::at: o << "<at>"; break;
+ case token::identifier: o << "<identifier>"; break;
+ case token::quoted_string: o << "<quoted_string>"; break;
+ case token::eof: o << "<eof>"; break;
+ default: o << "<invalid type>"; break;
+ }
+ o << " '" << t.normalized_value << "'";
+ return o;
+ }
+ };
+
+ struct lex_error: public std::exception {
+ std::string errmsg;
+ char bad_char;
+ lex_error(const std::string& errmsg, char bad_char): errmsg(errmsg), bad_char(bad_char) {
+ this->errmsg += std::string(" (char is '") + bad_char + "')";
+ }
+ const char* what() const throw () {return errmsg.c_str();}
+ ~lex_error() throw () {};
+ };
+
+ struct parse_error: public std::exception {
+ std::string errmsg;
+ token bad_token;
+ parse_error(const std::string& errmsg, const token& bad_token): errmsg(errmsg), bad_token(bad_token) {
+ this->errmsg += std::string(" (token is \"") + boost::lexical_cast<std::string>(bad_token) + "\")";
+ }
+ const char* what() const throw () {return errmsg.c_str();}
+ ~parse_error() throw () {};
+ };
+
+ template <typename BidirectionalIterator>
+ struct tokenizer {
+ BidirectionalIterator begin, end;
+ std::vector<token> lookahead;
+ // Precomputed regexes
+ boost::regex stuff_to_skip;
+ boost::regex basic_id_token;
+ boost::regex punctuation_token;
+ boost::regex number_token;
+ boost::regex quoted_string_token;
+
+ tokenizer(BidirectionalIterator begin, BidirectionalIterator end)
+ : begin(begin), end(end)
+ {
+ std::string end_of_token = "(?=(?:\\W))";
+ std::string whitespace = "(?:\\s+)";
+ std::string slash_slash_comment = "(?://.*$)";
+ std::string slash_star_comment = "(?:/\\*.*?\\*/)";
+ std::string hash_comment = "(?:^#.*?$)";
+ stuff_to_skip = "\\A(?:" + whitespace + "|" + slash_slash_comment + "|" + slash_star_comment + "|" + hash_comment + ")*";
+ basic_id_token = "\\A([[:alpha:]_](?:\\w*))";
+ punctuation_token = "\\A([][{};=,:+()@]|[-][>-])";
+ number_token = "\\A([-]?(?:(?:\\.\\d+)|(?:\\d+(?:\\.\\d*)?)))";
+ quoted_string_token = "\\A(\"(?:[^\"\\\\]|(?:[\\\\].))*\")";
+ }
+
+ void skip() {
+ boost::match_results<BidirectionalIterator> results;
+ bool found = boost::regex_search(begin, end, results, stuff_to_skip);
+ assert (found);
+ boost::sub_match<BidirectionalIterator> sm1 = results.suffix();
+ assert (sm1.second == end);
+ begin = sm1.first;
+ }
+
+ token get_token_raw() {
+ if (!lookahead.empty()) {
+ token t = lookahead.front();
+ lookahead.erase(lookahead.begin());
+ return t;
+ }
+ skip();
+ if (begin == end) return token(token::eof, "");
+ // Look for keywords first
+ bool found;
+ boost::match_results<BidirectionalIterator> results;
+ found = boost::regex_search(begin, end, results, basic_id_token);
+ if (found) {
+ std::string str = results[1].str();
+ std::string str_lower = boost::algorithm::to_lower_copy(str);
+ begin = results.suffix().first;
+ if (str_lower == "strict") {
+ return token(token::kw_strict, str);
+ } else if (str_lower == "graph") {
+ return token(token::kw_graph, str);
+ } else if (str_lower == "digraph") {
+ return token(token::kw_digraph, str);
+ } else if (str_lower == "node") {
+ return token(token::kw_node, str);
+ } else if (str_lower == "edge") {
+ return token(token::kw_edge, str);
+ } else if (str_lower == "subgraph") {
+ return token(token::kw_subgraph, str);
+ } else {
+ return token(token::identifier, str);
+ }
+ }
+ found = boost::regex_search(begin, end, results, punctuation_token);
+ if (found) {
+ std::string str = results[1].str();
+ begin = results.suffix().first;
+ switch (str[0]) {
+ case '[': return token(token::left_bracket, str);
+ case ']': return token(token::right_bracket, str);
+ case '{': return token(token::left_brace, str);
+ case '}': return token(token::right_brace, str);
+ case ';': return token(token::semicolon, str);
+ case '=': return token(token::equal, str);
+ case ',': return token(token::comma, str);
+ case ':': return token(token::colon, str);
+ case '+': return token(token::plus, str);
+ case '(': return token(token::left_paren, str);
+ case ')': return token(token::right_paren, str);
+ case '@': return token(token::at, str);
+ case '-': {
+ switch (str[1]) {
+ case '-': return token(token::dash_dash, str);
+ case '>': return token(token::dash_greater, str);
+ default: assert (!"Definition of punctuation_token does not match switch statement");
+ }
+ }
+ default: assert (!"Definition of punctuation_token does not match switch statement"); std::abort();
+ }
+ }
+ found = boost::regex_search(begin, end, results, number_token);
+ if (found) {
+ std::string str = results[1].str();
+ begin = results.suffix().first;
+ return token(token::identifier, str);
+ }
+ found = boost::regex_search(begin, end, results, quoted_string_token);
+ if (found) {
+ std::string str = results[1].str();
+ begin = results.suffix().first;
+ // Remove the beginning and ending quotes
+ assert (str.size() >= 2);
+ str.erase(str.begin());
+ str.erase(str.end() - 1);
+ // Unescape quotes in the middle, but nothing else (see format spec)
+ for (size_t i = 0; i + 1 < str.size() /* May change */; ++i) {
+ if (str[i] == '\\' && str[i + 1] == '"') {
+ str.erase(str.begin() + i);
+ // Don't need to adjust i
+ } else if (str[i] == '\\' && str[i + 1] == '\n') {
+ str.erase(str.begin() + i);
+ str.erase(str.begin() + i);
+ --i; // Invert ++ that will be applied
+ }
+ }
+ return token(token::quoted_string, str);
+ }
+ if (*begin == '<') {
+ throw_lex_error("HTML strings not supported");
+ return token();
+ } else {
+ throw_lex_error("Invalid character");
+ return token();
+ }
+ }
+
+ token peek_token_raw() {
+ if (lookahead.empty()) {
+ token t = get_token_raw();
+ lookahead.push_back(t);
+ }
+ return lookahead.front();
+ }
+
+ token get_token() { // Handle string concatenation
+ token t = get_token_raw();
+ if (t.type != token::quoted_string) return t;
+ std::string str = t.normalized_value;
+ while (peek_token_raw().type == token::plus) {
+ get_token_raw();
+ token t2 = get_token_raw();
+ if (t2.type != token::quoted_string) {
+ throw_lex_error("Must have quoted string after string concatenation");
+ }
+ str += t2.normalized_value;
+ }
+ return token(token::identifier, str); // Note that quoted_string does not get passed to the parser
+ }
+
+ void throw_lex_error(const std::string& errmsg) {
+ boost::throw_exception(lex_error(errmsg, *begin));
+ }
+ };
+
+ typedef std::map<std::string, std::string> properties;
+
+ struct node_id {
+ std::string name;
+ std::string angle; // Or empty if no angle
+ std::vector<std::string> location; // Up to two identifiers
+ };
+
+ // Parser policy object should have the following methods:
+ // struct parser_policy {
+ // void do_node(const node_id& n, const properties& default_props, const properties& custom_props);
+ // void do_edge(const node_id& a, const node_id& b, const properties& props);
+ // void do_begin_graph(bool is_strict, bool is_directed, const std::string& name);
+ // void do_end_graph(const properties& props);
+ // void do_begin_subgraph(const std::string& name);
+ // void do_end_subgraph(const properties& props);
+ // };
+
+ template <typename BidirectionalIterator, typename Policy>
+ struct parser {
+ tokenizer<BidirectionalIterator> tokenizer;
+ std::vector<token> lookahead;
+ bool graph_is_directed;
+ properties graph_props;
+ properties node_props;
+ properties edge_props;
+ Policy hooks;
+
+ parser(BidirectionalIterator begin, BidirectionalIterator end, Policy hooks)
+ : tokenizer(begin, end), lookahead(), hooks(hooks) {}
+
+ token get() {
+ if (lookahead.empty()) {
+ token t = tokenizer.get_token();
+ return t;
+ } else {
+ token t = lookahead.front();
+ lookahead.erase(lookahead.begin());
+ return t;
+ }
+ }
+
+ token peek() {
+ if (lookahead.empty()) {
+ lookahead.push_back(tokenizer.get_token());
+ }
+ return lookahead.front();
+ }
+
+ void error(const std::string& str) {
+ boost::throw_exception(parse_error(str, peek()));
+ }
+
+ void parse_graph(bool want_directed) {
+ bool is_strict = false;
+ bool is_directed;
+ std::string name;
+ if (peek().type == token::kw_strict) {get(); is_strict = true;}
+ switch (peek().type) {
+ case token::kw_graph: is_directed = false; break;
+ case token::kw_digraph: is_directed = true; break;
+ default: error("Wanted \"graph\" or \"digraph\"");
+ }
+ graph_is_directed = is_directed; // Used to check edges
+ if (want_directed != graph_is_directed) {
+ if (want_directed) {
+ boost::throw_exception(boost::undirected_graph_error());
+ } else {
+ boost::throw_exception(boost::directed_graph_error());
+ }
+ }
+ hooks.do_begin_graph(is_strict, is_directed, name);
+ get();
+ switch (peek().type) {
+ case token::identifier: name = peek().normalized_value; get(); break;
+ case token::left_brace: break;
+ default: error("Wanted a graph name or left brace");
+ }
+ if (peek().type == token::left_brace) get(); else error("Wanted a left brace to start the graph");
+ parse_stmt_list();
+ if (peek().type == token::right_brace) get(); else error("Wanted a right brace to end the graph");
+ hooks.do_end_graph(graph_props);
+ if (peek().type == token::eof) {} else error("Wanted end of file");
+ }
+
+ void parse_stmt_list() {
+ while (true) {
+ if (peek().type == token::right_brace) return;
+ parse_stmt();
+ if (peek().type == token::semicolon) get();
+ }
+ }
+
+ void parse_stmt() {
+ switch (peek().type) {
+ case token::kw_node:
+ case token::kw_edge:
+ case token::kw_graph: parse_attr_stmt(); break;
+ case token::kw_subgraph:
+ case token::left_brace: parse_subgraph(); break;
+ case token::identifier: {
+ token id = get();
+ switch (peek().type) {
+ case token::dash_dash:
+ case token::dash_greater: {
+ node_id n = parse_node_id_rest(id);
+ parse_edge_stmt(n);
+ break;
+ }
+ case token::equal: {
+ get();
+ if (peek().type != token::identifier) error("Wanted identifier as right side of =");
+ token id2 = get();
+ graph_props[id.normalized_value] = id2.normalized_value;
+ break;
+ }
+ default: {
+ node_id n = parse_node_id_rest(id);
+ parse_node_stmt(n);
+ break;
+ }
+ }
+ break;
+ }
+ default: error("Invalid start token for statement");
+ }
+ }
+
+ void parse_attr_stmt() {
+ switch (get().type) {
+ case token::kw_graph: parse_attr_list(graph_props); break;
+ case token::kw_node: parse_attr_list(node_props); break;
+ case token::kw_edge: parse_attr_list(edge_props); break;
+ default: assert (!"Bad attr_stmt case"); std::abort();
+ }
+ }
+
+ void parse_subgraph() {
+ std::string name;
+ if (peek().type == token::kw_subgraph) {
+ get();
+ if (peek().type == token::identifier) {
+ name = get().normalized_value;
+ }
+ }
+ properties saved_node_props = node_props;
+ properties saved_edge_props = edge_props;
+ properties saved_graph_props = graph_props;
+ if (peek().type != token::left_brace) {
+ if (name.empty()) error("Subgraph reference needs a name");
+ hooks.do_subgraph_reference(name);
+ return;
+ }
+ hooks.do_begin_subgraph(name);
+ if (peek().type == token::left_brace) get(); else error("Wanted left brace to start subgraph");
+ parse_stmt_list();
+ if (peek().type == token::right_brace) get(); else error("Wanted right brace to end subgraph");
+ hooks.do_end_subgraph(graph_props);
+ node_props = saved_node_props;
+ edge_props = saved_edge_props;
+ graph_props = saved_graph_props;
+ if (peek().type == token::dash_greater ||
+ peek().type == token::dash_dash) { // FIXME
+ std::cerr << "FIXME: Subgraphs in edges are not supported" << std::endl;
+ error("Unsupported subgraph edge case");
+ }
+ }
+
+ node_id parse_node_id_rest(const token& name) {
+ // A node ID is a node name, followed optionally by a port angle and a
+ // port location (in either order); a port location is either :id,
+ // :id:id, or :(id,id); the last two forms are treated as equivalent
+ // although I am not sure about that.
+ node_id id;
+ id.name = name.normalized_value;
+ parse_more:
+ switch (peek().type) {
+ case token::at: {
+ get();
+ if (peek().type != token::identifier) error("Wanted identifier as port angle");
+ if (id.angle != "") error("Duplicate port angle");
+ id.angle = get().normalized_value;
+ goto parse_more;
+ }
+ case token::colon: {
+ get();
+ if (!id.location.empty()) error("Duplicate port location");
+ switch (peek().type) {
+ case token::identifier: {
+ id.location.push_back(get().normalized_value);
+ switch (peek().type) {
+ case token::colon: {
+ get();
+ if (peek().type != token::identifier) error("Wanted identifier as port location");
+ id.location.push_back(get().normalized_value);
+ goto parse_more;
+ }
+ default: goto parse_more;
+ }
+ }
+ case token::left_paren: {
+ get();
+ if (peek().type != token::identifier) error("Wanted identifier as first element of port location");
+ id.location.push_back(get().normalized_value);
+ if (peek().type != token::comma) error("Wanted comma between parts of port location");
+ get();
+ if (peek().type != token::identifier) error("Wanted identifier as second element of port location");
+ id.location.push_back(get().normalized_value);
+ if (peek().type != token::right_paren) error("Wanted right parenthesis to close port location");
+ get();
+ goto parse_more;
+ }
+ default: error("Wanted identifier or left parenthesis as start of port location");
+ }
+ }
+ default: break;
+ }
+ return id;
+ }
+
+ node_id parse_node_id() {
+ if (peek().type != token::identifier) error("Wanted identifier as node name (subgraphs not supported yet)");
+ token name = get();
+ return parse_node_id_rest(name);
+ }
+
+ void parse_node_stmt(const node_id& n) {
+ properties this_node_props;
+ if (peek().type == token::left_bracket) parse_attr_list(this_node_props);
+ hooks.do_node(n, node_props, this_node_props);
+ }
+
+ void parse_edge_stmt(const node_id& lhs) {
+ std::vector<node_id> nodes_in_chain(1, lhs);
+ while (true) {
+ bool leave_loop = true;
+ switch (peek().type) {
+ case token::dash_dash: {
+ if (graph_is_directed) error("Using -- in directed graph");
+ get();
+ nodes_in_chain.push_back(parse_node_id());
+ leave_loop = false;
+ break;
+ }
+ case token::dash_greater: {
+ if (!graph_is_directed) error("Using -> in undirected graph");
+ get();
+ nodes_in_chain.push_back(parse_node_id());
+ leave_loop = false;
+ break;
+ }
+ default: leave_loop = true; break;
+ }
+ if (leave_loop) break;
+ }
+ properties this_edge_props = edge_props;
+ if (peek().type == token::left_bracket) parse_attr_list(this_edge_props);
+ assert (nodes_in_chain.size() >= 2); // Should be in node parser otherwise
+ for (size_t i = 0; i + 1 < nodes_in_chain.size(); ++i) {
+ hooks.do_edge(nodes_in_chain[i], nodes_in_chain[i + 1], this_edge_props);
+ }
+ }
+
+ void parse_attr_list(properties& props) {
+ while (true) {
+ if (peek().type == token::left_bracket) get(); else error("Wanted left bracket to start attribute list");
+ while (true) {
+ switch (peek().type) {
+ case token::right_bracket: break;
+ case token::identifier: {
+ std::string lhs = get().normalized_value;
+ std::string rhs = "true";
+ if (peek().type == token::equal) {
+ get();
+ if (peek().type != token::identifier) error("Wanted identifier as value of attributed");
+ rhs = get().normalized_value;
+ }
+ props[lhs] = rhs;
+ break;
+ }
+ default: error("Wanted identifier as name of attribute");
+ }
+ if (peek().type == token::comma) {get(); continue;}
+ break;
+ }
+ if (peek().type == token::right_bracket) get(); else error("Wanted right bracket to end attribute list");
+ if (peek().type != token::left_bracket) break;
+ }
+ }
+ };
+
+ struct graph_parser_policy {
+ ::boost::detail::graph::mutate_graph* mg;
+
+ typedef boost::detail::graph::node_t vertex;
+ typedef boost::detail::graph::edge_t edge;
+
+ std::map<std::string, vertex> vertex_map;
+ std::map<std::string, edge> edge_map;
+
+ graph_parser_policy(::boost::detail::graph::mutate_graph* mg)
+ : mg(mg),
+ vertex_map(),
+ edge_map()
+ {}
+
+ bool node_exists(const node_id& n) const {
+ std::map<std::string, vertex>::const_iterator i = vertex_map.find(n.name);
+ return (i != vertex_map.end());
+ }
+
+ vertex get_or_build_node(const node_id& n) {
+ // FIXME: use ports
+ std::map<std::string, vertex>::const_iterator i = vertex_map.find(n.name);
+ if (i == vertex_map.end()) {
+ vertex v = n.name;
+ mg->do_add_vertex(v);
+ vertex_map.insert(std::make_pair(v, v));
+ return v;
+ } else {
+ return i->second;
+ }
+ }
+
+ static std::string node_id_to_string(const node_id& n) {
+ std::string result = n.name;
+ for (size_t i = 0; i < n.location.size(); ++i) {
+ result += ":" + n.location[i];
+ }
+ if (!n.angle.empty()) result += "@" + n.angle;
+ return result;
+ }
+
+ static std::string props_to_string(const properties& props) {
+ std::string result = "[";
+ for (properties::const_iterator i = props.begin(); i != props.end(); ++i) {
+ if (i != props.begin()) result += ", ";
+ result += i->first + "=" + i->second;
+ }
+ result += "]";
+ return result;
+ }
+
+ void do_node(const node_id& n, const properties& def_props, const properties& new_props) {
+ std::cerr << node_id_to_string(n) << " " << props_to_string(def_props) << " " << props_to_string(new_props) << std::endl;
+ properties props_to_set = new_props;
+ if (!node_exists(n)) { // Only use defaults if node is new
+ props_to_set.insert(def_props.begin(), def_props.end()); // This keeps old properties in preference to ones from def_props
+ }
+ vertex v = get_or_build_node(n);
+ for (properties::const_iterator i = props_to_set.begin(); i != props_to_set.end(); ++i) {
+ mg->set_node_property(i->first, v, i->second);
+ }
+ }
+
+ void do_edge(const node_id& a, const node_id& b, const properties& props) {
+ std::cerr << node_id_to_string(a) << " -> " << node_id_to_string(b) << " " << props_to_string(props) << std::endl;
+ edge e = edge::new_edge();
+ mg->do_add_edge(e, get_or_build_node(a), get_or_build_node(b));
+ for (properties::const_iterator i = props.begin(); i != props.end(); ++i) {
+ mg->set_edge_property(i->first, e, i->second);
+ }
+ }
+
+ void do_begin_graph(bool is_strict, bool is_directed, const std::string& name) {
+ // std::cerr << "starting" << (is_strict ? " strict" : "") << " " << (is_directed ? "directed" : "undirected") << " graph named " << name << std::endl;
+ }
+
+ void do_end_graph(const properties& props) {
+ std::cerr << "ending graph " << props_to_string(props) << std::endl;
+ for (properties::const_iterator i = props.begin(); i != props.end(); ++i) {
+ mg->set_graph_property(i->first, i->second);
+ }
+ }
+
+ void do_subgraph_reference(const std::string& name) {
+ // std::cerr << "subgraph reference to " << name << std::endl;
+ }
+
+ void do_begin_subgraph(const std::string& name) {
+ // std::cerr << "starting subgraph named " << name << std::endl;
+ }
+
+ void do_end_subgraph(const properties& props) {
+ // std::cerr << "ending subgraph " << props_to_string(props) << std::endl;
+ }
+ };
+
+} // namespace read_graphviz_detail
+
+template <typename BidirectionalIterator, typename MutableGraph>
+bool read_graphviz(BidirectionalIterator begin, BidirectionalIterator end,
+ MutableGraph& graph, boost::dynamic_properties& dp,
+ std::string const& node_id = "node_id") {
+ boost::detail::graph::mutate_graph_impl<MutableGraph> mg(graph, dp, node_id);
+ read_graphviz_detail::graph_parser_policy policy(&mg);
+ read_graphviz_detail::parser<BidirectionalIterator, read_graphviz_detail::graph_parser_policy> p(begin, end, policy);
+ p.parse_graph(mg.is_directed());
+ return true;
+}
+
+} // namespace boost
+
+#endif // BOOST_READ_GRAPHVIZ_NEW_HPP
Modified: trunk/boost/graph/graphviz.hpp
==============================================================================
--- trunk/boost/graph/graphviz.hpp (original)
+++ trunk/boost/graph/graphviz.hpp 2009-05-18 13:27:15 EDT (Mon, 18 May 2009)
@@ -784,15 +784,24 @@
dynamic_properties& dp,
std::string const& node_id = "node_id")
{
- detail::graph::mutate_graph_impl<MutableGraph> m_graph(graph, dp, node_id);
- return detail::graph::read_graphviz(in, m_graph);
+ std::string data;
+ in >> std::noskipws;
+ std::copy(std::istream_iterator<char>(in),
+ std::istream_iterator<char>(),
+ std::back_inserter(data));
+ return read_graphviz(data.begin(),data.end(),graph,dp,node_id);
}
} // namespace boost
-#ifdef BOOST_GRAPH_READ_GRAPHVIZ_ITERATORS
+#ifdef BOOST_GRAPH_USE_SPIRIT_PARSER
+# ifndef BOOST_GRAPH_READ_GRAPHVIZ_ITERATORS
+# define BOOST_GRAPH_READ_GRAPHVIZ_ITERATORS
+# endif
# include <boost/graph/detail/read_graphviz_spirit.hpp>
-#endif // BOOST_GRAPH_READ_GRAPHVIZ_ITERATORS
+#else // New default parser
+# include <boost/graph/detail/read_graphviz_new.hpp>
+#endif // BOOST_GRAPH_USE_SPIRIT_PARSER
#ifdef BOOST_GRAPH_USE_MPI
# include <boost/graph/distributed/graphviz.hpp>
Modified: trunk/libs/graph/doc/read_graphviz.html
==============================================================================
--- trunk/libs/graph/doc/read_graphviz.html (original)
+++ trunk/libs/graph/doc/read_graphviz.html 2009-05-18 13:27:15 EDT (Mon, 18 May 2009)
@@ -1,48 +1,319 @@
<?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/" />
+<meta name="generator" content="Docutils 0.6: http://docutils.sourceforge.net/" />
<title>Boost read_graphviz</title>
-<link rel="stylesheet" href="default.css" type="text/css" />
+<style type="text/css">
+
+/*
+:Author: David Goodger (goodger_at_[hidden])
+:Id: $Id$
+:Copyright: This stylesheet has been placed in the public domain.
+
+Default cascading style sheet for the HTML output of Docutils.
+
+See http://docutils.sf.net/docs/howto/html-stylesheets.html for how to
+customize this style sheet.
+*/
+
+/* used to remove borders from tables and images */
+.borderless, table.borderless td, table.borderless th {
+ border: 0 }
+
+table.borderless td, table.borderless th {
+ /* Override padding for "table.docutils td" with "! important".
+ The right padding separates the table cells. */
+ padding: 0 0.5em 0 0 ! important }
+
+.first {
+ /* Override more specific margin styles with "! important". */
+ margin-top: 0 ! important }
+
+.last, .with-subtitle {
+ margin-bottom: 0 ! important }
+
+.hidden {
+ display: none }
+
+a.toc-backref {
+ text-decoration: none ;
+ color: black }
+
+blockquote.epigraph {
+ margin: 2em 5em ; }
+
+dl.docutils dd {
+ margin-bottom: 0.5em }
+
+/* Uncomment (and remove this text!) to get bold-faced definition list terms
+dl.docutils dt {
+ font-weight: bold }
+*/
+
+div.abstract {
+ margin: 2em 5em }
+
+div.abstract p.topic-title {
+ font-weight: bold ;
+ text-align: center }
+
+div.admonition, div.attention, div.caution, div.danger, div.error,
+div.hint, div.important, div.note, div.tip, div.warning {
+ margin: 2em ;
+ border: medium outset ;
+ padding: 1em }
+
+div.admonition p.admonition-title, div.hint p.admonition-title,
+div.important p.admonition-title, div.note p.admonition-title,
+div.tip p.admonition-title {
+ font-weight: bold ;
+ font-family: sans-serif }
+
+div.attention p.admonition-title, div.caution p.admonition-title,
+div.danger p.admonition-title, div.error p.admonition-title,
+div.warning p.admonition-title {
+ color: red ;
+ font-weight: bold ;
+ font-family: sans-serif }
+
+/* Uncomment (and remove this text!) to get reduced vertical space in
+ compound paragraphs.
+div.compound .compound-first, div.compound .compound-middle {
+ margin-bottom: 0.5em }
+
+div.compound .compound-last, div.compound .compound-middle {
+ margin-top: 0.5em }
+*/
+
+div.dedication {
+ margin: 2em 5em ;
+ text-align: center ;
+ font-style: italic }
+
+div.dedication p.topic-title {
+ font-weight: bold ;
+ font-style: normal }
+
+div.figure {
+ margin-left: 2em ;
+ margin-right: 2em }
+
+div.footer, div.header {
+ clear: both;
+ font-size: smaller }
+
+div.line-block {
+ display: block ;
+ margin-top: 1em ;
+ margin-bottom: 1em }
+
+div.line-block div.line-block {
+ margin-top: 0 ;
+ margin-bottom: 0 ;
+ margin-left: 1.5em }
+
+div.sidebar {
+ margin: 0 0 0.5em 1em ;
+ border: medium outset ;
+ padding: 1em ;
+ background-color: #ffffee ;
+ width: 40% ;
+ float: right ;
+ clear: right }
+
+div.sidebar p.rubric {
+ font-family: sans-serif ;
+ font-size: medium }
+
+div.system-messages {
+ margin: 5em }
+
+div.system-messages h1 {
+ color: red }
+
+div.system-message {
+ border: medium outset ;
+ padding: 1em }
+
+div.system-message p.system-message-title {
+ color: red ;
+ font-weight: bold }
+
+div.topic {
+ margin: 2em }
+
+h1.section-subtitle, h2.section-subtitle, h3.section-subtitle,
+h4.section-subtitle, h5.section-subtitle, h6.section-subtitle {
+ margin-top: 0.4em }
+
+h1.title {
+ text-align: center }
+
+h2.subtitle {
+ text-align: center }
+
+hr.docutils {
+ width: 75% }
+
+img.align-left {
+ clear: left }
+
+img.align-right {
+ clear: right }
+
+ol.simple, ul.simple {
+ margin-bottom: 1em }
+
+ol.arabic {
+ list-style: decimal }
+
+ol.loweralpha {
+ list-style: lower-alpha }
+
+ol.upperalpha {
+ list-style: upper-alpha }
+
+ol.lowerroman {
+ list-style: lower-roman }
+
+ol.upperroman {
+ list-style: upper-roman }
+
+p.attribution {
+ text-align: right ;
+ margin-left: 50% }
+
+p.caption {
+ font-style: italic }
+
+p.credits {
+ font-style: italic ;
+ font-size: smaller }
+
+p.label {
+ white-space: nowrap }
+
+p.rubric {
+ font-weight: bold ;
+ font-size: larger ;
+ color: maroon ;
+ text-align: center }
+
+p.sidebar-title {
+ font-family: sans-serif ;
+ font-weight: bold ;
+ font-size: larger }
+
+p.sidebar-subtitle {
+ font-family: sans-serif ;
+ font-weight: bold }
+
+p.topic-title {
+ font-weight: bold }
+
+pre.address {
+ margin-bottom: 0 ;
+ margin-top: 0 ;
+ font: inherit }
+
+pre.literal-block, pre.doctest-block {
+ margin-left: 2em ;
+ margin-right: 2em }
+
+span.classifier {
+ font-family: sans-serif ;
+ font-style: oblique }
+
+span.classifier-delimiter {
+ font-family: sans-serif ;
+ font-weight: bold }
+
+span.interpreted {
+ font-family: sans-serif }
+
+span.option {
+ white-space: nowrap }
+
+span.pre {
+ white-space: pre }
+
+span.problematic {
+ color: red }
+
+span.section-subtitle {
+ /* font-size relative to parent (h1..h6 element) */
+ font-size: 80% }
+
+table.citation {
+ border-left: solid 1px gray;
+ margin-left: 1px }
+
+table.docinfo {
+ margin: 2em 4em }
+
+table.docutils {
+ margin-top: 0.5em ;
+ margin-bottom: 0.5em }
+
+table.footnote {
+ border-left: solid 1px black;
+ margin-left: 1px }
+
+table.docutils td, table.docutils th,
+table.docinfo td, table.docinfo th {
+ padding-left: 0.5em ;
+ padding-right: 0.5em ;
+ vertical-align: top }
+
+table.docutils th.field-name, table.docinfo th.docinfo-name {
+ font-weight: bold ;
+ text-align: left ;
+ white-space: nowrap ;
+ padding-left: 0 }
+
+h1 tt.docutils, h2 tt.docutils, h3 tt.docutils,
+h4 tt.docutils, h5 tt.docutils, h6 tt.docutils {
+ font-size: 100% }
+
+ul.auto-toc {
+ list-style-type: none }
+
+</style>
</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>
+<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 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">
-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);
+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 BidirectionalIterator, typename MutableGraph>
+ bool read_graphviz(BidirectionalIterator begin, BidirectionalIterator 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" 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>
+<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 <tt class="docutils literal"><span class="pre">BOOST_GRAPH_USE_SPIRIT_PARSER</span></tt> macro may be defined before including
+<tt class="docutils literal"><span class="pre"><boost/graph/graphviz.hpp></span></tt> to include a previous parser implementation,
+with the same interface, that uses Spirit for its implementation. The main
+advantage of that version is that it supports subgraphs to a limited extent,
+while the new parser does not support them at all.</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;
@@ -50,7 +321,7 @@
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
+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
@@ -58,32 +329,31 @@
<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>
+<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.sgi.com/tech/stl/BidirectionalIterator.html">Bidirectional 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>
+<p class="topic-title first">Contents</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>
+<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" name="where-defined">Where Defined</a></h1>
+<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" name="exceptions">Exceptions</a></h1>
+<h1><a class="toc-backref" href="#id3">Exceptions</a></h1>
<pre class="literal-block">
struct graph_exception : public std::exception {
virtual ~graph_exception() throw();
@@ -130,13 +400,13 @@
language.</p>
</div>
<div class="section" id="example">
-<h1><a class="toc-backref" href="#id4" name="example">Example</a></h1>
+<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;
+ property < vertex_color_t, float > > vertex_p;
// Edge properties
typedef property < edge_weight_t, double > edge_p;
// Graph properties
@@ -162,7 +432,7 @@
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>
+boost::ref_property_map<graph_t*,std::string>
gname(get_property(graph,graph_name));
dp.property("name",gname);
@@ -174,20 +444,13 @@
</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>
+<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" 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>
+the "boost_regex" library. The library can be built by following the
+<a class="reference external" href="../../../more/getting_started.html#Build_Install">Boost Jam Build Instructions</a> for the subdirectory <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="#id7" name="notes">Notes</a></h1>
+<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
@@ -196,15 +459,6 @@
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
@@ -217,21 +471,33 @@
that property map value types are default constructible.</strong></li>
</ul>
</blockquote>
+<!-- - ``read_graphviz`` 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 ``digraph { a -> subgraph {b -> c} -> e }`` and
+ ``digraph { a -> b -> e ; a -> c -> e ; b -> c}`` are equivalent. -->
+<!-- - Subgraph IDs refer to subgraphs defined earlier in the graph
+ description. Undefined subgraphs behave as empty subgraphs
+ (``{}``). -->
</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>
+<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="#id9" name="future-work">Future Work</a></h1>
+<h1><a class="toc-backref" href="#id8">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>
+<li>Support for subgraphs (currently parsed but ignored).</li>
+<li>Support for HTML strings.</li>
+<li>Passing port information to BGL.</li>
+<li>Expanding escape codes in the same way GraphViz does.</li>
+<li>Enforcement of the <tt class="docutils literal"><span class="pre">strict</span></tt> keyword (ignoring self-loops and parallel
+edges).</li>
</ul>
</blockquote>
+<!-- - Support for optional recognition of subgraphs as distinct entities. -->
</div>
</div>
</body>
Modified: trunk/libs/graph/doc/read_graphviz.rst
==============================================================================
--- trunk/libs/graph/doc/read_graphviz.rst (original)
+++ trunk/libs/graph/doc/read_graphviz.rst 2009-05-18 13:27:15 EDT (Mon, 18 May 2009)
@@ -14,32 +14,31 @@
::
- 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);
+ 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 BidirectionalIterator, typename MutableGraph>
+ bool read_graphviz(BidirectionalIterator begin, BidirectionalIterator end,
+ MutableGraph& graph, dynamic_properties& dp,
+ const std::string& node_id = "node_id");
+
+ }
The ``read_graphviz`` function interprets a graph described using the
GraphViz_ 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 ``read_graphviz``,
-you will need to define the macro BOOST_GRAPH_READ_GRAPHVIZ_ITERATORS
-before including the header ``<boost/graph/graphviz.hpp>``. Doing so
-may greatly increase the amount of time required to compile the
-GraphViz reader.
+description. Using these functions, you can initialize a graph using
+data stored as text.
+
+The ``BOOST_GRAPH_USE_SPIRIT_PARSER`` macro may be defined before including
+``<boost/graph/graphviz.hpp>`` to include a previous parser implementation,
+with the same interface, that uses Spirit for its implementation. The main
+advantage of that version is that it supports subgraphs to a limited extent,
+while the new parser does not support them at all.
The DOT language can specify both directed and undirected graphs, and
``read_graphviz`` differentiates between the two. One must pass
@@ -57,7 +56,7 @@
Requirements:
- The type of the graph must model the `Mutable Graph`_ concept.
- - The type of the iterator must model the `Multi-Pass Iterator`_
+ - The type of the iterator must model the `Bidirectional Iterator`_
concept.
- The property map value types must be default-constructible.
@@ -172,15 +171,8 @@
Building the GraphViz Readers
-----------------------------
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
-`Boost Jam Build Instructions`_ for the subdirectory ``libs/graph/build``.
-
-Deprecated Readers
-------------------
-The deprecated readers do not provide exceptions on error (they
-abort), they require the use of one of the predefined graph types
-(``GraphvizDigraph`` or ``GraphvizGraph``), and they do not support
-arbitrary properties. They will be removed in a future Boost version.
+the "boost_regex" library. The library can be built by following the
+`Boost Jam Build Instructions`_ for the subdirectory ``libs/regex/build``.
Notes
@@ -193,17 +185,6 @@
resulting interpretation may be subtly different from dot for some
corner cases that are not well specified.
- - ``read_graphviz`` 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 ``digraph { a -> subgraph {b -> c} -> e }`` and
- ``digraph { a -> b -> e ; a -> c -> e ; b -> c}`` are equivalent.
-
- - Subgraph IDs refer to subgraphs defined earlier in the graph
- description. Undefined subgraphs behave as empty subgraphs
- (``{}``).
-
- 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
@@ -215,6 +196,19 @@
given the default constructed value of the value type. **Be sure
that property map value types are default constructible.**
+..
+ - ``read_graphviz`` 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 ``digraph { a -> subgraph {b -> c} -> e }`` and
+ ``digraph { a -> b -> e ; a -> c -> e ; b -> c}`` are equivalent.
+
+..
+ - Subgraph IDs refer to subgraphs defined earlier in the graph
+ description. Undefined subgraphs behave as empty subgraphs
+ (``{}``).
+
See Also
--------
@@ -224,16 +218,24 @@
Future Work
-----------
- - 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.
+ - Support for subgraphs (currently parsed but ignored).
- - Support for optional recognition of subgraphs as distinct entities.
+ - Support for HTML strings.
+
+ - Passing port information to BGL.
+
+ - Expanding escape codes in the same way GraphViz does.
+
+ - Enforcement of the ``strict`` keyword (ignoring self-loops and parallel
+ edges).
+..
+ - Support for optional recognition of subgraphs as distinct entities.
+
.. _GraphViz: http://graphviz.org/
.. _`Mutable Graph`: MutableGraph.html
-.. _`Multi-Pass Iterator`: ../../iterator/index.html
+.. _`Bidirectional Iterator`: http://www.sgi.com/tech/stl/BidirectionalIterator.html
.. _dynamic_properties: ../../property_map/doc/dynamic_property_map.html
.. _write_graphviz: write-graphviz.html
.. _Boost Jam Build Instructions: ../../../more/getting_started.html#Build_Install
Modified: trunk/libs/graph/src/read_graphviz_spirit.cpp
==============================================================================
--- trunk/libs/graph/src/read_graphviz_spirit.cpp (original)
+++ trunk/libs/graph/src/read_graphviz_spirit.cpp 2009-05-18 13:27:15 EDT (Mon, 18 May 2009)
@@ -26,38 +26,22 @@
# define BOOST_GRAPH_READ_GRAPHVIZ_ITERATORS
#endif
#include <boost/graph/graphviz.hpp>
+#include <iostream>
namespace boost { namespace detail { namespace graph {
+#if 0
BOOST_GRAPH_DECL
bool read_graphviz(std::istream& in, mutate_graph& graph)
{
using namespace boost;
- using namespace boost::spirit::classic;
typedef std::istream_iterator<char> is_t;
- typedef multi_pass<is_t> iterator_t;
- iterator_t first(make_multi_pass(is_t(in)));
- iterator_t last(make_multi_pass(is_t()));
+ std::string str((is_t(in)), is_t());
- // Turn off white space skipping on the stream
- in.unsetf(std::ios::skipws);
-
- typedef skip_parser_iteration_policy< boost::detail::graph::dot_skipper>
- iter_policy_t;
- typedef scanner_policies<iter_policy_t> scanner_policies_t;
- typedef scanner<iterator_t, scanner_policies_t> scanner_t;
-
- boost::detail::graph::dot_grammar p(graph);
- boost::detail::graph::dot_skipper skip_p;
-
- iter_policy_t iter_policy(skip_p);
- scanner_policies_t policies(iter_policy);
-
- scanner_t scan(first, last, policies);
-
- return p.parse(scan);
+ return read_graphviz(str.begin(), str.end());
}
+#endif
} } } // end namespace boost::detail::graph
Modified: trunk/libs/graph/test/Jamfile.v2
==============================================================================
--- trunk/libs/graph/test/Jamfile.v2 (original)
+++ trunk/libs/graph/test/Jamfile.v2 2009-05-18 13:27:15 EDT (Mon, 18 May 2009)
@@ -58,7 +58,8 @@
[ compile graph_concepts.cpp ]
[ run graphviz_test.cpp
/boost/test//boost_test_exec_monitor/<link>static
- ../build//boost_graph ]
+ ../build//boost_graph
+ ../../regex/build//boost_regex ]
[ run metis_test.cpp : $(METIS_INPUT_FILE) ]
[ run gursoy_atun_layout_test.cpp ]
[ run layout_test.cpp : : : <test-info>always_show_run_output <toolset>intel:<debug-symbols>off ]
@@ -85,7 +86,7 @@
[ run matching_test.cpp ]
[ run max_flow_test.cpp ]
[ run kolmogorov_max_flow_test.cpp ]
- [ run cycle_ratio_tests.cpp ../build//boost_graph : $(CYCLE_RATIO_INPUT_FILE) ]
+ [ run cycle_ratio_tests.cpp ../build//boost_graph ../../regex/build//boost_regex : $(CYCLE_RATIO_INPUT_FILE) ]
[ run basic_planarity_test.cpp ]
[ run make_connected_test.cpp ]
[ run make_bicon_planar_test.cpp ]
Modified: trunk/libs/graph/test/graphviz_test.cpp
==============================================================================
--- trunk/libs/graph/test/graphviz_test.cpp (original)
+++ trunk/libs/graph/test/graphviz_test.cpp 2009-05-18 13:27:15 EDT (Mon, 18 May 2009)
@@ -11,8 +11,8 @@
// Author: Ronald Garcia
-//#define BOOST_GRAPH_READ_GRAPHVIZ_ITERATORS
#define BOOST_GRAPHVIZ_USE_ISTREAM
+#include <boost/regex.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/assign/std/map.hpp>
#include <boost/graph/adjacency_list.hpp>
@@ -31,9 +31,6 @@
using namespace std;
using namespace boost;
-#ifndef BOOST_GRAPHVIZ_USE_ISTREAM
-using namespace boost::spirit;
-#endif
using namespace boost::assign;
typedef std::string node_t;
@@ -43,7 +40,8 @@
typedef std::map<edge_t,double> weight_map_t;
template <typename Directedness, typename OutEdgeList>
-bool test_graph(std::istream& dotfile, mass_map_t const& masses,
+bool test_graph(std::istream& dotfile, std::size_t correct_num_vertices,
+ mass_map_t const& masses,
weight_map_t const& weights,
std::string const& node_id = "node_id",
std::string const& g_name = std::string()) {
@@ -79,11 +77,14 @@
if(read_graphviz(dotfile,graph,dp,node_id)) {
#else
std::string data;
+ dotfile >> std::noskipws;
std::copy(std::istream_iterator<char>(dotfile),
std::istream_iterator<char>(),
std::back_inserter(data));
if(read_graphviz(data.begin(),data.end(),graph,dp,node_id)) {
#endif
+ // check correct vertex count
+ BOOST_CHECK_EQUAL(num_vertices(graph), correct_num_vertices);
// check masses
if(!masses.empty()) {
// assume that all the masses have been set
@@ -139,16 +140,25 @@
mass_map_t masses;
insert ( masses ) ("a",0.0f) ("c",7.7f) ("e", 6.66f);
gs_t gs("digraph { a node [mass = 7.7] c e [mass = 6.66] }");
- BOOST_CHECK((test_graph<directedS,vecS>(gs,masses,weight_map_t())));
+ BOOST_CHECK((test_graph<directedS,vecS>(gs,3,masses,weight_map_t())));
+ }
+
+ {
+ mass_map_t masses;
+ insert ( masses ) ("a",0.0f) ("e", 6.66f);
+ gs_t gs("digraph { a node [mass = 7.7] \"a\" e [mass = 6.66] }");
+ BOOST_CHECK((test_graph<directedS,vecS>(gs,2,masses,weight_map_t())));
}
{
weight_map_t weights;
insert( weights )(make_pair("a","b"),0.0)
- (make_pair("c","d"),7.7)(make_pair("e","f"),6.66);
- gs_t gs("digraph { a -> b edge [weight = 7.7] "
- "c -> d e-> f [weight = 6.66] }");
- BOOST_CHECK((test_graph<directedS,vecS>(gs,mass_map_t(),weights)));
+ (make_pair("c","d"),7.7)(make_pair("e","f"),6.66)
+ (make_pair("d","e"),0.5)(make_pair("e","a"),0.5);
+ gs_t gs("digraph { a -> b eDge [weight = 7.7] "
+ "c -> d e-> f [weight = 6.66] "
+ "d ->e->a [weight=.5]}");
+ BOOST_CHECK((test_graph<directedS,vecS>(gs,6,mass_map_t(),weights)));
}
// undirected graph with alternate node_id property name
@@ -156,7 +166,7 @@
mass_map_t masses;
insert ( masses ) ("a",0.0f) ("c",7.7f) ("e", 6.66f);
gs_t gs("graph { a node [mass = 7.7] c e [mass = 6.66] }");
- BOOST_CHECK((test_graph<undirectedS,vecS>(gs,masses,weight_map_t(),
+ BOOST_CHECK((test_graph<undirectedS,vecS>(gs,3,masses,weight_map_t(),
"nodenames")));
}
@@ -165,7 +175,7 @@
mass_map_t masses;
insert ( masses ) ("a",0.0f) ("c",7.7f) ("e", 6.66f);
gs_t gs("graph { a node [mass = 7.7] c e [mass = 6.66] }");
- BOOST_CHECK((test_graph<undirectedS,vecS>(gs,masses,weight_map_t())));
+ BOOST_CHECK((test_graph<undirectedS,vecS>(gs,3,masses,weight_map_t())));
}
{
@@ -174,7 +184,7 @@
(make_pair("c","d"),7.7)(make_pair("e","f"),6.66);
gs_t gs("graph { a -- b eDge [weight = 7.7] "
"c -- d e -- f [weight = 6.66] }");
- BOOST_CHECK((test_graph<undirectedS,vecS>(gs,mass_map_t(),weights)));
+ BOOST_CHECK((test_graph<undirectedS,vecS>(gs,6,mass_map_t(),weights)));
}
// Mismatch directed graph test
@@ -183,7 +193,7 @@
insert ( masses ) ("a",0.0f) ("c",7.7f) ("e", 6.66f);
gs_t gs("graph { a nodE [mass = 7.7] c e [mass = 6.66] }");
try {
- test_graph<directedS,vecS>(gs,masses,weight_map_t());
+ test_graph<directedS,vecS>(gs,3,masses,weight_map_t());
BOOST_ERROR("Failed to throw boost::directed_graph_error.");
} catch (boost::undirected_graph_error&) {}
}
@@ -194,7 +204,7 @@
insert ( masses ) ("a",0.0f) ("c",7.7f) ("e", 6.66f);
gs_t gs("digraph { a node [mass = 7.7] c e [mass = 6.66] }");
try {
- test_graph<undirectedS,vecS>(gs,masses,weight_map_t());
+ test_graph<undirectedS,vecS>(gs,3,masses,weight_map_t());
BOOST_ERROR("Failed to throw boost::directed_graph_error.");
} catch (boost::directed_graph_error&) {}
}
@@ -205,7 +215,7 @@
insert( weights )(make_pair("a","b"),7.7);
gs_t gs("diGraph { a -> b [weight = 7.7] a -> b [weight = 7.7] }");
try {
- test_graph<directedS,setS>(gs,mass_map_t(),weights);
+ test_graph<directedS,setS>(gs,2,mass_map_t(),weights);
BOOST_ERROR("Failed to throw boost::bad_parallel_edge.");
} catch (boost::bad_parallel_edge&) {}
}
@@ -215,16 +225,16 @@
weight_map_t weights;
insert( weights )(make_pair("a","b"),7.7);
gs_t gs("digraph { a -> b [weight = 7.7] a -> b [weight = 7.7] }");
- BOOST_CHECK((test_graph<directedS,vecS>(gs,mass_map_t(),weights)));
+ BOOST_CHECK((test_graph<directedS,vecS>(gs,2,mass_map_t(),weights)));
}
// Graph Property Test 1
{
mass_map_t masses;
insert ( masses ) ("a",0.0f) ("c",0.0f) ("e", 6.66f);
- gs_t gs("digraph { graph [name=\"foo\"] a c e [mass = 6.66] }");
- std::string graph_name("foo");
- BOOST_CHECK((test_graph<directedS,vecS>(gs,masses,weight_map_t(),"",
+ gs_t gs("digraph { graph [name=\"foo \\\"escaped\\\"\"] a c e [mass = 6.66] }");
+ std::string graph_name("foo \"escaped\"");
+ BOOST_CHECK((test_graph<directedS,vecS>(gs,3,masses,weight_map_t(),"",
graph_name)));
}
@@ -232,9 +242,9 @@
{
mass_map_t masses;
insert ( masses ) ("a",0.0f) ("c",0.0f) ("e", 6.66f);
- gs_t gs("digraph { name=\"foo\" a c e [mass = 6.66] }");
+ gs_t gs("digraph { name=\"fo\"+ \"\\\no\" a c e [mass = 6.66] }");
std::string graph_name("foo");
- BOOST_CHECK((test_graph<directedS,vecS>(gs,masses,weight_map_t(),"",
+ BOOST_CHECK((test_graph<directedS,vecS>(gs,3,masses,weight_map_t(),"",
graph_name)));
}
@@ -246,7 +256,7 @@
"a1 [ label = \"//depot/path/to/file_29#9\" ];"
"a0 -> a1 [ color=gray ];"
"}");
- BOOST_CHECK((test_graph<directedS,vecS>(gs,mass_map_t(),weight_map_t())));
+ BOOST_CHECK((test_graph<directedS,vecS>(gs,2,mass_map_t(),weight_map_t())));
}
return 0;
}