Vaucanson  1.4.1
bmig_graph_impl.hh
1 // bmig_graph_impl.hh: this file is part of the Vaucanson project.
2 //
3 // Vaucanson, a generic library for finite state machines.
4 //
5 // Copyright (C) 2007, 2008 The Vaucanson Group.
6 //
7 // This program is free software; you can redistribute it and/or
8 // modify it under the terms of the GNU General Public License
9 // as published by the Free Software Foundation; either version 2
10 // of the License, or (at your option) any later version.
11 //
12 // The complete GNU General Public Licence Notice can be found as the
13 // `COPYING' file in the root directory.
14 //
15 // The Vaucanson Group consists of people listed in the `AUTHORS' file.
16 //
17 
18 #ifndef VCSN_AUTOMATA_IMPLEMENTATION_BMIG_GRAPH_IMPL_HH_
19 # define VCSN_AUTOMATA_IMPLEMENTATION_BMIG_GRAPH_IMPL_HH_
20 # include <boost/dynamic_bitset.hpp>
21 # include <boost/shared_ptr.hpp>
22 
23 # include <vaucanson/algebra/implementation/series/rat/exp.hh>
24 # include <vaucanson/automata/implementation/bmig/vgraph_container.hh>
25 # include <vaucanson/automata/implementation/bmig/bmig_handlers.hh>
26 # include <vaucanson/automata/implementation/bmig/iterator.hh>
27 # include <vaucanson/automata/concept/automata_base.hh>
28 # include <vaucanson/automata/concept/automata.hh>
29 # include <vaucanson/automata/concept/automata_kind.hh>
30 # include <vaucanson/automata/implementation/bmig/bmig_support.hh>
31 # include <vaucanson/automata/concept/transducer_base.hh>
32 # include <vaucanson/automata/concept/smart_label.hh>
33 # include <vaucanson/automata/implementation/kind_adapter.hh>
34 # include <vaucanson/automata/implementation/geometry.hh>
35 # include <vaucanson/automata/concept/tags.hh>
36 # include <vaucanson/misc/hash.hh>
37 # include <vaucanson/automata/implementation/bmig/initial_value.hh>
38 # include <vaucanson/automata/implementation/bmig/graphcontainer.hh>
39 # include <vaucanson/automata/implementation/bmig/edge_value.hh>
40 # include <vaucanson/automata/implementation/bmig/bmig_functors.hh>
41 # include <vaucanson/automata/implementation/bmig/initial_container.hh>
42 
43 namespace vcsn
44 {
45  namespace bmig
46  {
47 
48  // class Graph.
49  template <typename Kind, typename WordValue, typename WeightValue,
50  typename SeriesValue, typename Letter, typename Tag, typename GeometryCoords>
51  class Graph
52  {
53  public:
54  /*
55  ** Type definitions
56  */
57 
58  // self definition.
59  typedef Graph<Kind, WordValue, WeightValue,
60  SeriesValue, Letter, Tag, GeometryCoords>
61  self_t;
62 
63  typedef WeightValue semiring_elt_value_t;
64  typedef WordValue monoid_elt_value_t;
65  typedef WordValue word_value_t;
66  typedef SeriesValue series_set_elt_value_t;
67  typedef Letter letter_t;
68  typedef Tag tag_t;
69 
70  typedef typename LabelOf<Kind, WordValue, WeightValue,
71  SeriesValue, Letter>::ret label_t;
72 
73  //typedef typename SmartLabelContainer<label_t>::hlabel_t
74  typedef label_t
75  hlabel_t;
76 
77  typedef boost::shared_ptr<std::size_t> state_t;
78  // State descriptor.
79  //
80  typedef handler<state_h, state_t> hstate_t;
81 
82  typedef EdgeValue<state_t, label_t> edge_data_t;
83  //typedef EdgeValue<state_t, hlabel_t> edge_data_t;
84 
85  typedef GraphContainer<state_t, label_t, edge_data_t> graph_data_t;
86  //typedef GraphContainer<state_t, hlabel_t, edge_data_t> graph_data_t;
87 
88  // Transition descriptor.
89  //
90  // We store a pointer to an EdgeValue to avoid a new index on transitions and
91  // get the data more quickly. Actually this is the adresse of an element
92  // inserted in the multi_index.
93  // We are allowed to do so since Boost::multi_index guaranties that the data
94  // inserted will not be reallocated.
95  //
96  // We may need to try storing an iterator instead of a pointer. We haven't tried yet
97  // since its size is higher than a simple pointer.
98  typedef typename graph_data_t::iterator
99  edges_iterator;
100  typedef handler<transition_h, edges_iterator> htransition_t;
101  typedef htransition_t hedge_t;
102 
103  //The graph stores edges only, thus we can define this type.
104  typedef VGraphContainer<edges_iterator, graph_data_t, htransition_t> edges_t;
105  typedef std::vector<state_t> states_data_t;
106  typedef misc::Support<states_data_t> states_t;
107 
108  //FIXME: find a better name than initial_container_t. The word initial
109  //is ambiguous since we use it also for final_t
110  typedef InitialValue<state_t, series_set_elt_value_t>
111  initial_value_t;
112  typedef initial_value_t final_value_t;
113  typedef InitialContainer<initial_value_t, state_t>
114  initial_container_t;
115 
116  typedef typename initial_container_t::Type initial_t;
117  typedef initial_t final_t;
118 
119  typedef misc::Support<initial_container_t> initial_support_t;
120  typedef misc::Support<initial_container_t> final_support_t;
121 
122  typedef GeometryCoords geometry_coords_t;
123 
124  typedef vcsn::geometry<hstate_t, htransition_t, GeometryCoords>
125  geometry_t;
126 
127  //Definition of various iterator types for the graph structure.
128  typedef typename graph_data_t::iterator iterator;
129  typedef typename graph_data_t::const_iterator const_iterator;
130  typedef iterator transition_iterator;
131 
132  typedef typename index_iterator<graph_data_t, src>::type
133  src_iterator;
134  typedef src_iterator src_const_iterator;
135  typedef typename index_iterator<graph_data_t, dst>::type
136  dst_iterator;
137  typedef dst_iterator dst_const_iterator;
138  typedef std::pair<src_iterator, src_iterator> src_range;
139  typedef std::pair<dst_iterator, dst_iterator> dst_range;
140 
141  typedef typename index_iterator<graph_data_t, succ>::type
142  succ_iterator;
143  typedef succ_iterator succ_const_iterator;
144  typedef std::pair<succ_iterator, succ_iterator> succ_range;
145 
146  typedef ::vcsn::bmig::DeltaConstIterator<self_t, src_iterator>
147  delta_iterator;
148  typedef ::vcsn::bmig::DeltaConstIterator<self_t, dst_iterator>
149  rdelta_iterator;
150 
151  Graph ();
152  Graph (unsigned int reserve_number_of_state,
153  unsigned int reserve_number_edge);
154  Graph (const self_t&);
155  ~Graph ();
156 
157  self_t& operator= (const self_t&);
158 
159  // FIXME: add const rettype& versions?
160 
161  states_t states () const;
162  edges_t edges () const;
163  initial_support_t initial () const;
164  final_support_t final () const;
165 
166  // state manipulations
167  bool has_state (const hstate_t& h) const;
168  hstate_t add_state ();
169  hstate_t get_state (unsigned h) const;
170  void del_state (const hstate_t& h);
171 
172  void set_initial(const hstate_t& s,
173  const series_set_elt_value_t& v,
174  const series_set_elt_value_t& z);
175  const series_set_elt_value_t&
176  get_initial(const hstate_t&,
177  const series_set_elt_value_t&) const;
178  bool is_initial(const hstate_t& s,
179  const series_set_elt_value_t&) const;
180  void clear_initial();
181 
182  void set_final(const hstate_t&,
183  const series_set_elt_value_t&,
184  const series_set_elt_value_t&);
185  const series_set_elt_value_t&
186  get_final(const hstate_t&,
187  const series_set_elt_value_t&) const;
188  bool is_final(const hstate_t& s,
189  const series_set_elt_value_t&) const;
190  void clear_final();
191 
192 
193  // edge manipulations
194  bool has_edge (const hedge_t& h) const;
195  hedge_t add_edge (const hstate_t& from,
196  const hstate_t& to,
197  const label_t& l);
198  void del_edge (const hedge_t& h);
199 
200  hstate_t src_of (const hedge_t& h) const;
201  hstate_t dst_of (const hedge_t& h) const;
202 
203  const label_t& label_of (const hedge_t& h) const;
204  void update(const hedge_t& h, const label_t& l);
205 
206  // check the consistency of an automata
207  template <class S>
208  bool exists (const AutomataBase<S>& s) const;
209 
210  self_t& clone () const; // TODO
211 
212  tag_t& tag ();
213  const tag_t& tag () const;
214  geometry_t& geometry ();
215  const geometry_t& geometry () const;
216 
217  // Helper used in deltai.
218  // Gives the htransition held by a boost iterator.
219  // Avoid the burden of carrying a reference to the main hash table
220  // when we are working on a sub-hash. (this is related to the projection).
221  template <typename I>
222  htransition_t get_htransition(const I& i) const;
223 
224  // Retrieve the (src|dst)_range from a given state
225  // Used by the delta iterators
226 # define DECLARE_DELTAI_FUNCTION(DeltaKind) \
227  std::pair<DeltaKind##_iterator, DeltaKind##_iterator> \
228  deltai(const hstate_t& s, DeltaKind##_iterator) const
229  DECLARE_DELTAI_FUNCTION(src);
230  DECLARE_DELTAI_FUNCTION(dst);
231 # undef DECLARE_DELTAI_FUNCTION
232 
233  private:
234  typename graph_data_t::const_iterator
235  find_edge(const state_t&,
236  const state_t&,
237  const hlabel_t&) const;
238 
239  geometry_t geometry_;
240  graph_data_t graph_;
241  tag_t tag_;
242  final_t final_;
243  initial_t initial_;
244 
245  //NEW ATTRIBUTES
246  boost::dynamic_bitset<> initial_bitset_;
247  boost::dynamic_bitset<> final_bitset_;
248  unsigned number_of_epsilon_;
249 
250  // number_of_state_ == 0 => there is no state.
251  unsigned number_of_state_;
252  states_data_t states_;
253 
254  SmartLabelContainer<label_t>
255  label_container_;
256 
257  }; // End of class Graph
258 
259  // FIXME: add some nice comments
260 
261 # define BMIGRAPH_TPARAM \
262  template <class S, class WordValue, class WeightValue, class SeriesValue, \
263  class Letter, class Tag, class GeometryCoords>
264 
265 # define BMIGRAPH_SERIES \
266  Graph<labels_are_series, WordValue, WeightValue, SeriesValue, \
267  Letter, Tag, GeometryCoords>
268 
269  BMIGRAPH_TPARAM
270  ADAPT_ADD_LETTER_TRANSITION_TO_SERIES_LABEL(BMIGRAPH_SERIES);
271 
272  BMIGRAPH_TPARAM
273  ADAPT_LETTER_OF_TO_SERIES_LABEL(BMIGRAPH_SERIES);
274 
275  BMIGRAPH_TPARAM
276  ADAPT_WORD_OF_TO_SERIES_LABEL(BMIGRAPH_SERIES);
277 
278 # undef BMIGRAPH_SERIES
279 # define BMIGRAPH_LETTERS \
280  Graph<labels_are_letters, WordValue, WeightValue, SeriesValue,\
281  Letter, Tag, GeometryCoords>
282 
283  BMIGRAPH_TPARAM
284  ADAPT_WORD_OF_TO_LETTERS_LABEL(BMIGRAPH_LETTERS);
285 
286  BMIGRAPH_TPARAM
287  ADAPT_SERIE_OF_TO_LETTERS_LABEL(BMIGRAPH_LETTERS);
288 
289  BMIGRAPH_TPARAM
290  ADAPT_ADD_SERIE_TRANSITION_TO_LETTERS_LABEL(BMIGRAPH_LETTERS);
291 
292 # undef BMIGRAPH_LETTERS
293 
294 # define BMIGRAPH \
295  Graph<Kind, WordValue, WeightValue, SerieValue, \
296  Letter, Tag, GeometryCoords>
297 
298  template <class Kind, class WordValue, class WeightValue, class SerieValue,
299  class Letter, class Tag, class GeometryCoords, class I>
300  Tag& op_tag(const AutomataBase<I>&, BMIGRAPH&);
301 
302  template <class Kind, class WordValue, class WeightValue, class SerieValue,
303  class Letter, class Tag, class GeometryCoords, class I>
304  const Tag& op_tag(const AutomataBase<I>&, BMIGRAPH&);
305 
306  template <class Kind, class WordValue, class WeightValue, class SerieValue,
307  class Letter, class Tag, class GeometryCoords, class I>
308  typename BMIGRAPH::geometry_t&
309  op_geometry(const AutomataBase<I>&, BMIGRAPH&);
310 
311  template <class Kind, class WordValue, class WeightValue, class SerieValue,
312  class Letter, class Tag, class GeometryCoords, class I>
313  const typename BMIGRAPH::geometry_t&
314  op_geometry(const AutomataBase<I>&, const BMIGRAPH&);
315 
316 # undef BMIGRAPH
317 # undef BMIGRAPH_TPARAM
318 
319  } // End of namespace bmig
320 
321  // This implementation can be used as an implementation of automaton.
322  VCSN_MAKE_AUTOMATON_TRAITS(bmig::Graph);
323  VCSN_MAKE_GENERALIZED_AUTOMATON_TRAITS(bmig::Graph);
324  VCSN_MAKE_MUTE_GRAPH_IMPL_TRAITS(bmig::Graph);
325  VCSN_MAKE_MUTE_GRAPH_IMPL_MONOID_TRAITS(bmig::Graph);
326 
327  // This implementation can be used as a transducer one.
328  template <class Kind,
329  class WordValue,
330  class WeightValue,
331  class SeriesValue,
332  class Letter,
333  class Tag,
334  class GeometryCoords>
335  struct transducer_traits<bmig::Graph<Kind,
336  WordValue,
337  WeightValue,
338  SeriesValue,
339  Letter,
340  Tag,
341  GeometryCoords> >
342  {
343  typedef WordValue input_monoid_elt_value_t;
344  typedef typename algebra::series_traits<WeightValue>::monoid_elt_value_t
345  output_monoid_elt_value_t;
346  typedef typename algebra::series_traits<WeightValue>::semiring_elt_value_t
347  output_semiring_elt_value_t;
348  };
349 
350  // Explain how to project type of transducer into input automaton type.
351  template <class Kind,
352  class WordValue,
353  class WeightValue,
354  class SeriesValue,
355  class Letter,
356  class Tag,
357  class GeometryCoords>
358  struct input_projection_traits<bmig::Graph<Kind,
359  WordValue,
360  WeightValue,
361  SeriesValue,
362  Letter,
363  Tag,
364  GeometryCoords> >
365  {
366  typedef bmig::Graph<Kind, WordValue, WeightValue, SeriesValue,
367  Letter, Tag, GeometryCoords>
368  self_t;
369  typedef typename transducer_traits<self_t>::output_semiring_elt_value_t
370  semiring_elt_value_t;
371  typedef typename transducer_traits<self_t>::input_monoid_elt_value_t
372  monoid_elt_value_t;
373  typedef typename algebra::mute_series_impl<SeriesValue,
374  semiring_elt_value_t,
375  monoid_elt_value_t>::ret
376  series_set_elt_value_t;
377 
378  typedef
379  bmig::Graph<Kind,
380  monoid_elt_value_t,
381  semiring_elt_value_t,
382  series_set_elt_value_t,
383  Letter,
384  Tag,
385  GeometryCoords>
386  ret;
387  };
388 
389  // Input projection for FMP transducers.
390  template <class Kind,
391  class WordValue,
392  class WeightValue,
393  class SeriesValue,
394  class Letter,
395  class Tag,
396  class GeometryCoords>
397  struct fmp_input_projection_traits<bmig::Graph<Kind,
398  WordValue,
399  WeightValue,
400  SeriesValue,
401  Letter,
402  Tag,
403  GeometryCoords> >
404  {
405  typedef bmig::Graph<Kind, WordValue, WeightValue, SeriesValue,
406  Letter, Tag, GeometryCoords>
407  self_t;
408 
409  typedef typename automaton_traits<self_t>::semiring_elt_value_t
410  semiring_elt_value_t;
411 
412  typedef typename WordValue::first_type monoid_elt_value_t;
413  typedef typename monoid_elt_value_t::value_type letter_t;
414 
415  typedef typename algebra::mute_series_impl<SeriesValue,
416  semiring_elt_value_t,
417  monoid_elt_value_t>::ret
418  series_set_elt_value_t;
419 
420  typedef
421  bmig::Graph<Kind,
422  monoid_elt_value_t,
423  semiring_elt_value_t,
424  series_set_elt_value_t,
425  letter_t,
426  Tag,
427  GeometryCoords>
428  ret;
429  };
430 
431  template <class Kind,
432  class WordValue,
433  class WeightValue,
434  class SeriesValue,
435  class Letter,
436  class Tag,
437  class GeometryCoords>
438  struct output_projection_traits<bmig::Graph<Kind,
439  WordValue,
440  WeightValue,
441  SeriesValue,
442  Letter,
443  Tag,
444  GeometryCoords> >
445  {
446  typedef bmig::Graph<Kind, WordValue, WeightValue, SeriesValue,
447  Letter, Tag, GeometryCoords>
448  self_t;
449 
450  typedef typename automaton_traits<self_t>::semiring_elt_value_t
451  series_set_elt_value_t;
452 
453  typedef typename
454  algebra::series_traits<series_set_elt_value_t>::monoid_elt_value_t
455  monoid_elt_value_t;
456 
457  typedef typename
458  algebra::series_traits<series_set_elt_value_t>::semiring_elt_value_t
459  semiring_elt_value_t;
460 
461  typedef
462  bmig::Graph<Kind,
463  monoid_elt_value_t,
464  semiring_elt_value_t,
465  series_set_elt_value_t,
466  Letter,
467  Tag,
468  GeometryCoords>
469  ret;
470  };
471 
472  // Output projection for FMP transducers.
473  template <class Kind,
474  class WordValue,
475  class WeightValue,
476  class SeriesValue,
477  class Letter,
478  class Tag,
479  class GeometryCoords>
480  struct fmp_output_projection_traits<bmig::Graph<Kind,
481  WordValue,
482  WeightValue,
483  SeriesValue,
484  Letter,
485  Tag,
486  GeometryCoords> >
487  {
488  typedef bmig::Graph<Kind, WordValue, WeightValue, SeriesValue,
489  Letter, Tag, GeometryCoords>
490  self_t;
491 
492  typedef typename WordValue::second_type monoid_elt_value_t;
493  typedef typename monoid_elt_value_t::value_type letter_t;
494 
495  typedef typename automaton_traits<self_t>::semiring_elt_value_t
496  semiring_elt_value_t;
497 
498  typedef typename algebra::mute_series_impl<SeriesValue,
499  semiring_elt_value_t,
500  monoid_elt_value_t>::ret series_set_elt_value_t;
501 
502  typedef
503  bmig::Graph<Kind,
504  monoid_elt_value_t,
505  semiring_elt_value_t,
506  series_set_elt_value_t,
507  letter_t,
508  Tag,
509  GeometryCoords>
510  ret;
511  };
512 
513  // Explain how to extend an input automaton into a transducer.
514  template <class Kind,
515  class WordValue,
516  class WeightValue,
517  class SeriesValue,
518  class Letter,
519  class Tag,
520  class GeometryCoords>
521  struct extension_traits<bmig::Graph<Kind,
522  WordValue,
523  WeightValue,
524  SeriesValue,
525  Letter,
526  Tag,
527  GeometryCoords> >
528  {
529  typedef bmig::Graph<Kind, WordValue, WeightValue,
530  SeriesValue, Letter, Tag, GeometryCoords>
531  self_t;
532  typedef typename automaton_traits<self_t>::monoid_elt_value_t
533  monoid_elt_value_t;
534  typedef typename algebra::mute_series_impl<SeriesValue,
535  SeriesValue,
536  monoid_elt_value_t>::ret
537  series_set_elt_value_t;
538 
539  typedef
540  bmig::Graph<Kind,
541  monoid_elt_value_t,
542  SeriesValue,
543  series_set_elt_value_t,
544  Letter,
545  Tag,
546  GeometryCoords>
547  ret;
548  };
549 } // End of namespace vcsn
550 
551 # if !defined VCSN_USE_INTERFACE_ONLY || defined VCSN_USE_LIB
552 # include <vaucanson/automata/implementation/bmig_graph_impl.hxx>
553 # endif // !VCSN_USE_INTERFACE_ONLY || VCSN_USE_LIB
554 
555 // FIXME __ITERATOR__ put back again later
556 //# include <vaucanson/automata/implementation/bmig_graph_letters_spec.hh>
557 
558 #endif // !VCSN_AUTOMATA_IMPLEMENTATION_BMIG_GRAPH_IMPL_HH_ //
559 
Generated on Sat Jul 14 2012 18:46:39 for Vaucanson by   doxygen 1.8.1.1