| // 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: |
| // 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); |
| |
| return p.parse(scan); |
| } |
| |
| } // namespace boost |
| |
| #endif // BOOST_READ_GRAPHVIZ_SPIRIT_HPP |