1 // Copyright 2004-5 Trustees of Indiana University

     2 

     3 // Distributed under the Boost Software License, Version 1.0.

     4 // (See accompanying file LICENSE_1_0.txt or copy at

     5 // http://www.boost.org/LICENSE_1_0.txt)

     6 

     7 //

     8 // read_graphviz_spirit.hpp - 

     9 //   Initialize a model of the BGL's MutableGraph concept and an associated

    10 //  collection of property maps using a graph expressed in the GraphViz

    11 // DOT Language.  

    12 //

    13 //   Based on the grammar found at:

    14 //   http://www.graphviz.org/cvs/doc/info/lang.html

    15 //

    16 //   See documentation for this code at: 

    17 //     http://www.boost.org/libs/graph/doc/read-graphviz.html

    18 //

    19 

    20 // Author: Ronald Garcia

    21 //

    22 

    23 #ifndef BOOST_READ_GRAPHVIZ_SPIRIT_HPP

    24 #define BOOST_READ_GRAPHVIZ_SPIRIT_HPP

    25 

    26 // Phoenix/Spirit set these limits to 3, but I need more.

    27 #define PHOENIX_LIMIT 6

    28 #define BOOST_SPIRIT_CLOSURE_LIMIT 6

    29 

    30 

    31 #include <boost/spirit/iterator/multi_pass.hpp>

    32 #include <boost/spirit/core.hpp>

    33 #include <boost/spirit/utility/confix.hpp>

    34 #include <boost/spirit/utility/distinct.hpp>

    35 #include <boost/spirit/utility/lists.hpp>

    36 #include <boost/spirit/utility/escape_char.hpp>

    37 #include <boost/spirit/attribute.hpp>

    38 #include <boost/spirit/dynamic.hpp>

    39 #include <boost/spirit/actor.hpp>

    40 #include <boost/spirit/phoenix.hpp>

    41 #include <boost/spirit/phoenix/binders.hpp>

    42 #include <boost/ref.hpp>

    43 #include <boost/function/function2.hpp>

    44 #include <boost/type_traits/is_same.hpp>

    45 #include <boost/dynamic_property_map.hpp>

    46 #include <boost/graph/graph_traits.hpp>

    47 #include <boost/detail/workaround.hpp>

    48 #include <algorithm>

    49 #include <exception> // for std::exception

    50 #include <string>

    51 #include <vector>

    52 #include <set>

    53 #include <utility>

    54 #include <map>

    55 #include <boost/graph/graphviz.hpp>

    56 

    57 namespace phoenix {

    58 // Workaround:  std::map::operator[] uses a different return type than all

    59 // other standard containers.  Phoenix doesn't account for that.

    60 template <typename TK, typename T0, typename T1>

    61 struct binary_operator<index_op, std::map<TK,T0>, T1>

    62 {

    63     typedef typename std::map<TK,T0>::mapped_type& result_type;

    64     static result_type eval(std::map<TK,T0>& container, T1 const& index)

    65     { return container[index]; }

    66 };

    67 } // namespace phoenix

    68 

    69 namespace boost {

    70 namespace detail {

    71 namespace graph {

    72 

    73 

    74 /////////////////////////////////////////////////////////////////////////////

    75 // Application-specific type definitions

    76 /////////////////////////////////////////////////////////////////////////////

    77 

    78 typedef std::set<edge_t> edges_t;

    79 typedef std::set<node_t> nodes_t;

    80 typedef std::set<id_t> ids_t;

    81 typedef std::map<edge_t,ids_t> edge_map_t;

    82 typedef std::map<node_t,ids_t> node_map_t;

    83 typedef std::map<id_t,id_t> props_t;

    84 typedef std::map<id_t,props_t> subgraph_props_t;

    85 typedef boost::function2<void, id_t const&, id_t const&> actor_t;

    86 typedef std::vector<edge_t> edge_stack_t;

    87 typedef std::map<id_t,nodes_t> subgraph_nodes_t;

    88 typedef std::map<id_t,edges_t> subgraph_edges_t;

    89 

    90 

    91 

    92 /////////////////////////////////////////////////////////////////////////////

    93 // Stack frames used by semantic actions

    94 /////////////////////////////////////////////////////////////////////////////

    95 struct id_closure : boost::spirit::closure<id_closure, node_t> {

    96   member1 name;

    97 };

    98 

    99 

   100 struct node_id_closure : boost::spirit::closure<node_id_closure, node_t> {

   101   member1 name;

   102 };

   103 

   104 struct attr_list_closure : boost::spirit::closure<attr_list_closure, actor_t> {

   105   member1 prop_actor;

   106 };

   107 

   108 struct property_closure : boost::spirit::closure<property_closure, id_t, id_t> {

   109   member1 key;

   110   member2 value;

   111 };

   112 

   113 struct data_stmt_closure : boost::spirit::closure<data_stmt_closure,

   114                            nodes_t,nodes_t,edge_stack_t,bool,node_t> {

   115   member1 sources;

   116   member2 dests;

   117   member3 edge_stack;

   118   member4 saw_node;

   119   member5 active_node;

   120 };

   121 

   122 struct subgraph_closure : boost::spirit::closure<subgraph_closure,

   123                           nodes_t, edges_t, node_t> {

   124   member1 nodes;

   125   member2 edges;

   126   member3 name;

   127 };

   128 

   129 /////////////////////////////////////////////////////////////////////////////

   130 // Grammar and Actions for the DOT Language

   131 /////////////////////////////////////////////////////////////////////////////

   132 

   133 // Grammar for a dot file.

   134 struct dot_grammar : public boost::spirit::grammar<dot_grammar> { 

   135   mutate_graph& graph_;

   136   explicit dot_grammar(mutate_graph& graph) : graph_(graph) { }

   137 

   138   template <class ScannerT>

   139   struct definition {

   140    

   141     definition(dot_grammar const& self) : self(self), subgraph_depth(0),

   142     keyword_p("0-9a-zA-Z_") {

   143       using namespace boost::spirit;

   144       using namespace phoenix;

   145       

   146       // RG - Future Work

   147       // - Handle multi-line strings using \ line continuation

   148       // - Make keywords case insensitive

   149       ID 

   150           = ( lexeme_d[((alpha_p | ch_p('_')) >> *(alnum_p | ch_p('_')))]

   151             | real_p

   152             | confix_p('"', *c_escape_ch_p, '"')

   153             | comment_nest_p('<', '>')

   154             )[ID.name = construct_<std::string>(arg1,arg2)]

   155           ; 

   156 

   157       a_list

   158           = list_p( ID[(a_list.key = arg1),

   159                        (a_list.value = "true")

   160                       ]

   161                     >> !( ch_p('=')

   162                           >> ID[a_list.value = arg1])

   163                           [phoenix::bind(&definition::call_prop_actor)

   164                           (var(*this),a_list.key,a_list.value)],ch_p(','));

   165       

   166       attr_list = +(ch_p('[') >> !a_list >> ch_p(']'));

   167 

   168       // RG - disregard port id's for now.

   169       port_location 

   170           = (ch_p(':') >> ID)

   171           | (ch_p(':') >> ch_p('(') >> ID >> ch_p(',') >> ID >> ch_p(')'))

   172           ;

   173 

   174       port_angle = ch_p('@') >> ID;

   175 

   176       port

   177           = port_location >> (!port_angle)

   178           | port_angle >> (!port_location);

   179 

   180 

   181       node_id

   182           = ( ID[node_id.name = arg1] >> (!port) )

   183              [phoenix::bind(&definition::memoize_node)(var(*this))];

   184 

   185       attr_stmt

   186           = (as_lower_d[keyword_p("graph")]

   187              >> attr_list(actor_t(phoenix::bind(&definition::default_graph_prop)

   188                                      (var(*this),arg1,arg2))))

   189           | (as_lower_d[keyword_p("node")]

   190              >> attr_list(actor_t(phoenix::bind(&definition::default_node_prop)

   191                                      (var(*this),arg1,arg2))))

   192           | (as_lower_d[keyword_p("edge")]

   193              >> attr_list(actor_t(phoenix::bind(&definition::default_edge_prop)

   194                                      (var(*this),arg1,arg2))))

   195           ;

   196 

   197       // edge_head is set depending on the graph type (directed/undirected)

   198       edgeop = ch_p('-') >> ch_p(boost::ref(edge_head));

   199 

   200       edgeRHS

   201           =  +(    edgeop[(data_stmt.sources = data_stmt.dests),

   202                           (data_stmt.dests = construct_<nodes_t>())]

   203                    >> ( subgraph[data_stmt.dests = arg1]

   204                       | node_id[phoenix::bind(&definition::insert_node)

   205                                 (var(*this),data_stmt.dests,arg1)]

   206                       )

   207                    [phoenix::bind(&definition::activate_edge)

   208                     (var(*this),data_stmt.sources,data_stmt.dests,

   209                      var(edges), var(default_edge_props))]

   210               );

   211       

   212 

   213       // To avoid backtracking, edge, node, and subgraph statements are

   214       // processed as one nonterminal.

   215       data_stmt

   216           = ( subgraph[(data_stmt.dests = arg1),// will get moved in rhs

   217                        (data_stmt.saw_node = false)] 

   218             | node_id[(phoenix::bind(&definition::insert_node)

   219                        (var(*this),data_stmt.dests,arg1)),

   220                       (data_stmt.saw_node = true),

   221 #ifdef BOOST_GRAPH_DEBUG

   222                       (std::cout << val("AcTive Node: ") << arg1 << "\n"),

   223 #endif // BOOST_GRAPH_DEBUG

   224                       (data_stmt.active_node = arg1)]

   225             ) >> if_p(edgeRHS)[

   226                      !attr_list(

   227                        actor_t(phoenix::bind(&definition::edge_prop)

   228                                (var(*this),arg1,arg2)))

   229                   ].else_p[

   230                      if_p(data_stmt.saw_node)[

   231                          !attr_list(

   232                            actor_t(phoenix::bind(&definition::node_prop)

   233                                    (var(*this),arg1,arg2)))

   234                      ] // otherwise it's a subgraph, nothing more to do.

   235                   ];

   236 

   237 

   238       stmt

   239           = (ID >> ch_p('=') >> ID) // Graph property -- ignore.

   240           | attr_stmt

   241           | data_stmt

   242           ;

   243 

   244       stmt_list = *( stmt >> !ch_p(';') );

   245 

   246       subgraph

   247           = !(  as_lower_d[keyword_p("subgraph")]

   248                 >> (!ID[(subgraph.name = arg1), 

   249                         (subgraph.nodes = (var(subgraph_nodes))[arg1]),

   250                         (subgraph.edges = (var(subgraph_edges))[arg1])])

   251                 )

   252           >> ch_p('{')[++var(subgraph_depth)]

   253           >> stmt_list 

   254           >> ch_p('}')[--var(subgraph_depth)]

   255                       [(var(subgraph_nodes))[subgraph.name] = subgraph.nodes]

   256                       [(var(subgraph_edges))[subgraph.name] = subgraph.edges]

   257                      

   258           | as_lower_d[keyword_p("subgraph")]

   259                 >> ID[(subgraph.nodes = (var(subgraph_nodes))[arg1]),

   260                       (subgraph.edges = (var(subgraph_edges))[arg1])]

   261           ;

   262 

   263       the_grammar

   264           = (!as_lower_d[keyword_p("strict")])

   265             >>  ( as_lower_d[keyword_p("graph")][

   266                    (var(edge_head) = '-'),

   267                    (phoenix::bind(&definition::check_undirected)(var(*this)))]

   268                 | as_lower_d[keyword_p("digraph")][

   269                    (var(edge_head) = '>'),

   270                    (phoenix::bind(&definition::check_directed)(var(*this)))]

   271                 )

   272             >> (!ID) >> ch_p('{') >> stmt_list >> ch_p('}');

   273 

   274     } // definition()

   275 

   276     typedef boost::spirit::rule<ScannerT> rule_t;

   277 

   278     rule_t const& start() const { return the_grammar; }

   279 

   280 

   281     //  

   282     // Semantic actions

   283     //

   284 

   285     void check_undirected() {

   286       if(self.graph_.is_directed())

   287         throw boost::undirected_graph_error();

   288     }

   289 

   290     void check_directed() {

   291       if(!self.graph_.is_directed())

   292         throw boost::directed_graph_error();

   293     }

   294     

   295     void memoize_node() {

   296       id_t const& node = node_id.name();

   297       props_t& node_props = default_node_props; 

   298 

   299       if(nodes.find(node) == nodes.end()) {

   300         nodes.insert(node);

   301         self.graph_.do_add_vertex(node);

   302 

   303         node_map.insert(std::make_pair(node,ids_t()));

   304 

   305 #ifdef BOOST_GRAPH_DEBUG

   306         std::cout << "Add new node " << node << std::endl;

   307 #endif // BOOST_GRAPH_DEBUG

   308         // Set the default properties for this edge

   309         // RG: Here I  would actually set the properties

   310         for(props_t::iterator i = node_props.begin();

   311             i != node_props.end(); ++i) {

   312           set_node_property(node,i->first,i->second);

   313         }

   314         if(subgraph_depth > 0) {

   315           subgraph.nodes().insert(node);

   316           // Set the subgraph's default properties as well

   317           props_t& props = subgraph_node_props[subgraph.name()];

   318           for(props_t::iterator i = props.begin(); i != props.end(); ++i) {

   319             set_node_property(node,i->first,i->second);

   320           }

   321         }

   322       } else {

   323 #ifdef BOOST_GRAPH_DEBUG

   324         std::cout << "See node " << node << std::endl;

   325 #endif // BOOST_GRAPH_DEBUG

   326       }

   327     }

   328 

   329     void activate_edge(nodes_t& sources, nodes_t& dests, edges_t& edges,

   330                        props_t& edge_props) {

   331       edge_stack_t& edge_stack = data_stmt.edge_stack();

   332       for(nodes_t::iterator i = sources.begin(); i != sources.end(); ++i) {

   333         for(nodes_t::iterator j = dests.begin(); j != dests.end(); ++j) {

   334           // Create the edge and and push onto the edge stack.

   335 #ifdef BOOST_GRAPH_DEBUG

   336           std::cout << "Edge " << *i << " to " << *j << std::endl;

   337 #endif // BOOST_GRAPH_DEBUG

   338 

   339           edge_t edge = edge_t::new_edge();

   340           edge_stack.push_back(edge);

   341           edges.insert(edge);

   342           edge_map.insert(std::make_pair(edge,ids_t()));

   343 

   344           // Add the real edge.

   345           self.graph_.do_add_edge(edge, *i, *j);

   346 

   347           // Set the default properties for this edge

   348           for(props_t::iterator k = edge_props.begin();

   349               k != edge_props.end(); ++k) {

   350             set_edge_property(edge,k->first,k->second);

   351           }

   352           if(subgraph_depth > 0) {

   353             subgraph.edges().insert(edge);

   354             // Set the subgraph's default properties as well

   355             props_t& props = subgraph_edge_props[subgraph.name()];

   356             for(props_t::iterator k = props.begin(); k != props.end(); ++k) {

   357               set_edge_property(edge,k->first,k->second);

   358             }

   359           }

   360         }

   361       }

   362     }

   363 

   364     // node_prop - Assign the property for the current active node.

   365     void node_prop(id_t const& key, id_t const& value) {

   366       node_t& active_object = data_stmt.active_node();

   367       set_node_property(active_object, key, value);

   368     }

   369 

   370     // edge_prop - Assign the property for the current active edges.

   371     void edge_prop(id_t const& key, id_t const& value) {

   372       edge_stack_t const& active_edges_ = data_stmt.edge_stack();

   373       for (edge_stack_t::const_iterator i = active_edges_.begin();

   374            i != active_edges_.end(); ++i) {

   375         set_edge_property(*i,key,value);

   376       }

   377     }

   378 

   379     // default_graph_prop - Just ignore graph properties.

   380     void default_graph_prop(id_t const&, id_t const&) { }

   381 

   382     // default_node_prop - declare default properties for any future new nodes

   383     void default_node_prop(id_t const& key, id_t const& value) {

   384       nodes_t& nodes_ =

   385         subgraph_depth == 0 ? nodes : subgraph.nodes();

   386       props_t& node_props_ =

   387         subgraph_depth == 0 ?

   388         default_node_props :

   389         subgraph_node_props[subgraph.name()];

   390 

   391       // add this to the selected list of default node properties.

   392       node_props_[key] = value;

   393       // for each node, set its property to default-constructed value 

   394       //   if it hasn't been set already.

   395       // set the dynamic property map value

   396       for(nodes_t::iterator i = nodes_.begin(); i != nodes_.end(); ++i)

   397         if(node_map[*i].find(key) == node_map[*i].end()) {

   398           set_node_property(*i,key,id_t());

   399         }

   400     }

   401 

   402     // default_edge_prop - declare default properties for any future new edges

   403    void default_edge_prop(id_t const& key, id_t const& value) {

   404       edges_t& edges_ =

   405         subgraph_depth == 0 ? edges : subgraph.edges();

   406       props_t& edge_props_ =

   407         subgraph_depth == 0 ?

   408         default_edge_props :

   409         subgraph_edge_props[subgraph.name()];

   410   

   411       // add this to the list of default edge properties.

   412       edge_props_[key] = value;

   413       // for each edge, set its property to be empty string

   414       // set the dynamic property map value

   415       for(edges_t::iterator i = edges_.begin(); i != edges_.end(); ++i)

   416         if(edge_map[*i].find(key) == edge_map[*i].end())

   417           set_edge_property(*i,key,id_t());

   418     }

   419 

   420     // helper function

   421     void insert_node(nodes_t& nodes, id_t const& name) {

   422       nodes.insert(name);

   423     }

   424 

   425     void call_prop_actor(std::string const& lhs, std::string const& rhs) {

   426       actor_t& actor = attr_list.prop_actor();

   427       // If first and last characters of the rhs are double-quotes,

   428       // remove them.

   429       if (!rhs.empty() && rhs[0] == '"' && rhs[rhs.size() - 1] == '"')

   430         actor(lhs, rhs.substr(1, rhs.size()-2));

   431       else

   432         actor(lhs,rhs);

   433     }

   434 

   435     void set_node_property(node_t const& node, id_t const& key,

   436                            id_t const& value) {

   437 

   438       // Add the property key to the "set" table to avoid default overwrite

   439       node_map[node].insert(key);

   440       // Set the user's property map

   441       self.graph_.set_node_property(key, node, value);

   442 #ifdef BOOST_GRAPH_DEBUG

   443       // Tell the world

   444       std::cout << node << ": " << key << " = " << value << std::endl;

   445 #endif // BOOST_GRAPH_DEBUG

   446     }

   447 

   448     void set_edge_property(edge_t const& edge, id_t const& key,

   449                            id_t const& value) {

   450 

   451       // Add the property key to the "set" table to avoid default overwrite

   452       edge_map[edge].insert(key);

   453       // Set the user's property map

   454       self.graph_.set_edge_property(key, edge, value);

   455 #ifdef BOOST_GRAPH_DEBUG

   456       // Tell the world

   457       std::cout << "(" << edge.first << "," << edge.second << "): "

   458                 << key << " = " << value << std::endl;

   459 #endif // BOOST_GRAPH_DEBUG

   460     }

   461 

   462     // Variables explicitly initialized

   463     dot_grammar const& self;

   464     // if subgraph_depth > 0, then we're processing a subgraph.

   465     int subgraph_depth; 

   466 

   467     // Keywords;

   468     const boost::spirit::distinct_parser<> keyword_p;

   469     //

   470     // rules that make up the grammar

   471     //

   472     boost::spirit::rule<ScannerT,id_closure::context_t> ID;

   473     boost::spirit::rule<ScannerT,property_closure::context_t> a_list;

   474     boost::spirit::rule<ScannerT,attr_list_closure::context_t> attr_list;

   475     rule_t port_location;

   476     rule_t port_angle;

   477     rule_t port;

   478     boost::spirit::rule<ScannerT,node_id_closure::context_t> node_id;

   479     rule_t attr_stmt;

   480     boost::spirit::rule<ScannerT,data_stmt_closure::context_t> data_stmt;

   481     boost::spirit::rule<ScannerT,subgraph_closure::context_t> subgraph;

   482     rule_t edgeop;

   483     rule_t edgeRHS;

   484     rule_t stmt;

   485     rule_t stmt_list;

   486     rule_t the_grammar;

   487 

   488     

   489     // The grammar uses edge_head to dynamically set the syntax for edges

   490     // directed graphs: edge_head = '>', and so edgeop = "->"

   491     // undirected graphs: edge_head = '-', and so edgeop = "--"

   492     char edge_head;

   493 

   494 

   495     // 

   496     // Support data structures

   497     //

   498 

   499     nodes_t nodes;  // list of node names seen

   500     edges_t edges;  // list of edges seen

   501     node_map_t node_map; // remember the properties set for each node

   502     edge_map_t edge_map; // remember the properties set for each edge

   503 

   504     subgraph_nodes_t subgraph_nodes;   // per-subgraph lists of nodes

   505     subgraph_edges_t subgraph_edges;   // per-subgraph lists of edges

   506     

   507     props_t default_node_props;  // global default node properties

   508     props_t default_edge_props;  // global default edge properties

   509     subgraph_props_t subgraph_node_props;  // per-subgraph default node properties

   510     subgraph_props_t subgraph_edge_props;  // per-subgraph default edge properties

   511   }; // struct definition

   512 }; // struct dot_grammar

   513 

   514 

   515 

   516 //

   517 // dot_skipper - GraphViz whitespace and comment skipper

   518 //

   519 struct dot_skipper : public boost::spirit::grammar<dot_skipper>

   520 {

   521     dot_skipper() {}

   522 

   523     template <typename ScannerT>

   524     struct definition

   525     {

   526         definition(dot_skipper const& /*self*/)  {

   527           using namespace boost::spirit;

   528           using namespace phoenix;

   529           // comment forms

   530           skip = space_p

   531                | comment_p("//")                 

   532                | comment_p("#")  

   533 #if BOOST_WORKAROUND(BOOST_MSVC, <= 1400)

   534                | confix_p(str_p("/*") ,*anychar_p, str_p("*/"))

   535 #else

   536                | confix_p("/*" ,*anychar_p, "*/")

   537 #endif

   538                ;

   539 

   540 #ifdef BOOST_SPIRIT_DEBUG

   541                BOOST_SPIRIT_DEBUG_RULE(skip);

   542 #endif

   543         }

   544 

   545       boost::spirit::rule<ScannerT>  skip;

   546       boost::spirit::rule<ScannerT> const&

   547       start() const { return skip; }

   548     }; // definition

   549 }; // dot_skipper

   550 

   551 } // namespace graph

   552 } // namespace detail

   553 

   554 template <typename MultiPassIterator, typename MutableGraph>

   555 bool read_graphviz(MultiPassIterator begin, MultiPassIterator end,

   556                    MutableGraph& graph, dynamic_properties& dp,

   557                    std::string const& node_id = "node_id") {

   558   using namespace boost;

   559   using namespace boost::spirit;

   560 

   561   typedef MultiPassIterator iterator_t;

   562   typedef skip_parser_iteration_policy< boost::detail::graph::dot_skipper>

   563     iter_policy_t;

   564   typedef scanner_policies<iter_policy_t> scanner_policies_t;

   565   typedef scanner<iterator_t, scanner_policies_t> scanner_t;

   566 

   567   ::boost::detail::graph::mutate_graph_impl<MutableGraph> 

   568       m_graph(graph, dp, node_id);

   569 

   570   ::boost::detail::graph::dot_grammar p(m_graph);

   571   ::boost::detail::graph::dot_skipper skip_p;

   572 

   573   iter_policy_t iter_policy(skip_p);

   574   scanner_policies_t policies(iter_policy);

   575 

   576   scanner_t scan(begin, end, policies);

   577 

   578   return p.parse(scan);

   579 }

   580 

   581 } // namespace boost

   582 

   583 #endif // BOOST_READ_GRAPHVIZ_SPIRIT_HPP