Generated on Wed Apr 29 2015 11:51:40 for GGL-4.1.2 by doxygen 1.8.3.1
Graph_GML_grammar.hh
Go to the documentation of this file.
1 #ifndef GGL_GRAPH_GML_GRAMMAR_HH_
2 #define GGL_GRAPH_GML_GRAMMAR_HH_
3 
4 #include <utility>
5 #include <vector>
6 
7 #include "sgm/HashMap.hh"
8 
9 #if HAVE_UNORDERED_MAP > 0
10  #include <unordered_map>
11 #elif HAVE_TR1_UNORDERED_MAP > 0
12  #include <tr1/unordered_map>
13 #elif HAVE_GNU_HASH_MAP > 0
14  #include <ext/hash_map>
15 #else
16  #include <map>
17 #endif
18 
19  // set spirit closure limit if neccessary
20 #if !defined(BOOST_SPIRIT_CLOSURE_LIMIT)
21 #define BOOST_SPIRIT_CLOSURE_LIMIT 5
22 #elif BOOST_SPIRIT_CLOSURE_LIMIT < 5
23 #error "GGL_GRAPH_GML_GRAMMAR : BOOST_SPIRIT_CLOSURE_LIMIT too low, has to be at least 5"
24 #endif
25 
26  // set phoenix limit if neccessary
27 #if !defined(PHOENIX_LIMIT)
28 #define PHOENIX_LIMIT 5
29 #elif PHOENIX_LIMIT < 5
30 #error "GGL_GRAPH_GML_GRAMMAR : PHOENIX_LIMIT too low, has to be at least 5"
31 #endif
32 
33 #include <boost/version.hpp>
34 #if BOOST_VERSION >= 103800
35 #include <boost/spirit/include/classic.hpp>
36 #include <boost/spirit/include/phoenix1.hpp>
37 #define NS_BOOSTSPIRIT boost::spirit::classic
38 #else
39 #include <boost/spirit.hpp>
40 #include <boost/spirit/phoenix.hpp>
41 #define NS_BOOSTSPIRIT boost::spirit
42 #endif
43 
44 #include "ggl/Graph.hh"
45 
46 namespace ggl {
47 
48 
49  /*! @brief Graph GML parser
50  *
51  * Parses a GML string representation of a ggl::Graph object.
52  *
53  * Example :
54  *
55  * \verbatim
56  ====== GRAPH TO ENCODE =======================
57 
58  3(D) -1- 1(B)
59  | /
60  2 3
61  | /
62  2(C) -0- 0(A)
63 
64  ======= GRAPH IN GML =========================
65 
66  graph [
67  node [ id 0 label "A" ]
68  node [ id 1 label "B" ]
69  node [ id 2 label "C" ]
70  node [ id 3 label "D" ]
71  edge [ source 0 target 2 label "-0-" ]
72  edge [ source 1 target 3 label "-1-" ]
73  edge [ source 1 target 2 label "-3-" ]
74  edge [ source 2 target 3 label "-2-" ]
75  ]
76 
77  ==============================================
78  \endverbatim
79  *
80  * BNF grammar of GML (http://www.infosun.fim.uni-passau.de/Graphlet/GML/)
81  *
82  * \verbatim
83  gml ::= keyvalues
84  keyvalues ::= keyvalue (keyvalue)
85  keyvalue ::= key value
86  key ::= ['a'-'z''A'-'Z']['a'-'z''A'-'Z''0'-'9']
87  value ::= real | integer | string | list
88  real ::= sign? digit '.' digit+ mantissa
89  integer ::= sign? digit+
90  string ::= '"' instring '"'
91  list ::= '[' keyvalues ']'
92  sign ::= '+' | '-'
93  digit ::= ['0'-'9']
94  mantissa ::= ('E' | 'e') sign? digit+
95  instring ::= ASCII-{'&', '"'} | '&' ['a'-'z''A'-'Z'] ';'
96  \endverbatim
97  *
98  * @author Christoph Flamm (c) 2008 http://www.tbi.univie.ac.at/~xtof/
99  * @author Martin Mann (c) 2008 http://www.bioinf.uni-freiburg.de/~mmann/
100  *
101  */
102  class Graph_GML_grammar
103  : public NS_BOOSTSPIRIT::grammar< Graph_GML_grammar >
104  {
105  protected:
106 
107  //! enummeration of value types in gml key-value pairs
108  enum kv_values {
109  Y_CONTXT = -3, /* works as outer key context */
110  N_CONTXT = -2, /* ignore as outer context key */
111  UNKNOWN = -1, /* unknown value type */
112  INT_VAL = 0, /* integer value type */
113  STR_VAL = 1, /* string value type */
114  DBL_VAL = 2, /* double value type */
115  LST_VAL = 3 /* list value type */
116  };
117 
118  // typedefs
119  typedef enum kv_values kv_values_t;
120 
121  typedef
122 #if HAVE_UNORDERED_MAP > 0
123  std::unordered_map<std::string, kv_values_t>
124 #elif HAVE_TR1_UNORDERED_MAP > 0
125  std::tr1::unordered_map<std::string, kv_values_t>
126 #elif HAVE_GNU_HASH_MAP > 0
127  __gnu_cxx::hash_map<std::string, kv_values_t, sgm::hash_string>
128 #else
129  std::map<std::string, kv_values_t>
130 #endif
131  keys_map_t;
132 
133  typedef boost::tuple<int,int,std::string,std::string> edge_t;
134  typedef boost::tuple<int,std::string,std::string> node_t;
135 
136  struct lt_edge : public std::binary_function<edge_t, edge_t, bool> {
137  bool operator()(edge_t a, edge_t b) {
138  if (a.get<0>() != b.get<0>()) return ( a.get<0>() < b.get<0>() );
139  if (a.get<1>() != b.get<1>()) return ( a.get<1>() < b.get<1>() );
140  if (a.get<2>() != b.get<2>()) return ( a.get<2>() < b.get<2>() );
141  if (a.get<3>() != b.get<3>()) return ( a.get<3>() < b.get<3>() );
142 
143  return (false);
144  }
145  };
146 
147  struct lt_node : public std::binary_function<node_t, node_t, bool> {
148  bool operator()(node_t a, node_t b) {
149  if (a.get<0>() != b.get<0>()) return ( a.get<0>() < b.get<0>() );
150  if (a.get<1>() != b.get<1>()) return ( a.get<1>() < b.get<1>() );
151  if (a.get<2>() != b.get<2>()) return ( a.get<2>() < b.get<2>() );
152 
153  return (false);
154  }
155  };
156 
157  struct keyvalue_closure : NS_BOOSTSPIRIT::closure<keyvalue_closure,
158  std::string, std::string, int, double>
159  {
160  typedef NS_BOOSTSPIRIT::closure< keyvalue_closure
161  , std::string
162  , std::string
163  , int
164  , double > SuperClass;
165 
166  SuperClass::member1 key;
167  SuperClass::member2 strval;
168  SuperClass::member3 numval;
169  SuperClass::member4 dblval;
170  };
171 
172  class keys_map {
173  public:
174 
175  keys_map() { inizialize(); }
176 
177  void inizialize(void) {
178  _keys["id"] = INT_VAL;
179  _keys["label"] = STR_VAL;
180  _keys["source"] = INT_VAL;
181  _keys["target"] = INT_VAL;
182  _keys["graph"] = LST_VAL;
183  _keys["node"] = LST_VAL;
184  _keys["edge"] = LST_VAL;
185  _keys["_node"] = UNKNOWN;
186  _keys["_edge"] = UNKNOWN;
187  }
188 
189  kv_values_t lookup(std::string k) {
190  keys_map_t::iterator pos = _keys.find(k);
191 
192  if (pos != _keys.end()) return (pos->second);
193  else return (UNKNOWN);
194  }
195 
196  kv_values_t context(std::string k) {
197  keys_map_t::iterator pos = _keys.find("_"+k);
198 
199  if (pos != _keys.end()) return (N_CONTXT);
200  else return (Y_CONTXT);
201  }
202 
203  private:
204  keys_map_t _keys;
205  };
206 
207 
208 
209  protected:
210 
211  //! The boost core graph object that is filled to represent the next
212  //! parsed Rule.
213  Graph& g2fill;
214 
215  //! Access to the node label property_map of g2fill to set node labels
216  mutable
217  boost::property_map< Graph, PropNodeLabel>::type
218  nodeLabel;
219 
220  //! Access to the edge label property_map of g2fill to set edge labels
221  mutable
222  boost::property_map< Graph, PropEdgeLabel>::type
223  edgeLabel;
224 
225 
226  public:
227 
228  //! Constructs the definitions of a GML graph grammar to parse
229  //! a GML graph string representation and to fill the encoded graph
230  //! into a given boost graph object.
231  //! @param toFill the graph object to add nodes and edges to
232  explicit Graph_GML_grammar( Graph & toFill );
233 
234  //! Parses a GML string and generates a Graph object
235  //! @param GML_string the string to parse
236  //! @return pair.first = the parsed graph object
237  //! pair.second = -1 if parsing was successful,
238  //! in error case it returns the string position that caused
239  //! the parsing error
240  static
241  std::pair< Graph, int >
242  parseGraph( const std::string & GML_string );
243 
244 
245  //! The definition of the GML grammar.
246  template <typename ScannerT>
247  struct definition
248  {
249  public:
250 
251  //! Construction of the GML BNF grammar rules
252  definition( Graph_GML_grammar const& self);
253 
254  //! start parsing
255  NS_BOOSTSPIRIT::rule<ScannerT> const&
256  start() const;
257 
258  protected:
259 
260  // Variables explicitly initialized
261  //! back reference to enclosing object for molecule creation
262  Graph_GML_grammar const& self;
263  typedef NS_BOOSTSPIRIT::rule<ScannerT
264  , keyvalue_closure::context_t> keyvalue_t;
265 
266  NS_BOOSTSPIRIT::rule<ScannerT> gml, keyvalues, value;
267 
268  keyvalue_t keyvalue, key, string, integer, real, list;
269 
270  // typedefs for local data structures
271 
272  typedef std::vector<bool> boolstack_t;
273  typedef std::vector<std::string> keystack_t;
274  typedef std::set<edge_t,lt_edge> edges_t;
275  typedef std::set<node_t,lt_node> nodes_t;
276 
277  // helper functions
278 
279  /***************************/
280  bool is_valid_node(node_t& a);
281 
282  /***************************/
283  bool is_valid_edge(edge_t& e);
284 
285  /***************************/
286  std::string spacer(int level);
287 
288  /******************************/
289  void reset_data_structures(void);
290 
291  /****************************/
292  void clear_tmp_node_data(void);
293 
294  /****************************/
295  void clear_tmp_edge_data(void);
296 
297  /****************/
298  void dumpvec(void);
299 
300  // semantic actions
301 
302  /**************************/
303  void openList(std::string s);
304 
305  /******************/
306  void closeList(void);
307 
308  /*************/
309  void create_Graph(void);
310 
311  /*************/
312  void Dump(void);
313 
314  /***************************************************************/
315  void dumpKeyValues(std::string k, std::string s, int i, double d);
316 
317  /**********************/
318  void memorize_node(void);
319 
320  /**********************/
321  void memorize_edge(void);
322 
323  /***************************************************************/
324  void set_node_data(std::string k, std::string s, int i, double d);
325 
326  /***************************************************************/
327  void set_edge_data(std::string k, std::string s, int i, double d);
328 
329  /****************************************************************/
330  void keyValueAction(std::string k, std::string s, int i, double d);
331 
332  // local data structures
333 
334  int level;
335  boolstack_t boolstack;
336  keystack_t keystack;
337  node_t tmp_node;
338  edge_t tmp_edge;
339  edges_t edges;
340  nodes_t nodes;
341  keys_map keys;
342 
343 
344  };
345 
346 
347 
348  };
349 
350 
351 } // namespace ggl
352 
353 // include implementation
354 #include "ggl/Graph_GML_grammar.icc"
355 
356 #endif /*GRAPH_GML_GRAMMAR_HH_*/