boost/graph/detail/read_graphviz_spirit.hpp
// 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_spirit.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: // https://web.archive.org/web/20041213234742/http://www.graphviz.org/cvs/doc/info/lang.html // // See documentation for this code at: // http://www.boost.org/libs/graph/doc/read_graphviz.html // // Author: Ronald Garcia // #ifndef BOOST_READ_GRAPHVIZ_SPIRIT_HPP #define BOOST_READ_GRAPHVIZ_SPIRIT_HPP // Phoenix/Spirit set these limits to 3, but I need more. #define PHOENIX_LIMIT 6 #define BOOST_SPIRIT_CLOSURE_LIMIT 6 #include <boost/spirit/include/classic_multi_pass.hpp> #include <boost/spirit/include/classic_core.hpp> #include <boost/spirit/include/classic_confix.hpp> #include <boost/spirit/include/classic_distinct.hpp> #include <boost/spirit/include/classic_lists.hpp> #include <boost/spirit/include/classic_escape_char.hpp> #include <boost/spirit/include/classic_attribute.hpp> #include <boost/spirit/include/classic_dynamic.hpp> #include <boost/spirit/include/classic_actor.hpp> #include <boost/spirit/include/classic_closure.hpp> #include <boost/spirit/include/phoenix1.hpp> #include <boost/spirit/include/phoenix1_binders.hpp> #include <boost/ref.hpp> #include <boost/function/function2.hpp> #include <boost/type_traits/is_same.hpp> #include <boost/property_map/dynamic_property_map.hpp> #include <boost/graph/graph_traits.hpp> #include <boost/detail/workaround.hpp> #include <algorithm> #include <exception> // for std::exception #include <string> #include <vector> #include <set> #include <utility> #include <map> #include <boost/graph/graphviz.hpp> #include <boost/throw_exception.hpp> namespace phoenix { // Workaround: std::map::operator[] uses a different return type than all // other standard containers. Phoenix doesn't account for that. template < typename TK, typename T0, typename T1 > struct binary_operator< index_op, std::map< TK, T0 >, T1 > { typedef typename std::map< TK, T0 >::mapped_type& result_type; static result_type eval(std::map< TK, T0 >& container, T1 const& index) { return container[index]; } }; } // namespace phoenix namespace boost { namespace detail { namespace graph { ///////////////////////////////////////////////////////////////////////////// // Application-specific type definitions ///////////////////////////////////////////////////////////////////////////// typedef std::set< edge_t > edges_t; typedef std::set< node_t > nodes_t; typedef std::set< id_t > ids_t; typedef std::map< edge_t, ids_t > edge_map_t; typedef std::map< node_t, ids_t > node_map_t; typedef std::map< id_t, id_t > props_t; typedef std::map< id_t, props_t > subgraph_props_t; typedef boost::function2< void, id_t const&, id_t const& > actor_t; typedef std::vector< edge_t > edge_stack_t; typedef std::map< id_t, nodes_t > subgraph_nodes_t; typedef std::map< id_t, edges_t > subgraph_edges_t; ///////////////////////////////////////////////////////////////////////////// // Stack frames used by semantic actions ///////////////////////////////////////////////////////////////////////////// struct id_closure : boost::spirit::classic::closure< id_closure, node_t > { member1 name; }; struct node_id_closure : boost::spirit::classic::closure< node_id_closure, node_t > { member1 name; }; struct attr_list_closure : boost::spirit::classic::closure< attr_list_closure, actor_t > { member1 prop_actor; }; struct property_closure : boost::spirit::classic::closure< property_closure, id_t, id_t > { member1 key; member2 value; }; struct data_stmt_closure : boost::spirit::classic::closure< data_stmt_closure, nodes_t, nodes_t, edge_stack_t, bool, node_t > { member1 sources; member2 dests; member3 edge_stack; member4 saw_node; member5 active_node; }; struct subgraph_closure : boost::spirit::classic::closure< subgraph_closure, nodes_t, edges_t, node_t > { member1 nodes; member2 edges; member3 name; }; ///////////////////////////////////////////////////////////////////////////// // Grammar and Actions for the DOT Language ///////////////////////////////////////////////////////////////////////////// // Grammar for a dot file. struct dot_grammar : public boost::spirit::classic::grammar< dot_grammar > { mutate_graph& graph_; explicit dot_grammar(mutate_graph& graph) : graph_(graph) {} template < class ScannerT > struct definition { definition(dot_grammar const& self) : self(self), subgraph_depth(0), keyword_p("0-9a-zA-Z_") { using namespace boost::spirit::classic; using namespace phoenix; // RG - Future Work // - Handle multi-line strings using \ line continuation // - Make keywords case insensitive ID = (lexeme_d[( (alpha_p | ch_p('_')) >> *(alnum_p | ch_p('_')))] | real_p | lexeme_d[confix_p('"', *c_escape_ch_p, '"')] | comment_nest_p('<', '>'))[ID.name = construct_< std::string >(arg1, arg2)]; a_list = list_p( ID[((a_list.key = arg1), (a_list.value = "true"))] >> !( ch_p('=') >> ID[a_list.value = arg1])[phoenix::bind( &definition::call_prop_actor)( var(*this), a_list.key, a_list.value)], !ch_p(',')); attr_list = +(ch_p('[') >> !a_list >> ch_p(']')); // RG - disregard port id's for now. port_location = (ch_p(':') >> ID) | (ch_p(':') >> ch_p('(') >> ID >> ch_p(',') >> ID >> ch_p(')')); port_angle = ch_p('@') >> ID; port = port_location >> (!port_angle) | port_angle >> (!port_location); node_id = (ID[node_id.name = arg1] >> (!port))[phoenix::bind( &definition::memoize_node)(var(*this))]; graph_stmt = (ID[graph_stmt.key = arg1] >> ch_p('=') >> ID[graph_stmt.value = arg1])[phoenix::bind( &definition::call_graph_prop)(var(*this), graph_stmt.key, graph_stmt.value)]; // Graph property. attr_stmt = (as_lower_d[keyword_p("graph")] >> attr_list(actor_t( phoenix::bind(&definition::default_graph_prop)( var(*this), arg1, arg2)))) | (as_lower_d[keyword_p("node")] >> attr_list(actor_t( phoenix::bind(&definition::default_node_prop)( var(*this), arg1, arg2)))) | (as_lower_d[keyword_p("edge")] >> attr_list(actor_t( phoenix::bind(&definition::default_edge_prop)( var(*this), arg1, arg2)))); // edge_head is set depending on the graph type // (directed/undirected) edgeop = ch_p('-') >> ch_p(boost::ref(edge_head)); edgeRHS = +(edgeop[((data_stmt.sources = data_stmt.dests), (data_stmt.dests = construct_< nodes_t >()))] >> (subgraph[data_stmt.dests = arg1] | node_id[phoenix::bind(&definition::insert_node)( var(*this), data_stmt.dests, arg1)]) [phoenix::bind(&definition::activate_edge)( var(*this), data_stmt.sources, data_stmt.dests, var(edges), var(default_edge_props))]); // To avoid backtracking, edge, node, and subgraph // statements are processed as one nonterminal. data_stmt = (subgraph[((data_stmt.dests = arg1), // will get moved in rhs (data_stmt.saw_node = false))] | node_id[((phoenix::bind( &definition::insert_node)( var(*this), data_stmt.dests, arg1)), (data_stmt.saw_node = true), #ifdef BOOST_GRAPH_DEBUG (std::cout << val("AcTive Node: ") << arg1 << "\n"), #endif // BOOST_GRAPH_DEBUG (data_stmt.active_node = arg1))]) >> if_p(edgeRHS)[!attr_list(actor_t(phoenix::bind( &definition::edge_prop)( var(*this), arg1, arg2)))] .else_p[if_p(data_stmt.saw_node)[!attr_list( actor_t(phoenix::bind( &definition::node_prop)(var(*this), arg1, arg2)))] // otherwise it's a subgraph, // nothing more to do. ]; stmt = graph_stmt | attr_stmt | data_stmt; stmt_list = *(stmt >> !ch_p(';')); subgraph = !(as_lower_d[keyword_p("subgraph")] >> (!ID[((subgraph.name = arg1), (subgraph.nodes = (var(subgraph_nodes))[arg1]), (subgraph.edges = (var(subgraph_edges))[arg1]))])) >> ch_p('{')[++var(subgraph_depth)] >> stmt_list >> ch_p('}')[--var(subgraph_depth)] [(var(subgraph_nodes))[subgraph.name] = subgraph.nodes] [(var(subgraph_edges))[subgraph.name] = subgraph.edges] | as_lower_d[keyword_p("subgraph")] >> ID[((subgraph.nodes = (var(subgraph_nodes))[arg1]), (subgraph.edges = (var(subgraph_edges))[arg1]))]; the_grammar = (!as_lower_d[keyword_p("strict")]) >> (as_lower_d[keyword_p( "graph")][((var(edge_head) = '-'), (phoenix::bind(&definition::check_undirected)( var(*this))))] | as_lower_d[keyword_p( "digraph")][((var(edge_head) = '>'), (phoenix::bind(&definition::check_directed)( var(*this))))]) >> (!ID) >> ch_p('{') >> stmt_list >> ch_p('}'); } // definition() typedef boost::spirit::classic::rule< ScannerT > rule_t; rule_t const& start() const { return the_grammar; } // // Semantic actions // void check_undirected() { if (self.graph_.is_directed()) boost::throw_exception(boost::undirected_graph_error()); } void check_directed() { if (!self.graph_.is_directed()) boost::throw_exception(boost::directed_graph_error()); } void memoize_node() { id_t const& node = node_id.name(); props_t& node_props = default_node_props; if (nodes.find(node) == nodes.end()) { nodes.insert(node); self.graph_.do_add_vertex(node); node_map.insert(std::make_pair(node, ids_t())); #ifdef BOOST_GRAPH_DEBUG std::cout << "Add new node " << node << std::endl; #endif // BOOST_GRAPH_DEBUG // Set the default properties for this edge // RG: Here I would actually set the properties for (props_t::iterator i = node_props.begin(); i != node_props.end(); ++i) { set_node_property(node, i->first, i->second); } if (subgraph_depth > 0) { subgraph.nodes().insert(node); // Set the subgraph's default properties as well props_t& props = subgraph_node_props[subgraph.name()]; for (props_t::iterator i = props.begin(); i != props.end(); ++i) { set_node_property(node, i->first, i->second); } } } else { #ifdef BOOST_GRAPH_DEBUG std::cout << "See node " << node << std::endl; #endif // BOOST_GRAPH_DEBUG } } void activate_edge(nodes_t& sources, nodes_t& dests, edges_t& edges, props_t& edge_props) { edge_stack_t& edge_stack = data_stmt.edge_stack(); for (nodes_t::iterator i = sources.begin(); i != sources.end(); ++i) { for (nodes_t::iterator j = dests.begin(); j != dests.end(); ++j) { // Create the edge and push onto the edge stack. #ifdef BOOST_GRAPH_DEBUG std::cout << "Edge " << *i << " to " << *j << std::endl; #endif // BOOST_GRAPH_DEBUG edge_t edge = edge_t::new_edge(); edge_stack.push_back(edge); edges.insert(edge); edge_map.insert(std::make_pair(edge, ids_t())); // Add the real edge. self.graph_.do_add_edge(edge, *i, *j); // Set the default properties for this edge for (props_t::iterator k = edge_props.begin(); k != edge_props.end(); ++k) { set_edge_property(edge, k->first, k->second); } if (subgraph_depth > 0) { subgraph.edges().insert(edge); // Set the subgraph's default properties as well props_t& props = subgraph_edge_props[subgraph.name()]; for (props_t::iterator k = props.begin(); k != props.end(); ++k) { set_edge_property( edge, k->first, k->second); } } } } } // node_prop - Assign the property for the current active node. void node_prop(id_t const& key, id_t const& value) { node_t& active_object = data_stmt.active_node(); set_node_property(active_object, key, value); } // edge_prop - Assign the property for the current active edges. void edge_prop(id_t const& key, id_t const& value) { edge_stack_t const& active_edges_ = data_stmt.edge_stack(); for (edge_stack_t::const_iterator i = active_edges_.begin(); i != active_edges_.end(); ++i) { set_edge_property(*i, key, value); } } // default_graph_prop - Store as a graph property. void default_graph_prop(id_t const& key, id_t const& value) { #ifdef BOOST_GRAPH_DEBUG std::cout << key << " = " << value << std::endl; #endif // BOOST_GRAPH_DEBUG self.graph_.set_graph_property(key, value); } // default_node_prop - declare default properties for any future // new nodes void default_node_prop(id_t const& key, id_t const& value) { nodes_t& nodes_ = subgraph_depth == 0 ? nodes : subgraph.nodes(); props_t& node_props_ = subgraph_depth == 0 ? default_node_props : subgraph_node_props[subgraph.name()]; // add this to the selected list of default node properties. node_props_[key] = value; // for each node, set its property to default-constructed // value // if it hasn't been set already. // set the dynamic property map value for (nodes_t::iterator i = nodes_.begin(); i != nodes_.end(); ++i) if (node_map[*i].find(key) == node_map[*i].end()) { set_node_property(*i, key, id_t()); } } // default_edge_prop - declare default properties for any future // new edges void default_edge_prop(id_t const& key, id_t const& value) { edges_t& edges_ = subgraph_depth == 0 ? edges : subgraph.edges(); props_t& edge_props_ = subgraph_depth == 0 ? default_edge_props : subgraph_edge_props[subgraph.name()]; // add this to the list of default edge properties. edge_props_[key] = value; // for each edge, set its property to be empty string // set the dynamic property map value for (edges_t::iterator i = edges_.begin(); i != edges_.end(); ++i) if (edge_map[*i].find(key) == edge_map[*i].end()) set_edge_property(*i, key, id_t()); } // helper function void insert_node(nodes_t& nodes, id_t const& name) { nodes.insert(name); } void call_prop_actor( std::string const& lhs, std::string const& rhs) { actor_t& actor = attr_list.prop_actor(); // If first and last characters of the rhs are // double-quotes, remove them. if (!rhs.empty() && rhs[0] == '"' && rhs[rhs.size() - 1] == '"') actor(lhs, rhs.substr(1, rhs.size() - 2)); else actor(lhs, rhs); } void call_graph_prop( std::string const& lhs, std::string const& rhs) { // If first and last characters of the rhs are // double-quotes, remove them. if (!rhs.empty() && rhs[0] == '"' && rhs[rhs.size() - 1] == '"') this->default_graph_prop( lhs, rhs.substr(1, rhs.size() - 2)); else this->default_graph_prop(lhs, rhs); } void set_node_property( node_t const& node, id_t const& key, id_t const& value) { // Add the property key to the "set" table to avoid default // overwrite node_map[node].insert(key); // Set the user's property map self.graph_.set_node_property(key, node, value); #ifdef BOOST_GRAPH_DEBUG // Tell the world std::cout << node << ": " << key << " = " << value << std::endl; #endif // BOOST_GRAPH_DEBUG } void set_edge_property( edge_t const& edge, id_t const& key, id_t const& value) { // Add the property key to the "set" table to avoid default // overwrite edge_map[edge].insert(key); // Set the user's property map self.graph_.set_edge_property(key, edge, value); #ifdef BOOST_GRAPH_DEBUG // Tell the world #if 0 // RG - edge representation changed, std::cout << "(" << edge.first << "," << edge.second << "): " #else std::cout << "an edge: " #endif // 0 << key << " = " << value << std::endl; #endif // BOOST_GRAPH_DEBUG } // Variables explicitly initialized dot_grammar const& self; // if subgraph_depth > 0, then we're processing a subgraph. int subgraph_depth; // Keywords; const boost::spirit::classic::distinct_parser<> keyword_p; // // rules that make up the grammar // boost::spirit::classic::rule< ScannerT, id_closure::context_t > ID; boost::spirit::classic::rule< ScannerT, property_closure::context_t > a_list; boost::spirit::classic::rule< ScannerT, attr_list_closure::context_t > attr_list; rule_t port_location; rule_t port_angle; rule_t port; boost::spirit::classic::rule< ScannerT, node_id_closure::context_t > node_id; boost::spirit::classic::rule< ScannerT, property_closure::context_t > graph_stmt; rule_t attr_stmt; boost::spirit::classic::rule< ScannerT, data_stmt_closure::context_t > data_stmt; boost::spirit::classic::rule< ScannerT, subgraph_closure::context_t > subgraph; rule_t edgeop; rule_t edgeRHS; rule_t stmt; rule_t stmt_list; rule_t the_grammar; // The grammar uses edge_head to dynamically set the syntax for // edges directed graphs: edge_head = '>', and so edgeop = "->" // undirected graphs: edge_head = '-', and so edgeop = "--" char edge_head; // // Support data structures // nodes_t nodes; // list of node names seen edges_t edges; // list of edges seen node_map_t node_map; // remember the properties set for each node edge_map_t edge_map; // remember the properties set for each edge subgraph_nodes_t subgraph_nodes; // per-subgraph lists of nodes subgraph_edges_t subgraph_edges; // per-subgraph lists of edges props_t default_node_props; // global default node properties props_t default_edge_props; // global default edge properties subgraph_props_t subgraph_node_props; // per-subgraph default node properties subgraph_props_t subgraph_edge_props; // per-subgraph default edge properties }; // struct definition }; // struct dot_grammar // // dot_skipper - GraphViz whitespace and comment skipper // struct dot_skipper : public boost::spirit::classic::grammar< dot_skipper > { dot_skipper() {} template < typename ScannerT > struct definition { definition(dot_skipper const& /*self*/) { using namespace boost::spirit::classic; using namespace phoenix; // comment forms skip = eol_p >> comment_p("#") | space_p | comment_p("//") #if BOOST_WORKAROUND(BOOST_MSVC, <= 1400) | confix_p(str_p("/*"), *anychar_p, str_p("*/")) #else | confix_p("/*", *anychar_p, "*/") #endif ; #ifdef BOOST_SPIRIT_DEBUG BOOST_SPIRIT_DEBUG_RULE(skip); #endif } boost::spirit::classic::rule< ScannerT > skip; boost::spirit::classic::rule< ScannerT > const& start() const { return skip; } }; // definition }; // dot_skipper } // namespace graph } // namespace detail template < typename MultiPassIterator, typename MutableGraph > bool read_graphviz_spirit(MultiPassIterator begin, MultiPassIterator end, MutableGraph& graph, dynamic_properties& dp, std::string const& node_id = "node_id") { using namespace boost; using namespace boost::spirit::classic; typedef MultiPassIterator iterator_t; 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::mutate_graph_impl< MutableGraph > m_graph( graph, dp, node_id); ::boost::detail::graph::dot_grammar p(m_graph); ::boost::detail::graph::dot_skipper skip_p; iter_policy_t iter_policy(skip_p); scanner_policies_t policies(iter_policy); scanner_t scan(begin, end, policies); bool ok = p.parse(scan); m_graph.finish_building_graph(); return ok; } } // namespace boost #endif // BOOST_READ_GRAPHVIZ_SPIRIT_HPP