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;
evalphoenix::binary_operator64 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_;
dot_grammarboost::detail::graph::dot_grammar140 explicit dot_grammar(mutate_graph& graph) : graph_(graph) { }
141
142 template <class ScannerT>
143 struct definition {
144
definitionboost::detail::graph::dot_grammar::definition145 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
startboost::detail::graph::dot_grammar::definition282 rule_t const& start() const { return the_grammar; }
283
284
285 //
286 // Semantic actions
287 //
288
check_undirectedboost::detail::graph::dot_grammar::definition289 void check_undirected() {
290 if(self.graph_.is_directed())
291 throw boost::undirected_graph_error();
292 }
293
check_directedboost::detail::graph::dot_grammar::definition294 void check_directed() {
295 if(!self.graph_.is_directed())
296 throw boost::directed_graph_error();
297 }
298
memoize_nodeboost::detail::graph::dot_grammar::definition299 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
activate_edgeboost::detail::graph::dot_grammar::definition333 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.
node_propboost::detail::graph::dot_grammar::definition369 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.
edge_propboost::detail::graph::dot_grammar::definition375 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.
default_graph_propboost::detail::graph::dot_grammar::definition384 void default_graph_prop(id_t const&, id_t const&) { }
385
386 // default_node_prop - declare default properties for any future new nodes
default_node_propboost::detail::graph::dot_grammar::definition387 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
default_edge_propboost::detail::graph::dot_grammar::definition407 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
insert_nodeboost::detail::graph::dot_grammar::definition425 void insert_node(nodes_t& nodes, id_t const& name) {
426 nodes.insert(name);
427 }
428
call_prop_actorboost::detail::graph::dot_grammar::definition429 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
set_node_propertyboost::detail::graph::dot_grammar::definition439 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
set_edge_propertyboost::detail::graph::dot_grammar::definition452 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 {
dot_skipperboost::detail::graph::dot_skipper525 dot_skipper() {}
526
527 template <typename ScannerT>
528 struct definition
529 {
definitionboost::detail::graph::dot_skipper::definition530 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&
startboost::detail::graph::dot_skipper::definition549 start() const { return skip; }
550 }; // definition
551 }; // dot_skipper
552
553 } // namespace graph
554 } // namespace detail
555
556 template <typename MultiPassIterator, typename MutableGraph>
read_graphviz(MultiPassIterator begin,MultiPassIterator end,MutableGraph & graph,dynamic_properties & dp,std::string const & node_id="node_id")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
585