← Back to branch summary

~ubuntu-branches/ubuntu/saucy/deal.ii/saucy

« back to all changes in this revision

Viewing changes to contrib/boost/include/boost/graph/detail/read_graphviz_spirit.hpp

  • Committer: Bazaar Package Importer
  • Author(s): Adam C. Powell, IV
  • Date: 2009-05-08 23:13:50 UTC
  • Revision ID: james.westby@ubuntu.com-20090508231350-rrh1ltgi0tifabwc
Tags: upstream-6.2.0
Import upstream version 6.2.0

Show diffs side-by-side

added added

removed removed

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