Generated on Wed Apr 29 2015 11:51:40 for GGL-4.1.2 by doxygen 1.8.3.1
Rule_GML_grammar.hh
Go to the documentation of this file.
1 #ifndef GGL_RULE_GML_GRAMMAR_HH_
2 #define GGL_RULE_GML_GRAMMAR_HH_
3 
4 #include <utility>
5 #include <vector>
6 
7 #include "sgm/HashMap.hh"
8 #if HAVE_UNORDERED_MAP > 0
9  #include <unordered_map>
10 #elif HAVE_TR1_UNORDERED_MAP > 0
11  #include <tr1/unordered_map>
12 #elif HAVE_GNU_HASH_MAP > 0
13  #include <ext/hash_map>
14 #else
15  #include <map>
16 #endif
17 
18  // set spirit closure limit if neccessary
19 #if !defined(BOOST_SPIRIT_CLOSURE_LIMIT)
20 #define BOOST_SPIRIT_CLOSURE_LIMIT 5
21 #elif BOOST_SPIRIT_CLOSURE_LIMIT < 5
22 #error "GGL_RULE_GML_GRAMMAR : BOOST_SPIRIT_CLOSURE_LIMIT too low, has to be at least 5"
23 #endif
24 
25  // set phoenix limit if neccessary
26 #if !defined(PHOENIX_LIMIT)
27 #define PHOENIX_LIMIT 5
28 #elif PHOENIX_LIMIT < 5
29 #error "GGL_RULE_GML_GRAMMAR : PHOENIX_LIMIT too low, has to be at least 5"
30 #endif
31 
32 #include <boost/version.hpp>
33 #if BOOST_VERSION >= 103800
34 #include <boost/spirit/include/classic.hpp>
35 #include <boost/spirit/include/phoenix1.hpp>
36 #define NS_BOOSTSPIRIT boost::spirit::classic
37 #else
38 #include <boost/spirit.hpp>
39 #include <boost/spirit/phoenix.hpp>
40 #define NS_BOOSTSPIRIT boost::spirit
41 #endif
42 
43 #include "sgm/MC_Node.hh"
44 #include "sgm/MC_Edge.hh"
45 #include "ggl/Rule.hh"
46 #include "ggl/Rule_GML_error.hh"
47 
48 namespace ggl {
49 
50 
51 
52  /*! @brief Graph grammar rule parser
53  *
54  * Parses a GML string representation of a ggl::Rule object.
55  *
56  * Example :
57  *
58  * \verbatim
59  ====== RULE TO ENCODE =======================
60 
61  3(D) -1- 1(B) 3(E) -1- 1(B)
62  | / | |
63  2 3 ==> 4 3
64  | / | |
65  2(C) -0- 0(A) 2(C) 4(D)
66 
67  ======= RULE IN GML =========================
68 
69  rule [
70  ruleID "Example rule"
71  context [
72  node [ id 1 label "B" ]
73  node [ id 2 label "C" ]
74  edge [ source 1 target 3 label "-1-" ]
75  ]
76  left [
77  node [ id 0 label "A" ]
78  node [ id 3 label "D" ]
79  edge [ source 0 target 2 label "-0-" ]
80  edge [ source 1 target 2 label "-3-" ]
81  edge [ source 2 target 3 label "-2-" ]
82  ]
83  right [
84  node [ id 3 label "E" ]
85  node [ id 4 label "D" ]
86  edge [ source 2 target 3 label "-4-" ]
87  edge [ source 1 target 4 label "-3-" ]
88  ]
89  ]
90 
91  =============================================
92  * \endverbatim
93  *
94  * BNF grammar of GML (http://www.infosun.fim.uni-passau.de/Graphlet/GML/)
95  *
96  \verbatim
97  gml ::= keyvalues
98  keyvalues ::= keyvalue (keyvalue)
99  keyvalue ::= key value
100  key ::= ['a'-'z''A'-'Z']['a'-'z''A'-'Z''0'-'9']
101  value ::= real | integer | string | operator | list
102  real ::= sign? digit '.' digit+ mantissa
103  integer ::= sign? digit+
104  string ::= '"' instring '"'
105  operator ::= '>' | '<' | '=' | '!'
106  list ::= '[' keyvalues ']'
107  sign ::= '+' | '-'
108  digit ::= ['0'-'9']
109  mantissa ::= ('E' | 'e') sign? digit+
110  instring ::= ASCII-{'&', '"'} | '&' ['a'-'z''A'-'Z'] ';'
111  * \endverbatim
112  *
113  * @author Christoph Flamm (c) 2008 http://www.tbi.univie.ac.at/~xtof/
114  * @author Martin Mann (c) 2008 http://www.bioinf.uni-freiburg.de/~mmann/
115  *
116  */
117  class Rule_GML_grammar
118  : public NS_BOOSTSPIRIT::grammar< Rule_GML_grammar >
119  {
120  protected:
121 
122  //! enummeration of value types in gml key-value pairs
123  enum kv_values {
124  Y_CONTXT = -3, /* works as outer key context */
125  N_CONTXT = -2, /* ignore as outer context key */
126  UNKNOWN = -1, /* unknown value type */
127  INT_VAL = 0, /* integer value type */
128  STR_VAL = 1, /* string value type */
129  DBL_VAL = 2, /* double value type */
130  LST_VAL = 3, /* list value type */
131  STRLST_VAL = 4 /* string list value type */
132  };
133 
134  // typedefs
135  typedef enum kv_values kv_values_t;
136  typedef boost::tuple<int,int,std::string,std::string> edge_t;
137  typedef boost::tuple<int,std::string,std::string> node_t;
138 #if HAVE_UNORDERED_MAP > 0
139  typedef std::unordered_map<std::string, kv_values_t> keys_map_t;
140 #elif HAVE_TR1_UNORDERED_MAP > 0
141  typedef std::tr1::unordered_map<std::string, kv_values_t> keys_map_t;
142 #elif HAVE_GNU_HASH_MAP > 0
143  typedef __gnu_cxx::hash_map<std::string, kv_values_t, sgm::hash_string> keys_map_t;
144 #else
145  typedef std::map<std::string, kv_values_t> keys_map_t;
146 #endif
147 
148  struct lt_edge : public std::binary_function<edge_t, edge_t, bool> {
149  bool operator()(edge_t a, edge_t b) {
150  if (a.get<0>() != b.get<0>()) return ( a.get<0>() < b.get<0>() );
151  if (a.get<1>() != b.get<1>()) return ( a.get<1>() < b.get<1>() );
152  if (a.get<2>() != b.get<2>()) return ( a.get<2>() < b.get<2>() );
153  if (a.get<3>() != b.get<3>()) return ( a.get<3>() < b.get<3>() );
154 
155  return (false);
156  }
157  };
158 
159  struct lt_node : public std::binary_function<node_t, node_t, bool> {
160  bool operator()(node_t a, node_t b) {
161  if (a.get<0>() != b.get<0>()) return ( a.get<0>() < b.get<0>() );
162  if (a.get<1>() != b.get<1>()) return ( a.get<1>() < b.get<1>() );
163  if (a.get<2>() != b.get<2>()) return ( a.get<2>() < b.get<2>() );
164 
165  return (false);
166  }
167  };
168 
169  struct keyvalue_closure : NS_BOOSTSPIRIT::closure<keyvalue_closure,
170  std::string, std::string, int, double>
171  {
172  typedef NS_BOOSTSPIRIT::closure< keyvalue_closure
173  , std::string
174  , std::string
175  , int
176  , double > SuperClass;
177 
178  SuperClass::member1 key;
179  SuperClass::member2 strval;
180  SuperClass::member3 numval;
181  SuperClass::member4 dblval;
182  };
183 
184  class keys_map {
185  public:
186 
187  keys_map() { inizialize(); }
188 
189  void inizialize(void) {
190  _keys["label"] = STR_VAL;
191  _keys["ruleID"] = STR_VAL;
192  _keys["wildcard"] = STR_VAL;
193  _keys["id"] = INT_VAL;
194  _keys["source"] = INT_VAL;
195  _keys["target"] = INT_VAL;
196  _keys["graph"] = LST_VAL;
197  _keys["rule"] = LST_VAL;
198  _keys["context"] = LST_VAL;
199  _keys["left"] = LST_VAL;
200  _keys["right"] = LST_VAL;
201  _keys["node"] = LST_VAL;
202  _keys["edge"] = LST_VAL;
203  _keys["_node"] = UNKNOWN;
204  _keys["_edge"] = UNKNOWN;
205  _keys["constrainAdj"] = LST_VAL;
206  _keys["constrainNode"] = LST_VAL;
207  _keys["constrainNoEdge"] = LST_VAL;
208  _keys["constrainEdge"] = LST_VAL;
209  _keys["count"] = INT_VAL;
210  _keys["op"] = STR_VAL;
211  _keys["nodeLabels"] = LST_VAL;
212  _keys["edgeLabels"] = LST_VAL;
213  _keys["copyAndPaste"] = LST_VAL;
214  }
215 
216  kv_values_t lookup( const std::string & k) {
217  keys_map_t::iterator pos = _keys.find(k);
218 
219  if (pos != _keys.end()) return (pos->second);
220  else return (UNKNOWN);
221  }
222 
223  kv_values_t context( const std::string & k) {
224  keys_map_t::iterator pos = _keys.find("_"+k);
225 
226  if (pos != _keys.end()) return (N_CONTXT);
227  else return (Y_CONTXT);
228  }
229 
230  private:
231  keys_map_t _keys;
232  };
233 
234 
235  protected:
236 
237  //! The boost core graph object that is filled to represent the next
238  //! parsed Rule.
239  Rule::CoreGraph& g2fill;
240 
241  //! The rule id that is filled.
242  std::string& ruleID;
243 
244  //! The additional constraints to be fulfilled by the rule to be filled
245  std::vector< sgm::Pattern_Interface::Match_Constraint* > & ruleConstraints;
246 
247  //! The copy-and-Paste operation container to be filled
248  Rule::CopyAndPasteOperations & copyAndPaste;
249 
250  //! The wildcard label that is filled if present.
251  std::string& wildcard;
252 
253  //! Access to the node label property_map of g2fill to set node labels
254  mutable
255  boost::property_map<Rule::CoreGraph
256  , Rule::NodeLabelProperty>::type
257  nodeLabel;
258 
259  //! Access to the right node label property_map of g2fill to set
260  //! changing node labels
261  mutable
262  boost::property_map<Rule::CoreGraph
263  , Rule::NodeRightLabelProperty>::type
264  nodeLabelRight;
265 
266  //! Access to the node Rule context property_map of g2fill
267  mutable
268  boost::property_map<Rule::CoreGraph
269  , Rule::NodeContextProperty>::type
270  nodeContext;
271 
272  //! Access to the edge label property_map of g2fill to set edge labels
273  mutable
274  boost::property_map<Rule::CoreGraph
275  , Rule::EdgeLabelProperty>::type
276  edgeLabel;
277 
278  //! Access to the edge Rule context property_map of g2fill
279  mutable
280  boost::property_map<Rule::CoreGraph
281  , Rule::EdgeContextProperty>::type
282  edgeContext;
283 
284 
285  public:
286 
287  //! Constructs the definitions of a GML graph grammar to parse
288  //! a GML graph string representation and to fill the encoded graph
289  //! into a given boost graph object.
290  //! @param toFill the Rule core graph object to add nodes and edges to
291  //! @param ruleID the Rule ID to set
292  //! @param ruleConstraints the additional constraints that
293  //! have to be met by the rule
294  //! @param copyAndPaste the copy-and-Paste operation container to fill
295  //! @param wildcard the wildcard string to be filled. NOTE: if no
296  //! wildcard was parsed this string is not changed, so check
297  //! for a change to know if a wildcard was parsed or not!
298  explicit Rule_GML_grammar( Rule::CoreGraph& toFill
299  , std::string& ruleID
300  , std::vector< sgm::Pattern_Interface::Match_Constraint* > & ruleConstraints
301  , Rule::CopyAndPasteOperations & copyAndPaste
302  , std::string& wildcard );
303 
304  //! Parses a GML string and generates a Rule object
305  //! @param GML_string the string to parse
306  //! @return pair.first = the graph encoding of the molecule
307  //! pair.second = -1 if parsing was successfull,
308  //! in error case it returns the string position that caused
309  //! the parsing error
310  //! @throw ggl::Rule_GML_error if parsing errors occur
311  static
312  std::pair< Rule, int >
313  parseRule( const std::string & GML_string ) throw (Rule_GML_error);
314 
315 
316  //! The definition of the GML grammar.
317  template <typename ScannerT>
318  struct definition
319  {
320  public:
321 
322  //! Construction of the GML BNF grammar rules
323  definition( Rule_GML_grammar const& self);
324 
325  //! start parsing
326  NS_BOOSTSPIRIT::rule<ScannerT> const&
327  start() const;
328 
329  protected:
330 
331  // Variables explicitly initialized
332  //! back reference to enclosing object for molecule creation
333  Rule_GML_grammar const& self;
334  typedef NS_BOOSTSPIRIT::rule<ScannerT
335  , keyvalue_closure::context_t> keyvalue_t;
336 
337  NS_BOOSTSPIRIT::rule<ScannerT> gml, keyvalues, value;
338 
339  keyvalue_t keyvalue, key, string, integer, real, relop, strlist, list;
340 
341  // typedefs for local data structures
342 
343  typedef std::vector<bool> boolstack_t;
344  typedef std::vector<std::string> keystack_t;
345  typedef std::multiset<edge_t,lt_edge> edges_t;
346  typedef std::set<node_t,lt_node> nodes_t;
347 
348  // helper functions
349 
350  /***************************/
351  bool is_valid_node(const node_t& a);
352 
353  /***************************/
354  bool is_valid_edge(const edge_t& e);
355 
356  /***************************/
357  bool is_valid_MC_NodeAdjacency(const sgm::MC_NodeAdjacency& c);
358 
359  /***************************/
360  bool is_valid_MC_NodeLabel(const sgm::MC_NodeLabel& c);
361 
362  /***************************/
363  bool is_valid_MC_NoEdge(const sgm::MC_NoEdge& c);
364 
365  /***************************/
366  bool is_valid_MC_EdgeLabel(const sgm::MC_EdgeLabel& c);
367 
368  /***************************/
369  bool is_valid_copyAndPaste(const Rule::RuleCnP& cnp);
370 
371  /***************************/
372  std::string spacer(int level);
373 
374  /******************************/
375  void reset_data_structures(void);
376 
377  /****************************/
378  void clear_tmp_node_data(void);
379 
380  /****************************/
381  void clear_tmp_edge_data(void);
382 
383  /****************************/
384  void clear_tmp_MC_NodeAdjacency(void);
385 
386  /****************************/
387  void clear_tmp_MC_NodeLabel(void);
388 
389  /****************************/
390  void clear_tmp_MC_NoEdge(void);
391 
392  /****************************/
393  void clear_tmp_MC_EdgeLabel(void);
394 
395  /****************************/
396  void clear_tmp_copyAndPaste(void);
397 
398  /****************/
399  void dumpvec(void);
400 
401  // semantic actions
402 
403  /**************************/
404  void openList(std::string s);
405 
406  /******************/
407  void closeList(void);
408 
409  /*************/
410  void create_Rule(void);
411 
412  /*************/
413  void Dump(void);
414 
415  /***************************************************************/
416  void dumpKeyValues(std::string k, std::string s, int i, double d);
417 
418  /***************************************************************/
419  void set_node_data(std::string k, std::string s, int i, double d);
420 
421  /***************************************************************/
422  void set_edge_data(std::string k, std::string s, int i, double d);
423 
424  /***************************************************************/
425  void set_MC_NodeAdjacency_data(std::string k, std::string s, int i, double d);
426 
427  /***************************************************************/
428  void set_MC_NodeAdjacencyNL_data(std::string k, std::string s, int i, double d);
429 
430  /***************************************************************/
431  void set_MC_NodeAdjacencyEL_data(std::string k, std::string s, int i, double d);
432 
433  /***************************************************************/
434  void set_MC_NodeLabel_data(std::string k, std::string s, int i, double d);
435 
436  /***************************************************************/
437  void set_MC_NodeLabelNL_data(std::string k, std::string s, int i, double d);
438 
439  /***************************************************************/
440  void set_MC_NoEdge_data(std::string k, std::string s, int i, double d);
441 
442  /***************************************************************/
443  void set_MC_EdgeLabel_data(std::string k, std::string s, int i, double d);
444 
445  /***************************************************************/
446  void set_MC_EdgeLabelEL_data(std::string k, std::string s, int i, double d);
447 
448  /***************************************************************/
449  void set_copyAndPaste_data(std::string k, std::string s, int i, double d);
450 
451  /***************************************************************/
452  void set_copyAndPaste_EL_data(std::string k, std::string s, int i, double d);
453 
454  /****************************************************************/
455  void keyValueAction(std::string k, std::string s, int i, double d);
456 
457  // local data structures
458 
459  int level;
460  boolstack_t boolstack;
461  keystack_t keystack;
462  node_t tmp_node;
463  edge_t tmp_edge;
464  std::string tmp_ruleID;
465  std::string tmp_wildcard;
466  edges_t edges;
467  nodes_t nodes;
468  keys_map keys;
469 
470  //! The current sgm::MC_NodeAdjacency rule constraint to be filled
471  sgm::MC_NodeAdjacency tmp_MC_NodeAdjacency;
472 
473  //! The current sgm::MC_NodeLabel rule constraint to be filled
474  sgm::MC_NodeLabel tmp_MC_NodeLabel;
475 
476  //! The current sgm::MC_NoEdge rule constraint to be filled
477  sgm::MC_NoEdge tmp_MC_NoEdge;
478 
479  //! The current sgm::MC_EdgeLabel rule constraint to be filled
480  sgm::MC_EdgeLabel tmp_MC_EdgeLabel;
481 
482  //! The current copy-and-paste operation to be filled
483  Rule::RuleCnP tmp_copyAndPaste;
484 
485 
486  };
487 
488  protected:
489 
490 
491 
492  //! Trims leading and tailing quotes from a string
493  //! @param s the string to trim
494  //! @return the trimmed string
495  static
496  std::string
497  trimQuotes( const std::string& s );
498 
499 
500  };
501 
502 
503 } // namespace ggl
504 
505 // include implementation
506 #include "ggl/Rule_GML_grammar.icc"
507 
508 #endif /*RULE_GML_GRAMMAR_HH_*/