[857] | 1 | // Copyright 2004-5 Trustees of Indiana University
|
---|
| 2 |
|
---|
| 3 | // Use, modification and distribution is subject to the Boost Software
|
---|
| 4 | // License, Version 1.0. (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 | using namespace std;
|
---|
| 74 | using namespace boost;
|
---|
| 75 | using namespace boost::spirit;
|
---|
| 76 | using namespace phoenix;
|
---|
| 77 |
|
---|
| 78 | /////////////////////////////////////////////////////////////////////////////
|
---|
| 79 | // Application-specific type definitions
|
---|
| 80 | /////////////////////////////////////////////////////////////////////////////
|
---|
| 81 |
|
---|
| 82 | typedef std::set<edge_t> edges_t;
|
---|
| 83 | typedef std::set<node_t> nodes_t;
|
---|
| 84 | typedef std::set<id_t> ids_t;
|
---|
| 85 | typedef std::map<edge_t,ids_t> edge_map_t;
|
---|
| 86 | typedef std::map<node_t,ids_t> node_map_t;
|
---|
| 87 | typedef std::map<id_t,id_t> props_t;
|
---|
| 88 | typedef std::map<id_t,props_t> subgraph_props_t;
|
---|
| 89 | typedef boost::function2<void, id_t const&, id_t const&> actor_t;
|
---|
| 90 | typedef std::vector<edge_t> edge_stack_t;
|
---|
| 91 | typedef std::map<id_t,nodes_t> subgraph_nodes_t;
|
---|
| 92 | typedef std::map<id_t,edges_t> subgraph_edges_t;
|
---|
| 93 |
|
---|
| 94 |
|
---|
| 95 |
|
---|
| 96 | /////////////////////////////////////////////////////////////////////////////
|
---|
| 97 | // Stack frames used by semantic actions
|
---|
| 98 | /////////////////////////////////////////////////////////////////////////////
|
---|
| 99 | struct id_closure : boost::spirit::closure<id_closure, node_t> {
|
---|
| 100 | member1 name;
|
---|
| 101 | };
|
---|
| 102 |
|
---|
| 103 |
|
---|
| 104 | struct node_id_closure : boost::spirit::closure<node_id_closure, node_t> {
|
---|
| 105 | member1 name;
|
---|
| 106 | };
|
---|
| 107 |
|
---|
| 108 | struct attr_list_closure : boost::spirit::closure<attr_list_closure, actor_t> {
|
---|
| 109 | member1 prop_actor;
|
---|
| 110 | };
|
---|
| 111 |
|
---|
| 112 | struct property_closure : boost::spirit::closure<property_closure, id_t, id_t> {
|
---|
| 113 | member1 key;
|
---|
| 114 | member2 value;
|
---|
| 115 | };
|
---|
| 116 |
|
---|
| 117 | struct data_stmt_closure : boost::spirit::closure<data_stmt_closure,
|
---|
| 118 | nodes_t,nodes_t,edge_stack_t,bool,node_t> {
|
---|
| 119 | member1 sources;
|
---|
| 120 | member2 dests;
|
---|
| 121 | member3 edge_stack;
|
---|
| 122 | member4 saw_node;
|
---|
| 123 | member5 active_node;
|
---|
| 124 | };
|
---|
| 125 |
|
---|
| 126 | struct subgraph_closure : boost::spirit::closure<subgraph_closure,
|
---|
| 127 | nodes_t, edges_t, node_t> {
|
---|
| 128 | member1 nodes;
|
---|
| 129 | member2 edges;
|
---|
| 130 | member3 name;
|
---|
| 131 | };
|
---|
| 132 |
|
---|
| 133 | /////////////////////////////////////////////////////////////////////////////
|
---|
| 134 | // Grammar and Actions for the DOT Language
|
---|
| 135 | /////////////////////////////////////////////////////////////////////////////
|
---|
| 136 |
|
---|
| 137 | // Grammar for a dot file.
|
---|
| 138 | struct dot_grammar : public grammar<dot_grammar> {
|
---|
| 139 | mutate_graph& graph_;
|
---|
| 140 | explicit dot_grammar(mutate_graph& graph) : graph_(graph) { }
|
---|
| 141 |
|
---|
| 142 | template <class ScannerT>
|
---|
| 143 | struct definition {
|
---|
| 144 |
|
---|
| 145 | definition(dot_grammar const& self) : self(self), subgraph_depth(0),
|
---|
| 146 | keyword_p("0-9a-zA-Z_") {
|
---|
| 147 |
|
---|
| 148 |
|
---|
| 149 | // RG - Future Work
|
---|
| 150 | // - Handle multi-line strings using \ line continuation
|
---|
| 151 | // - Make keywords case insensitive
|
---|
| 152 |
|
---|
| 153 | ID
|
---|
| 154 | = ( lexeme_d[((alpha_p | ch_p('_')) >> *(alnum_p | ch_p('_')))]
|
---|
| 155 | | real_p
|
---|
| 156 | | confix_p('"', *c_escape_ch_p, '"')
|
---|
| 157 | | comment_nest_p('<', '>')
|
---|
| 158 | )[ID.name = construct_<std::string>(arg1,arg2)]
|
---|
| 159 | ;
|
---|
| 160 |
|
---|
| 161 | a_list
|
---|
| 162 | = list_p( ID[(a_list.key = arg1),
|
---|
| 163 | (a_list.value = "true")
|
---|
| 164 | ]
|
---|
| 165 | >> !( ch_p('=')
|
---|
| 166 | >> ID[a_list.value = arg1])
|
---|
| 167 | [phoenix::bind(&definition::call_prop_actor)
|
---|
| 168 | (var(*this),a_list.key,a_list.value)],ch_p(','));
|
---|
| 169 |
|
---|
| 170 | attr_list = +(ch_p('[') >> !a_list >> ch_p(']'));
|
---|
| 171 |
|
---|
| 172 | // RG - disregard port id's for now.
|
---|
| 173 | port_location
|
---|
| 174 | = (ch_p(':') >> ID)
|
---|
| 175 | | (ch_p(':') >> ch_p('(') >> ID >> ch_p(',') >> ID >> ch_p(')'))
|
---|
| 176 | ;
|
---|
| 177 |
|
---|
| 178 | port_angle = ch_p('@') >> ID;
|
---|
| 179 |
|
---|
| 180 | port
|
---|
| 181 | = port_location >> (!port_angle)
|
---|
| 182 | | port_angle >> (!port_location);
|
---|
| 183 |
|
---|
| 184 |
|
---|
| 185 | node_id
|
---|
| 186 | = ( ID[node_id.name = arg1] >> (!port) )
|
---|
| 187 | [phoenix::bind(&definition::memoize_node)(var(*this))];
|
---|
| 188 |
|
---|
| 189 | attr_stmt
|
---|
| 190 | = (as_lower_d[keyword_p("graph")]
|
---|
| 191 | >> attr_list(actor_t(phoenix::bind(&definition::default_graph_prop)
|
---|
| 192 | (var(*this),arg1,arg2))))
|
---|
| 193 | | (as_lower_d[keyword_p("node")]
|
---|
| 194 | >> attr_list(actor_t(phoenix::bind(&definition::default_node_prop)
|
---|
| 195 | (var(*this),arg1,arg2))))
|
---|
| 196 | | (as_lower_d[keyword_p("edge")]
|
---|
| 197 | >> attr_list(actor_t(phoenix::bind(&definition::default_edge_prop)
|
---|
| 198 | (var(*this),arg1,arg2))))
|
---|
| 199 | ;
|
---|
| 200 |
|
---|
| 201 | // edge_head is set depending on the graph type (directed/undirected)
|
---|
| 202 | edgeop = ch_p('-') >> ch_p(boost::ref(edge_head));
|
---|
| 203 |
|
---|
| 204 | edgeRHS
|
---|
| 205 | = +( edgeop[(data_stmt.sources = data_stmt.dests),
|
---|
| 206 | (data_stmt.dests = construct_<nodes_t>())]
|
---|
| 207 | >> ( subgraph[data_stmt.dests = arg1]
|
---|
| 208 | | node_id[phoenix::bind(&definition::insert_node)
|
---|
| 209 | (var(*this),data_stmt.dests,arg1)]
|
---|
| 210 | )
|
---|
| 211 | [phoenix::bind(&definition::activate_edge)
|
---|
| 212 | (var(*this),data_stmt.sources,data_stmt.dests,
|
---|
| 213 | var(edges), var(default_edge_props))]
|
---|
| 214 | );
|
---|
| 215 |
|
---|
| 216 |
|
---|
| 217 | // To avoid backtracking, edge, node, and subgraph statements are
|
---|
| 218 | // processed as one nonterminal.
|
---|
| 219 | data_stmt
|
---|
| 220 | = ( subgraph[(data_stmt.dests = arg1),// will get moved in rhs
|
---|
| 221 | (data_stmt.saw_node = false)]
|
---|
| 222 | | node_id[(phoenix::bind(&definition::insert_node)
|
---|
| 223 | (var(*this),data_stmt.dests,arg1)),
|
---|
| 224 | (data_stmt.saw_node = true),
|
---|
| 225 | #ifdef BOOST_GRAPH_DEBUG
|
---|
| 226 | (std::cout << val("AcTive Node: ") << arg1 << "\n"),
|
---|
| 227 | #endif // BOOST_GRAPH_DEBUG
|
---|
| 228 | (data_stmt.active_node = arg1)]
|
---|
| 229 | ) >> if_p(edgeRHS)[
|
---|
| 230 | !attr_list(
|
---|
| 231 | actor_t(phoenix::bind(&definition::edge_prop)
|
---|
| 232 | (var(*this),arg1,arg2)))
|
---|
| 233 | ].else_p[
|
---|
| 234 | if_p(data_stmt.saw_node)[
|
---|
| 235 | !attr_list(
|
---|
| 236 | actor_t(phoenix::bind(&definition::node_prop)
|
---|
| 237 | (var(*this),arg1,arg2)))
|
---|
| 238 | ] // otherwise it's a subgraph, nothing more to do.
|
---|
| 239 | ];
|
---|
| 240 |
|
---|
| 241 |
|
---|
| 242 | stmt
|
---|
| 243 | = (ID >> ch_p('=') >> ID) // Graph property -- ignore.
|
---|
| 244 | | attr_stmt
|
---|
| 245 | | data_stmt
|
---|
| 246 | ;
|
---|
| 247 |
|
---|
| 248 | stmt_list = *( stmt >> !ch_p(';') );
|
---|
| 249 |
|
---|
| 250 | subgraph
|
---|
| 251 | = !( as_lower_d[keyword_p("subgraph")]
|
---|
| 252 | >> (!ID[(subgraph.name = arg1),
|
---|
| 253 | (subgraph.nodes = (var(subgraph_nodes))[arg1]),
|
---|
| 254 | (subgraph.edges = (var(subgraph_edges))[arg1])])
|
---|
| 255 | )
|
---|
| 256 | >> ch_p('{')[++var(subgraph_depth)]
|
---|
| 257 | >> stmt_list
|
---|
| 258 | >> ch_p('}')[--var(subgraph_depth)]
|
---|
| 259 | [(var(subgraph_nodes))[subgraph.name] = subgraph.nodes]
|
---|
| 260 | [(var(subgraph_edges))[subgraph.name] = subgraph.edges]
|
---|
| 261 |
|
---|
| 262 | | as_lower_d[keyword_p("subgraph")]
|
---|
| 263 | >> ID[(subgraph.nodes = (var(subgraph_nodes))[arg1]),
|
---|
| 264 | (subgraph.edges = (var(subgraph_edges))[arg1])]
|
---|
| 265 | ;
|
---|
| 266 |
|
---|
| 267 | the_grammar
|
---|
| 268 | = (!as_lower_d[keyword_p("strict")])
|
---|
| 269 | >> ( as_lower_d[keyword_p("graph")][
|
---|
| 270 | (var(edge_head) = '-'),
|
---|
| 271 | (phoenix::bind(&definition::check_undirected)(var(*this)))]
|
---|
| 272 | | as_lower_d[keyword_p("digraph")][
|
---|
| 273 | (var(edge_head) = '>'),
|
---|
| 274 | (phoenix::bind(&definition::check_directed)(var(*this)))]
|
---|
| 275 | )
|
---|
| 276 | >> (!ID) >> ch_p('{') >> stmt_list >> ch_p('}');
|
---|
| 277 |
|
---|
| 278 | } // definition()
|
---|
| 279 |
|
---|
| 280 | typedef rule<ScannerT> rule_t;
|
---|
| 281 |
|
---|
| 282 | rule_t const& start() const { return the_grammar; }
|
---|
| 283 |
|
---|
| 284 |
|
---|
| 285 | //
|
---|
| 286 | // Semantic actions
|
---|
| 287 | //
|
---|
| 288 |
|
---|
| 289 | void check_undirected() {
|
---|
| 290 | if(self.graph_.is_directed())
|
---|
| 291 | throw boost::undirected_graph_error();
|
---|
| 292 | }
|
---|
| 293 |
|
---|
| 294 | void check_directed() {
|
---|
| 295 | if(!self.graph_.is_directed())
|
---|
| 296 | throw boost::directed_graph_error();
|
---|
| 297 | }
|
---|
| 298 |
|
---|
| 299 | void memoize_node() {
|
---|
| 300 | id_t const& node = node_id.name();
|
---|
| 301 | props_t& node_props = default_node_props;
|
---|
| 302 |
|
---|
| 303 | if(nodes.find(node) == nodes.end()) {
|
---|
| 304 | nodes.insert(node);
|
---|
| 305 | self.graph_.do_add_vertex(node);
|
---|
| 306 |
|
---|
| 307 | node_map.insert(std::make_pair(node,ids_t()));
|
---|
| 308 |
|
---|
| 309 | #ifdef BOOST_GRAPH_DEBUG
|
---|
| 310 | std::cout << "Add new node " << node << std::endl;
|
---|
| 311 | #endif // BOOST_GRAPH_DEBUG
|
---|
| 312 | // Set the default properties for this edge
|
---|
| 313 | // RG: Here I would actually set the properties
|
---|
| 314 | for(props_t::iterator i = node_props.begin();
|
---|
| 315 | i != node_props.end(); ++i) {
|
---|
| 316 | set_node_property(node,i->first,i->second);
|
---|
| 317 | }
|
---|
| 318 | if(subgraph_depth > 0) {
|
---|
| 319 | subgraph.nodes().insert(node);
|
---|
| 320 | // Set the subgraph's default properties as well
|
---|
| 321 | props_t& props = subgraph_node_props[subgraph.name()];
|
---|
| 322 | for(props_t::iterator i = props.begin(); i != props.end(); ++i) {
|
---|
| 323 | set_node_property(node,i->first,i->second);
|
---|
| 324 | }
|
---|
| 325 | }
|
---|
| 326 | } else {
|
---|
| 327 | #ifdef BOOST_GRAPH_DEBUG
|
---|
| 328 | std::cout << "See node " << node << std::endl;
|
---|
| 329 | #endif // BOOST_GRAPH_DEBUG
|
---|
| 330 | }
|
---|
| 331 | }
|
---|
| 332 |
|
---|
| 333 | void activate_edge(nodes_t& sources, nodes_t& dests, edges_t& edges,
|
---|
| 334 | props_t& edge_props) {
|
---|
| 335 | edge_stack_t& edge_stack = data_stmt.edge_stack();
|
---|
| 336 | for(nodes_t::iterator i = sources.begin(); i != sources.end(); ++i) {
|
---|
| 337 | for(nodes_t::iterator j = dests.begin(); j != dests.end(); ++j) {
|
---|
| 338 | // Create the edge and and push onto the edge stack.
|
---|
| 339 | #ifdef BOOST_GRAPH_DEBUG
|
---|
| 340 | std::cout << "Edge " << *i << " to " << *j << std::endl;
|
---|
| 341 | #endif // BOOST_GRAPH_DEBUG
|
---|
| 342 |
|
---|
| 343 | edge_t edge = edge_t::new_edge();
|
---|
| 344 | edge_stack.push_back(edge);
|
---|
| 345 | edges.insert(edge);
|
---|
| 346 | edge_map.insert(std::make_pair(edge,ids_t()));
|
---|
| 347 |
|
---|
| 348 | // Add the real edge.
|
---|
| 349 | self.graph_.do_add_edge(edge, *i, *j);
|
---|
| 350 |
|
---|
| 351 | // Set the default properties for this edge
|
---|
| 352 | for(props_t::iterator k = edge_props.begin();
|
---|
| 353 | k != edge_props.end(); ++k) {
|
---|
| 354 | set_edge_property(edge,k->first,k->second);
|
---|
| 355 | }
|
---|
| 356 | if(subgraph_depth > 0) {
|
---|
| 357 | subgraph.edges().insert(edge);
|
---|
| 358 | // Set the subgraph's default properties as well
|
---|
| 359 | props_t& props = subgraph_edge_props[subgraph.name()];
|
---|
| 360 | for(props_t::iterator k = props.begin(); k != props.end(); ++k) {
|
---|
| 361 | set_edge_property(edge,k->first,k->second);
|
---|
| 362 | }
|
---|
| 363 | }
|
---|
| 364 | }
|
---|
| 365 | }
|
---|
| 366 | }
|
---|
| 367 |
|
---|
| 368 | // node_prop - Assign the property for the current active node.
|
---|
| 369 | void node_prop(id_t const& key, id_t const& value) {
|
---|
| 370 | node_t& active_object = data_stmt.active_node();
|
---|
| 371 | set_node_property(active_object, key, value);
|
---|
| 372 | }
|
---|
| 373 |
|
---|
| 374 | // edge_prop - Assign the property for the current active edges.
|
---|
| 375 | void edge_prop(id_t const& key, id_t const& value) {
|
---|
| 376 | edge_stack_t const& active_edges_ = data_stmt.edge_stack();
|
---|
| 377 | for (edge_stack_t::const_iterator i = active_edges_.begin();
|
---|
| 378 | i != active_edges_.end(); ++i) {
|
---|
| 379 | set_edge_property(*i,key,value);
|
---|
| 380 | }
|
---|
| 381 | }
|
---|
| 382 |
|
---|
| 383 | // default_graph_prop - Just ignore graph properties.
|
---|
| 384 | void default_graph_prop(id_t const&, id_t const&) { }
|
---|
| 385 |
|
---|
| 386 | // default_node_prop - declare default properties for any future new nodes
|
---|
| 387 | void default_node_prop(id_t const& key, id_t const& value) {
|
---|
| 388 | nodes_t& nodes_ =
|
---|
| 389 | subgraph_depth == 0 ? nodes : subgraph.nodes();
|
---|
| 390 | props_t& node_props_ =
|
---|
| 391 | subgraph_depth == 0 ?
|
---|
| 392 | default_node_props :
|
---|
| 393 | subgraph_node_props[subgraph.name()];
|
---|
| 394 |
|
---|
| 395 | // add this to the selected list of default node properties.
|
---|
| 396 | node_props_[key] = value;
|
---|
| 397 | // for each node, set its property to default-constructed value
|
---|
| 398 | // if it hasn't been set already.
|
---|
| 399 | // set the dynamic property map value
|
---|
| 400 | for(nodes_t::iterator i = nodes_.begin(); i != nodes_.end(); ++i)
|
---|
| 401 | if(node_map[*i].find(key) == node_map[*i].end()) {
|
---|
| 402 | set_node_property(*i,key,id_t());
|
---|
| 403 | }
|
---|
| 404 | }
|
---|
| 405 |
|
---|
| 406 | // default_edge_prop - declare default properties for any future new edges
|
---|
| 407 | void default_edge_prop(id_t const& key, id_t const& value) {
|
---|
| 408 | edges_t& edges_ =
|
---|
| 409 | subgraph_depth == 0 ? edges : subgraph.edges();
|
---|
| 410 | props_t& edge_props_ =
|
---|
| 411 | subgraph_depth == 0 ?
|
---|
| 412 | default_edge_props :
|
---|
| 413 | subgraph_edge_props[subgraph.name()];
|
---|
| 414 |
|
---|
| 415 | // add this to the list of default edge properties.
|
---|
| 416 | edge_props_[key] = value;
|
---|
| 417 | // for each edge, set its property to be empty string
|
---|
| 418 | // set the dynamic property map value
|
---|
| 419 | for(edges_t::iterator i = edges_.begin(); i != edges_.end(); ++i)
|
---|
| 420 | if(edge_map[*i].find(key) == edge_map[*i].end())
|
---|
| 421 | set_edge_property(*i,key,id_t());
|
---|
| 422 | }
|
---|
| 423 |
|
---|
| 424 | // helper function
|
---|
| 425 | void insert_node(nodes_t& nodes, id_t const& name) {
|
---|
| 426 | nodes.insert(name);
|
---|
| 427 | }
|
---|
| 428 |
|
---|
| 429 | void call_prop_actor(std::string const& lhs, std::string const& rhs) {
|
---|
| 430 | actor_t& actor = attr_list.prop_actor();
|
---|
| 431 | // If first and last characters of the rhs are double-quotes,
|
---|
| 432 | // remove them.
|
---|
| 433 | if (!rhs.empty() && rhs[0] == '"' && rhs[rhs.size() - 1] == '"')
|
---|
| 434 | actor(lhs, rhs.substr(1, rhs.size()-2));
|
---|
| 435 | else
|
---|
| 436 | actor(lhs,rhs);
|
---|
| 437 | }
|
---|
| 438 |
|
---|
| 439 | void set_node_property(node_t const& node, id_t const& key,
|
---|
| 440 | id_t const& value) {
|
---|
| 441 |
|
---|
| 442 | // Add the property key to the "set" table to avoid default overwrite
|
---|
| 443 | node_map[node].insert(key);
|
---|
| 444 | // Set the user's property map
|
---|
| 445 | self.graph_.set_node_property(key, node, value);
|
---|
| 446 | #ifdef BOOST_GRAPH_DEBUG
|
---|
| 447 | // Tell the world
|
---|
| 448 | std::cout << node << ": " << key << " = " << value << std::endl;
|
---|
| 449 | #endif // BOOST_GRAPH_DEBUG
|
---|
| 450 | }
|
---|
| 451 |
|
---|
| 452 | void set_edge_property(edge_t const& edge, id_t const& key,
|
---|
| 453 | id_t const& value) {
|
---|
| 454 |
|
---|
| 455 | // Add the property key to the "set" table to avoid default overwrite
|
---|
| 456 | edge_map[edge].insert(key);
|
---|
| 457 | // Set the user's property map
|
---|
| 458 | self.graph_.set_edge_property(key, edge, value);
|
---|
| 459 | #ifdef BOOST_GRAPH_DEBUG
|
---|
| 460 | // Tell the world
|
---|
| 461 | std::cout << "(" << edge.first << "," << edge.second << "): "
|
---|
| 462 | << key << " = " << value << std::endl;
|
---|
| 463 | #endif // BOOST_GRAPH_DEBUG
|
---|
| 464 | }
|
---|
| 465 |
|
---|
| 466 | // Variables explicitly initialized
|
---|
| 467 | dot_grammar const& self;
|
---|
| 468 | // if subgraph_depth > 0, then we're processing a subgraph.
|
---|
| 469 | int subgraph_depth;
|
---|
| 470 |
|
---|
| 471 | // Keywords;
|
---|
| 472 | const distinct_parser<> keyword_p;
|
---|
| 473 | //
|
---|
| 474 | // rules that make up the grammar
|
---|
| 475 | //
|
---|
| 476 | rule<ScannerT,id_closure::context_t> ID;
|
---|
| 477 | rule<ScannerT,property_closure::context_t> a_list;
|
---|
| 478 | rule<ScannerT,attr_list_closure::context_t> attr_list;
|
---|
| 479 | rule_t port_location;
|
---|
| 480 | rule_t port_angle;
|
---|
| 481 | rule_t port;
|
---|
| 482 | rule<ScannerT,node_id_closure::context_t> node_id;
|
---|
| 483 | rule_t attr_stmt;
|
---|
| 484 | rule<ScannerT,data_stmt_closure::context_t> data_stmt;
|
---|
| 485 | rule<ScannerT,subgraph_closure::context_t> subgraph;
|
---|
| 486 | rule_t edgeop;
|
---|
| 487 | rule_t edgeRHS;
|
---|
| 488 | rule_t stmt;
|
---|
| 489 | rule_t stmt_list;
|
---|
| 490 | rule_t the_grammar;
|
---|
| 491 |
|
---|
| 492 |
|
---|
| 493 | // The grammar uses edge_head to dynamically set the syntax for edges
|
---|
| 494 | // directed graphs: edge_head = '>', and so edgeop = "->"
|
---|
| 495 | // undirected graphs: edge_head = '-', and so edgeop = "--"
|
---|
| 496 | char edge_head;
|
---|
| 497 |
|
---|
| 498 |
|
---|
| 499 | //
|
---|
| 500 | // Support data structures
|
---|
| 501 | //
|
---|
| 502 |
|
---|
| 503 | nodes_t nodes; // list of node names seen
|
---|
| 504 | edges_t edges; // list of edges seen
|
---|
| 505 | node_map_t node_map; // remember the properties set for each node
|
---|
| 506 | edge_map_t edge_map; // remember the properties set for each edge
|
---|
| 507 |
|
---|
| 508 | subgraph_nodes_t subgraph_nodes; // per-subgraph lists of nodes
|
---|
| 509 | subgraph_edges_t subgraph_edges; // per-subgraph lists of edges
|
---|
| 510 |
|
---|
| 511 | props_t default_node_props; // global default node properties
|
---|
| 512 | props_t default_edge_props; // global default edge properties
|
---|
| 513 | subgraph_props_t subgraph_node_props; // per-subgraph default node properties
|
---|
| 514 | subgraph_props_t subgraph_edge_props; // per-subgraph default edge properties
|
---|
| 515 | }; // struct definition
|
---|
| 516 | }; // struct dot_grammar
|
---|
| 517 |
|
---|
| 518 |
|
---|
| 519 |
|
---|
| 520 | //
|
---|
| 521 | // dot_skipper - GraphViz whitespace and comment skipper
|
---|
| 522 | //
|
---|
| 523 | struct dot_skipper : public grammar<dot_skipper>
|
---|
| 524 | {
|
---|
| 525 | dot_skipper() {}
|
---|
| 526 |
|
---|
| 527 | template <typename ScannerT>
|
---|
| 528 | struct definition
|
---|
| 529 | {
|
---|
| 530 | definition(dot_skipper const& /*self*/) {
|
---|
| 531 | // comment forms
|
---|
| 532 | skip = space_p
|
---|
| 533 | | comment_p("//")
|
---|
| 534 | | comment_p("#")
|
---|
| 535 | #if BOOST_WORKAROUND(BOOST_MSVC, <= 1400)
|
---|
| 536 | | confix_p(str_p("/*") ,*anychar_p, str_p("*/"))
|
---|
| 537 | #else
|
---|
| 538 | | confix_p("/*" ,*anychar_p, "*/")
|
---|
| 539 | #endif
|
---|
| 540 | ;
|
---|
| 541 |
|
---|
| 542 | #ifdef BOOST_SPIRIT_DEBUG
|
---|
| 543 | BOOST_SPIRIT_DEBUG_RULE(skip);
|
---|
| 544 | #endif
|
---|
| 545 | }
|
---|
| 546 |
|
---|
| 547 | rule<ScannerT> skip;
|
---|
| 548 | rule<ScannerT> const&
|
---|
| 549 | start() const { return skip; }
|
---|
| 550 | }; // definition
|
---|
| 551 | }; // dot_skipper
|
---|
| 552 |
|
---|
| 553 | } // namespace graph
|
---|
| 554 | } // namespace detail
|
---|
| 555 |
|
---|
| 556 | template <typename MultiPassIterator, typename MutableGraph>
|
---|
| 557 | bool read_graphviz(MultiPassIterator begin, MultiPassIterator end,
|
---|
| 558 | MutableGraph& graph, dynamic_properties& dp,
|
---|
| 559 | std::string const& node_id = "node_id") {
|
---|
| 560 | using namespace boost;
|
---|
| 561 | using namespace boost::spirit;
|
---|
| 562 |
|
---|
| 563 | typedef MultiPassIterator iterator_t;
|
---|
| 564 | typedef skip_parser_iteration_policy< boost::detail::graph::dot_skipper>
|
---|
| 565 | iter_policy_t;
|
---|
| 566 | typedef scanner_policies<iter_policy_t> scanner_policies_t;
|
---|
| 567 | typedef scanner<iterator_t, scanner_policies_t> scanner_t;
|
---|
| 568 |
|
---|
| 569 | detail::graph::mutate_graph_impl<MutableGraph> m_graph(graph, dp, node_id);
|
---|
| 570 |
|
---|
| 571 | boost::detail::graph::dot_grammar p(m_graph);
|
---|
| 572 | boost::detail::graph::dot_skipper skip_p;
|
---|
| 573 |
|
---|
| 574 | iter_policy_t iter_policy(skip_p);
|
---|
| 575 | scanner_policies_t policies(iter_policy);
|
---|
| 576 |
|
---|
| 577 | scanner_t scan(begin, end, policies);
|
---|
| 578 |
|
---|
| 579 | return p.parse(scan);
|
---|
| 580 | }
|
---|
| 581 |
|
---|
| 582 | } // namespace boost
|
---|
| 583 |
|
---|
| 584 | #endif // BOOST_READ_GRAPHVIZ_SPIRIT_HPP
|
---|