read_graphviz_spirit.hpp

Boost provides free peer-reviewed portable C++ source libraries. We emphasize libraries that work

// Copyright 2004-5 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/iterator/multi_pass.hpp>
#include <boost/spirit/core.hpp>
#include <boost/spirit/utility/confix.hpp>
#include <boost/spirit/utility/distinct.hpp>
#include <boost/spirit/utility/lists.hpp>
#include <boost/spirit/utility/escape_char.hpp>
#include <boost/spirit/attribute.hpp>
#include <boost/spirit/dynamic.hpp>
#include <boost/spirit/actor.hpp>
#include <boost/spirit/phoenix.hpp>
#include <boost/spirit/phoenix/binders.hpp>
#include <boost/ref.hpp>
#include <boost/function/function2.hpp>
#include <boost/type_traits/is_same.hpp>
#include <boost/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::closure<id_closure, node_t> {
  member1 name;
};


struct node_id_closure : boost::spirit::closure<node_id_closure, node_t> {
  member1 name;
};

struct attr_list_closure : boost::spirit::closure<attr_list_closure, actor_t> {
  member1 prop_actor;
};

struct property_closure : boost::spirit::closure<property_closure, id_t, id_t> {
  member1 key;
  member2 value;
};

struct data_stmt_closure : boost::spirit::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::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::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;
      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::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;