// 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 |