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