| // 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.cpp - |
| // 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 |
| // |
| |
| #define BOOST_GRAPH_SOURCE |
| #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/throw_exception.hpp> |
| #include <boost/regex.hpp> |
| #include <boost/function.hpp> |
| #include <boost/bind.hpp> |
| #include <boost/graph/dll_import_export.hpp> |
| #include <boost/graph/graphviz.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 |
| }; |
| token_type 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; |
| } |
| }; |
| |
| bad_graphviz_syntax lex_error(const std::string& errmsg, char bad_char) { |
| if (bad_char == '\0') { |
| return bad_graphviz_syntax(errmsg + " (at end of input)"); |
| } else { |
| return bad_graphviz_syntax(errmsg + " (char is '" + bad_char + "')"); |
| } |
| } |
| |
| bad_graphviz_syntax parse_error(const std::string& errmsg, const token& bad_token) { |
| return bad_graphviz_syntax(errmsg + " (token is \"" + boost::lexical_cast<std::string>(bad_token) + "\")"); |
| } |
| |
| struct tokenizer { |
| std::string::const_iterator 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; |
| boost::regex xml_tag_token; |
| boost::regex cdata; |
| |
| tokenizer(const std::string& str) : begin(str.begin()), end(str.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 = "(?:^#.*?$)"; |
| std::string backslash_newline = "(?:[\\\\][\\n])"; |
| stuff_to_skip = "\\A(?:" + whitespace + "|" + |
| slash_slash_comment + "|" + |
| slash_star_comment + "|" + |
| hash_comment + "|" + |
| backslash_newline + ")*"; |
| basic_id_token = "\\A([[:alpha:]_](?:\\w*))"; |
| punctuation_token = "\\A([][{};=,:+()@]|[-][>-])"; |
| number_token = "\\A([-]?(?:(?:\\.\\d+)|(?:\\d+(?:\\.\\d*)?)))"; |
| quoted_string_token = "\\A(\"(?:[^\"\\\\]|(?:[\\\\].))*\")"; |
| xml_tag_token = "\\A<(/?)(?:[^!?'\"]|(?:'[^']*?')|(?:\"[^\"]*?\"))*?(/?)>"; |
| cdata = "\\A\\Q<![CDATA[\\E.*?\\Q]]>\\E"; |
| } |
| |
| void skip() { |
| boost::match_results<std::string::const_iterator> results; |
| #ifndef NDEBUG |
| bool found = |
| #endif |
| boost::regex_search(begin, end, results, stuff_to_skip); |
| #ifndef NDEBUG |
| assert (found); |
| #endif |
| boost::sub_match<std::string::const_iterator> 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<std::string::const_iterator> 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"); |
| } |
| } |
| 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 == '<') { |
| std::string::const_iterator saved_begin = begin; |
| int counter = 0; |
| do { |
| if (begin == end) throw_lex_error("Unclosed HTML string"); |
| if (*begin != '<') { |
| ++begin; |
| continue; |
| } |
| found = boost::regex_search(begin, end, results, xml_tag_token); |
| if (found) { |
| begin = results.suffix().first; |
| if (results[1].str() == "/") { // Close tag |
| --counter; |
| } else if (results[2].str() == "/") { // Empty tag |
| } else { // Open tag |
| ++counter; |
| } |
| continue; |
| } |
| found = boost::regex_search(begin, end, results, cdata); |
| if (found) { |
| begin = results.suffix().first; |
| continue; |
| } |
| throw_lex_error("Invalid contents in HTML string"); |
| } while (counter > 0); |
| return token(token::identifier, std::string(saved_begin, begin)); |
| } 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 == end ? '\0' : *begin))); |
| } |
| }; |
| |
| struct edge_endpoint { |
| bool is_subgraph; |
| node_and_port node_ep; |
| subgraph_name subgraph_ep; |
| |
| static edge_endpoint node(const node_and_port& ep) { |
| edge_endpoint r; |
| r.is_subgraph = false; |
| r.node_ep = ep; |
| return r; |
| } |
| |
| static edge_endpoint subgraph(const subgraph_name& ep) { |
| edge_endpoint r; |
| r.is_subgraph = true; |
| r.subgraph_ep = ep; |
| return r; |
| } |
| }; |
| |
| struct node_or_subgraph_ref { |
| bool is_subgraph; |
| std::string name; // Name for subgraphs or nodes, "___root___" for root graph |
| }; |
| |
| static node_or_subgraph_ref noderef(const node_name& n) { |
| node_or_subgraph_ref r; |
| r.is_subgraph = false; |
| r.name = n; |
| return r; |
| } |
| |
| static node_or_subgraph_ref subgraphref(const subgraph_name& n) { |
| node_or_subgraph_ref r; |
| r.is_subgraph = true; |
| r.name = n; |
| return r; |
| } |
| |
| typedef std::vector<node_or_subgraph_ref> subgraph_member_list; |
| |
| struct subgraph_info { |
| properties def_node_props; |
| properties def_edge_props; |
| subgraph_member_list members; |
| }; |
| |
| struct parser { |
| tokenizer the_tokenizer; |
| std::vector<token> lookahead; |
| parser_result& r; |
| std::map<subgraph_name, subgraph_info> subgraphs; |
| std::string current_subgraph_name; |
| int sgcounter; // Counter for anonymous subgraphs |
| std::set<std::pair<node_name, node_name> > existing_edges; // Used for checking in strict graphs |
| |
| subgraph_info& current() {return subgraphs[current_subgraph_name];} |
| properties& current_graph_props() {return r.graph_props[current_subgraph_name];} |
| subgraph_member_list& current_members() {return current().members;} |
| |
| parser(const std::string& gr, parser_result& result) |
| : the_tokenizer(gr), lookahead(), r(result), sgcounter(0) { |
| current_subgraph_name = "___root___"; |
| current() = subgraph_info(); // Initialize root graph |
| current_graph_props().clear(); |
| current_members().clear(); |
| } |
| |
| token get() { |
| if (lookahead.empty()) { |
| token t = the_tokenizer.get_token(); |
| return t; |
| } else { |
| token t = lookahead.front(); |
| lookahead.erase(lookahead.begin()); |
| return t; |
| } |
| } |
| |
| token peek() { |
| if (lookahead.empty()) { |
| lookahead.push_back(the_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 = false; |
| 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\""); |
| } |
| r.graph_is_directed = is_directed; // Used to check edges |
| r.graph_is_strict = is_strict; |
| if (want_directed != r.graph_is_directed) { |
| if (want_directed) { |
| boost::throw_exception(boost::undirected_graph_error()); |
| } else { |
| boost::throw_exception(boost::directed_graph_error()); |
| } |
| } |
| 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"); |
| 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: |
| case token::identifier: { |
| token id = get(); |
| if (id.type == token::identifier && peek().type == token::equal) { // Graph property |
| get(); |
| if (peek().type != token::identifier) error("Wanted identifier as right side of ="); |
| token id2 = get(); |
| current_graph_props()[id.normalized_value] = id2.normalized_value; |
| } else { |
| edge_endpoint ep = parse_endpoint_rest(id); |
| if (peek().type == token::dash_dash || peek().type == token::dash_greater) { // Edge |
| parse_edge_stmt(ep); |
| } else { |
| if (!ep.is_subgraph) { // Only nodes can have attribute lists |
| // This node already exists because of its first mention |
| // (properties set to defaults by parse_node_and_port, called |
| // by parse_endpoint_rest) |
| properties this_node_props; |
| if (peek().type == token::left_bracket) { |
| parse_attr_list(this_node_props); |
| } |
| for (properties::const_iterator i = this_node_props.begin(); |
| i != this_node_props.end(); ++i) { |
| // Override old properties with same names |
| r.nodes[ep.node_ep.name][i->first] = i->second; |
| } |
| current_members().push_back(noderef(ep.node_ep.name)); |
| } else { |
| current_members().push_back(subgraphref(ep.subgraph_ep)); |
| } |
| } |
| } |
| break; |
| } |
| default: error("Invalid start token for statement"); |
| } |
| } |
| |
| void parse_attr_stmt() { |
| switch (get().type) { |
| case token::kw_graph: parse_attr_list(current_graph_props()); break; |
| case token::kw_node: parse_attr_list(current().def_node_props); break; |
| case token::kw_edge: parse_attr_list(current().def_edge_props); break; |
| default: assert (!"Bad attr_stmt case"); |
| } |
| } |
| |
| edge_endpoint parse_endpoint() { |
| switch (peek().type) { |
| case token::kw_subgraph: |
| case token::left_brace: |
| case token::identifier: { |
| token first = get(); |
| return parse_endpoint_rest(first); |
| } |
| default: { |
| error("Wanted \"subgraph\", \"{\", or identifier to start node or subgraph"); |
| return edge_endpoint(); |
| } |
| } |
| } |
| |
| edge_endpoint parse_endpoint_rest(const token& first_token) { |
| switch (first_token.type) { |
| case token::kw_subgraph: |
| case token::left_brace: return edge_endpoint::subgraph(parse_subgraph(first_token)); |
| default: return edge_endpoint::node(parse_node_and_port(first_token)); |
| } |
| } |
| |
| subgraph_name parse_subgraph(const token& first_token) { |
| std::string name; |
| bool is_anonymous = true; |
| if (first_token.type == token::kw_subgraph) { |
| if (peek().type == token::identifier) { |
| name = get().normalized_value; |
| is_anonymous = false; |
| } |
| } |
| if (is_anonymous) { |
| name = "___subgraph_" + |
| boost::lexical_cast<std::string>(++sgcounter); |
| } |
| if (subgraphs.find(name) == subgraphs.end()) { |
| subgraphs[name] = current(); // Initialize properties and defaults |
| subgraphs[name].members.clear(); // Except member list |
| } |
| if (first_token.type == token::kw_subgraph && peek().type != token::left_brace) { |
| if (is_anonymous) error("Subgraph reference needs a name"); |
| return name; |
| } |
| subgraph_name old_sg = current_subgraph_name; |
| current_subgraph_name = 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"); |
| current_subgraph_name = old_sg; |
| return name; |
| } |
| |
| node_and_port parse_node_and_port(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_and_port 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; |
| } |
| if (r.nodes.find(id.name) == r.nodes.end()) { // First mention |
| r.nodes[id.name] = current().def_node_props; |
| } |
| return id; |
| } |
| |
| void parse_edge_stmt(const edge_endpoint& lhs) { |
| std::vector<edge_endpoint> nodes_in_chain(1, lhs); |
| while (true) { |
| bool leave_loop = true; |
| switch (peek().type) { |
| case token::dash_dash: { |
| if (r.graph_is_directed) error("Using -- in directed graph"); |
| get(); |
| nodes_in_chain.push_back(parse_endpoint()); |
| leave_loop = false; |
| break; |
| } |
| case token::dash_greater: { |
| if (!r.graph_is_directed) error("Using -> in undirected graph"); |
| get(); |
| nodes_in_chain.push_back(parse_endpoint()); |
| leave_loop = false; |
| break; |
| } |
| default: leave_loop = true; break; |
| } |
| if (leave_loop) break; |
| } |
| properties this_edge_props = current().def_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) { |
| do_orig_edge(nodes_in_chain[i], nodes_in_chain[i + 1], this_edge_props); |
| } |
| } |
| |
| // Do an edge from the file, the edge may need to be expanded if it connects to a subgraph |
| void do_orig_edge(const edge_endpoint& src, const edge_endpoint& tgt, const properties& props) { |
| std::set<node_and_port> sources = get_recursive_members(src); |
| std::set<node_and_port> targets = get_recursive_members(tgt); |
| for (std::set<node_and_port>::const_iterator i = sources.begin(); i != sources.end(); ++i) { |
| for (std::set<node_and_port>::const_iterator j = targets.begin(); j != targets.end(); ++j) { |
| do_edge(*i, *j, props); |
| } |
| } |
| } |
| |
| // Get nodes in an edge_endpoint, recursively |
| std::set<node_and_port> get_recursive_members(const edge_endpoint& orig_ep) { |
| std::set<node_and_port> result; |
| std::vector<edge_endpoint> worklist(1, orig_ep); |
| std::set<subgraph_name> done; |
| while (!worklist.empty()) { |
| edge_endpoint ep = worklist.back(); |
| worklist.pop_back(); |
| if (ep.is_subgraph) { |
| if (done.find(ep.subgraph_ep) == done.end()) { |
| done.insert(ep.subgraph_ep); |
| std::map<subgraph_name, subgraph_info>::const_iterator |
| info_i = subgraphs.find(ep.subgraph_ep); |
| if (info_i != subgraphs.end()) { |
| const subgraph_member_list& members = info_i->second.members; |
| for (subgraph_member_list::const_iterator i = members.begin(); |
| i != members.end(); ++i) { |
| node_or_subgraph_ref ref = *i; |
| if (ref.is_subgraph) { |
| worklist.push_back(edge_endpoint::subgraph(ref.name)); |
| } else { |
| node_and_port np; |
| np.name = ref.name; |
| worklist.push_back(edge_endpoint::node(np)); |
| } |
| } |
| } |
| } |
| } else { |
| result.insert(ep.node_ep); |
| } |
| } |
| return result; |
| } |
| |
| // Do a fixed-up edge, with only nodes as endpoints |
| void do_edge(const node_and_port& src, const node_and_port& tgt, const properties& props) { |
| if (r.graph_is_strict) { |
| if (src.name == tgt.name) return; |
| std::pair<node_name, node_name> tag(src.name, tgt.name); |
| if (existing_edges.find(tag) != existing_edges.end()) { |
| return; // Parallel edge |
| } |
| existing_edges.insert(tag); |
| } |
| edge_info e; |
| e.source = src; |
| e.target = tgt; |
| e.props = props; |
| r.edges.push_back(e); |
| } |
| |
| 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; |
| } |
| } |
| }; |
| |
| void parse_graphviz_from_string(const std::string& str, parser_result& result, bool want_directed) { |
| parser p(str, result); |
| p.parse_graph(want_directed); |
| } |
| |
| // Some debugging stuff |
| std::ostream& operator<<(std::ostream& o, const node_and_port& n) { |
| o << n.name; |
| for (size_t i = 0; i < n.location.size(); ++i) { |
| o << ":" << n.location[i]; |
| } |
| if (!n.angle.empty()) o << "@" << n.angle; |
| return o; |
| } |
| |
| // Can't be operator<< because properties is just an std::map |
| 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 translate_results_to_graph(const parser_result& r, ::boost::detail::graph::mutate_graph* mg) { |
| typedef boost::detail::graph::node_t vertex; |
| typedef boost::detail::graph::edge_t edge; |
| for (std::map<node_name, properties>::const_iterator i = r.nodes.begin(); i != r.nodes.end(); ++i) { |
| // std::cerr << i->first << " " << props_to_string(i->second) << std::endl; |
| mg->do_add_vertex(i->first); |
| for (properties::const_iterator j = i->second.begin(); j != i->second.end(); ++j) { |
| mg->set_node_property(j->first, i->first, j->second); |
| } |
| } |
| for (std::vector<edge_info>::const_iterator i = r.edges.begin(); i != r.edges.end(); ++i) { |
| const edge_info& ei = *i; |
| // std::cerr << ei.source << " -> " << ei.target << " " << props_to_string(ei.props) << std::endl; |
| edge e = edge::new_edge(); |
| mg->do_add_edge(e, ei.source.name, ei.target.name); |
| for (properties::const_iterator j = ei.props.begin(); j != ei.props.end(); ++j) { |
| mg->set_edge_property(j->first, e, j->second); |
| } |
| } |
| std::map<subgraph_name, properties>::const_iterator root_graph_props_i = r.graph_props.find("___root___"); |
| assert (root_graph_props_i != r.graph_props.end()); // Should not happen |
| const properties& root_graph_props = root_graph_props_i->second; |
| // std::cerr << "ending graph " << props_to_string(root_graph_props) << std::endl; |
| for (properties::const_iterator i = root_graph_props.begin(); i != root_graph_props.end(); ++i) { |
| mg->set_graph_property(i->first, i->second); |
| } |
| } |
| |
| } // end namespace read_graphviz_detail |
| |
| namespace detail { |
| namespace graph { |
| |
| BOOST_GRAPH_DECL bool read_graphviz_new(const std::string& str, boost::detail::graph::mutate_graph* mg) { |
| read_graphviz_detail::parser_result parsed_file; |
| read_graphviz_detail::parse_graphviz_from_string(str, parsed_file, mg->is_directed()); |
| read_graphviz_detail::translate_results_to_graph(parsed_file, mg); |
| return true; |
| } |
| |
| } // end namespace graph |
| } // end namespace detail |
| |
| } // end namespace boost |
| |
| // GraphViz format notes (tested using "dot version 1.13 (v16) (Mon August 23, |
| // 2004)", grammar from references in read_graphviz_new.hpp): |
| |
| // Subgraphs don't nest (all a0 subgraphs are the same thing), but a node or |
| // subgraph can have multiple parents (sources online say that the layout |
| // algorithms can't handle non-tree structures of clusters, but it seems to |
| // read them the same from the file). The containment relation is required to |
| // be a DAG, though; it appears that a node or subgraph can't be moved into an |
| // ancestor of a subgraph where it already was (we don't enforce that but do a |
| // DFS when finding members to prevent cycles). Nodes get their properties by |
| // when they are first mentioned, and can only have them overridden after that |
| // by explicit properties on that particular node. Closing and reopening the |
| // same subgraph name adds to its members, and graph properties and node/edge |
| // defaults are preserved in that subgraph. The members of a subgraph used in |
| // an edge are gathered when the edge is read, even if new members are added to |
| // the subgraph later. Ports are allowed in a lot more places in the grammar |
| // than Dot uses. For example, declaring a node seems to ignore ports, and I |
| // don't think it's possible to set properties on a particular port. Adding an |
| // edge between two ports on the same node seems to make Dot unhappy (crashed |
| // for me). |
| |
| // Test graph for GraphViz behavior on strange combinations of subgraphs and |
| // such. I don't have anywhere else to put this file. |
| |
| #if 0 |
| dIGRaph foo { |
| node [color=blue] |
| subgraph a -> b |
| subgraph a {c} |
| subgraph a -> d |
| subgraph a {node [color=red]; e} |
| subgraph a -> f |
| subgraph a {g} -> h |
| subgraph a {node [color=green]; i} -> j |
| subgraph a {node [color=yellow]} |
| |
| subgraph a0 {node [color=black]; subgraph a1 {node [color=white]}} |
| node [color=pink] zz |
| subgraph a0 {x1} |
| subgraph a0 {subgraph a1 {x2}} |
| |
| subgraph a0 -> x3 |
| subgraph a0 {subgraph a1 -> x3} |
| x3 |
| subgraph a0 {subgraph a0 {node [color=xxx]; x2} x7} |
| x2 [color=yyy] |
| subgraph cluster_ax {foo; subgraph a0} |
| subgraph a0 {foo2} |
| subgraph cluster_ax {foo3} |
| // subgraph a0 -> subgraph a0 |
| |
| bgcolor=yellow |
| subgraph cluster_a2 {y1} |
| // y1:n -> y1:(s,3)@se |
| y1@se [color=green] |
| y1@n [color=red] |
| } |
| #endif |
