Vaucanson  1.4.1
listg_graph_impl.hh
1 // listg_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) 2005, 2006, 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 #ifndef VCSN_AUTOMATA_IMPLEMENTATION_LISTG_GRAPH_IMPL_HH
18 # define VCSN_AUTOMATA_IMPLEMENTATION_LISTG_GRAPH_IMPL_HH
19 
20 # include <set>
21 # include <map>
22 # include <vector>
23 
24 # include <vaucanson/misc/static.hh>
25 # include <vaucanson/misc/usual_macros.hh>
26 
27 # include <vaucanson/misc/support.hh>
28 # include <vaucanson/algebra/implementation/series/rat/exp.hh>
29 # include <vaucanson/automata/concept/automata_base.hh>
30 # include <vaucanson/automata/concept/automata.hh>
31 # include <vaucanson/automata/concept/transducer_base.hh>
32 # include <vaucanson/automata/concept/automata_kind.hh>
33 # include <vaucanson/automata/concept/tags.hh>
34 # include <vaucanson/automata/implementation/kind_adapter.hh>
35 # include <vaucanson/automata/implementation/geometry.hh>
36 # include <vaucanson/automata/implementation/listg/iterator.hh>
37 # include <vaucanson/automata/implementation/listg/listg_handlers.hh>
38 # include <vaucanson/automata/implementation/listg/listg_sparse_interval.hh>
39 
40 namespace vcsn
41 {
42  namespace listg
43  {
45  template <class K, class WordValue, class WeightValue,
46  class SeriesValue, class Letter, class Tag, class GeometryCoords>
47  class Graph
48  {
50  public:
51  typedef Graph<K, WordValue, WeightValue, SeriesValue,
52  Letter, Tag, GeometryCoords> self_t;
53 
54  typedef WeightValue semiring_elt_value_t;
55  typedef WordValue monoid_elt_value_t;
56  typedef WordValue word_value_t;
57  typedef SeriesValue series_set_elt_value_t;
58  typedef Letter letter_t;
59  typedef Tag tag_t;
60 
62  typedef typename LabelOf<K, WordValue, WeightValue, SeriesValue, Letter>
63  ::ret label_t;
64  typedef unsigned hstate_value_t;
65  typedef unsigned hedge_value_t;
66  typedef handler<state_h, hstate_value_t> hstate_t;
67  typedef handler<transition_h, hedge_value_t> htransition_t;
68  typedef htransition_t hedge_t;
69 
71  template<typename EdgeLabel>
72  struct edge_value
73  {
74  inline edge_value(const hstate_t& h1, const hstate_t& h2,
75  const EdgeLabel& l = EdgeLabel())
76  : label(l),
77  from(h1),
78  to(h2)
79  {}
80 
81  inline operator const EdgeLabel& () const
82  { return label; }
83 
84  inline operator EdgeLabel& ()
85  { return label; }
86 
87  EdgeLabel label;
88  hstate_t from;
89  hstate_t to;
90  };
91 
93  struct state_value
94  {
95  typedef std::set<hedge_t> edges_t;
96  inline state_value() {}
97 
98  edges_t output_edges;
99  edges_t input_edges;
100  };
101 
104  typedef misc::SparseInterval<hstate_t, std::set<hstate_t> >
105  StateContainer;
106  typedef misc::SparseInterval<hedge_t, std::set<hedge_t> >
107  EdgeContainer;
108 
109  typedef state_value state_value_t;
110  typedef edge_value<label_t> edge_value_t;
111 
112  typedef std::vector<state_value_t> state_data_t;
113  typedef std::vector<edge_value_t> edge_data_t;
114 
115  typedef StateContainer states_t;
116  typedef EdgeContainer edges_t;
117 
118  typedef std::map<hstate_t, series_set_elt_value_t>
119  initial_t;
120  typedef std::map<hstate_t, series_set_elt_value_t>
121  final_t;
122 
123  typedef misc::Support<initial_t> initial_support_t;
124  typedef misc::Support<final_t> final_support_t;
125 
126  typedef ::vcsn::listg::DeltaConstIterator<self_t, ::vcsn::listg::forward_iterator>
127  delta_iterator;
128 
129  typedef ::vcsn::listg::DeltaConstIterator<self_t, ::vcsn::listg::backward_iterator>
130  rdelta_iterator;
131  // we guarantee that the handlers of state are indexed from 0 to
132  // initial_number_of_state - 1 when using this constructor.
133  Graph();
134  Graph(unsigned initial_number_of_state,
135  unsigned number_of_edge_initially_allocated);
136 
138  states_t states() const;
139 
141  edges_t edges() const;
142 
144  initial_support_t initial() const;
145  final_support_t final() const;
146 
149  hstate_t get_state(int n) const;
150  bool has_state(const hstate_t& n) const;
151  hstate_t add_state();
152 
156  void del_state(const hstate_t& n);
157 
173  void set_initial(const hstate_t& s,
174  const series_set_elt_value_t& v,
175  const series_set_elt_value_t& z);
176  const series_set_elt_value_t&
177  get_initial(const hstate_t&,
178  const series_set_elt_value_t&) const;
179  bool is_initial(const hstate_t& s,
180  const series_set_elt_value_t&) const;
181 
182  void clear_initial();
183 
190  void set_final(const hstate_t&,
191  const series_set_elt_value_t&,
192  const series_set_elt_value_t&);
193  const series_set_elt_value_t&
194  get_final(const hstate_t&,
195  const series_set_elt_value_t&) const;
196  bool is_final(const hstate_t& s,
197  const series_set_elt_value_t&) const;
198 
199  void clear_final();
205  bool has_edge(const hedge_t& n) const;
206 
207  hedge_t add_edge(const hstate_t& h1,
208  const hstate_t& h2,
209  const label_t& v);
210  void del_edge(const hedge_t& e);
211 
212  hstate_t src_of(const hedge_t& e1) const;
213  hstate_t dst_of(const hedge_t& e2) const;
214 
215  const label_t& label_of(const hedge_t& n) const;
216  void update(const hedge_t&, label_t);
221  template <class S>
222  bool exists(const AutomataBase<S>& s) const;
223 
226 
227  self_t& clone() const;
228 
231  tag_t& tag();
232  const tag_t& tag() const;
237  typedef vcsn::geometry<hstate_t, hedge_t, GeometryCoords>
238  geometry_t;
239  geometry_t& geometry();
240  const geometry_t& geometry() const;
243  geometry_t geometry_;
244 
245  public:
246  state_data_t states_;
247  edge_data_t edges_;
248  std::set<hstate_t> removed_states_;
249  std::set<hedge_t> removed_edges_;
250  tag_t tag_;
251  final_t final_;
252  initial_t initial_;
253  };
254 
255 
256 # define TParam \
257  template <class S, class WordValue, class WeightValue, class SeriesValue, \
258  class Letter, class Tag, class GeometryCoords>
259 # define GRAPH \
260  Graph<Kind, WordValue, WeightValue, SerieValue, \
261  Letter, Tag, GeometryCoords>
262 
263 
264 
265  TParam
266  ADAPT_ADD_LETTER_TRANSITION_TO_SERIES_LABEL(Graph<labels_are_series,
267  WordValue, WeightValue,
268  SeriesValue, Letter, Tag,
269  GeometryCoords>);
270 
271  TParam
272  ADAPT_LETTER_OF_TO_SERIES_LABEL(Graph<labels_are_series,
273  WordValue, WeightValue,
274  SeriesValue, Letter, Tag,
275  GeometryCoords>);
276 
277  TParam
278  ADAPT_WORD_OF_TO_SERIES_LABEL(Graph<labels_are_series,
279  WordValue, WeightValue,
280  SeriesValue, Letter, Tag,
281  GeometryCoords>);
282 
283  TParam
284  ADAPT_WORD_OF_TO_LETTERS_LABEL(Graph<labels_are_letters,
285  WordValue, WeightValue,
286  SeriesValue, Letter, Tag,
287  GeometryCoords>);
288 
289  TParam
290  ADAPT_SERIE_OF_TO_LETTERS_LABEL(Graph<labels_are_letters,
291  WordValue, WeightValue,
292  SeriesValue, Letter, Tag,
293  GeometryCoords>);
294 
295  TParam
296  ADAPT_ADD_SERIE_TRANSITION_TO_LETTERS_LABEL(Graph<labels_are_letters,
297  WordValue, WeightValue,
298  SeriesValue, Letter, Tag,
299  GeometryCoords>);
300 
301  template <class Kind, class WordValue, class WeightValue, class SerieValue,
302  class Letter, class Tag, class GeometryCoords, class I>
303  Tag& op_tag(const AutomataBase<I>&,
304  Graph<Kind, WordValue, WeightValue,
305  SerieValue, Letter, Tag,
306  GeometryCoords>&);
307 
308  template <class Kind, class WordValue, class WeightValue, class SerieValue,
309  class Letter, class Tag, class GeometryCoords, class I>
310  const Tag& op_tag(const AutomataBase<I>&,
311  const Graph<Kind, WordValue, WeightValue,
312  SerieValue, Letter, Tag, GeometryCoords>&);
313 
314  template <class Kind, class WordValue, class WeightValue, class SerieValue,
315  class Letter, class Tag, class GeometryCoords, class I>
316  typename GRAPH::geometry_t&
317  op_geometry(const AutomataBase<I>&,
318  Graph<Kind, WordValue, WeightValue,
319  SerieValue, Letter, Tag, GeometryCoords>&);
320 
321  template <class Kind, class WordValue, class WeightValue, class SerieValue,
322  class Letter, class Tag, class GeometryCoords, class I>
323  const typename GRAPH::geometry_t&
324  op_geometry(const AutomataBase<I>&,
325  const Graph<Kind, WordValue,
326  WeightValue, SerieValue, Letter, Tag,
327  GeometryCoords>&);
328 # undef TParam
329 # undef GRAPH
330 
331  } // End of namespace listg
332 
333 
334  // This implementation can be used as an implementation of automaton.
335  VCSN_MAKE_AUTOMATON_TRAITS(listg::Graph);
336  VCSN_MAKE_GENERALIZED_AUTOMATON_TRAITS(listg::Graph);
337  VCSN_MAKE_MUTE_GRAPH_IMPL_TRAITS(listg::Graph);
338  VCSN_MAKE_MUTE_GRAPH_IMPL_MONOID_TRAITS(listg::Graph);
339 
340  // This implementation can be used as a transducer one.
341  template <class Kind,
342  class WordValue,
343  class WeightValue,
344  class SeriesValue,
345  class Letter,
346  class Tag,
347  class GeometryCoords>
348  struct transducer_traits<listg::Graph<Kind,
349  WordValue,
350  WeightValue,
351  SeriesValue,
352  Letter,
353  Tag,
354  GeometryCoords> >
355  {
356  typedef WordValue input_monoid_elt_value_t;
357  typedef typename algebra::series_traits<WeightValue>::monoid_elt_value_t
358  output_monoid_elt_value_t;
359  typedef typename algebra::series_traits<WeightValue>::semiring_elt_value_t
360  output_semiring_elt_value_t;
361  };
362 
363  // Explain how to project type of transducer into input automaton type.
364  template <class Kind,
365  class WordValue,
366  class WeightValue,
367  class SeriesValue,
368  class Letter,
369  class Tag,
370  class GeometryCoords>
371  struct input_projection_traits<listg::Graph<Kind,
372  WordValue,
373  WeightValue,
374  SeriesValue,
375  Letter,
376  Tag,
377  GeometryCoords> >
378  {
379  typedef listg::Graph<Kind, WordValue, WeightValue, SeriesValue,
380  Letter, Tag, GeometryCoords>
381  self_t;
382  typedef typename transducer_traits<self_t>::output_semiring_elt_value_t
383  semiring_elt_value_t;
384  typedef typename transducer_traits<self_t>::input_monoid_elt_value_t
385  monoid_elt_value_t;
386  typedef typename algebra::mute_series_impl<SeriesValue,
387  semiring_elt_value_t,
388  monoid_elt_value_t>::ret
389  series_set_elt_value_t;
390 
391  typedef
392  listg::Graph<Kind,
393  monoid_elt_value_t,
394  semiring_elt_value_t,
395  series_set_elt_value_t,
396  Letter,
397  Tag,
398  GeometryCoords>
399  ret;
400  };
401 
402  // Input projection for FMP transducers.
403  template <class Kind,
404  class WordValue,
405  class WeightValue,
406  class SeriesValue,
407  class Letter,
408  class Tag,
409  class GeometryCoords>
410  struct fmp_input_projection_traits<listg::Graph<Kind,
411  WordValue,
412  WeightValue,
413  SeriesValue,
414  Letter,
415  Tag,
416  GeometryCoords> >
417  {
418  typedef listg::Graph<Kind, WordValue, WeightValue, SeriesValue,
419  Letter, Tag, GeometryCoords>
420  self_t;
421 
422  typedef typename automaton_traits<self_t>::semiring_elt_value_t
423  semiring_elt_value_t;
424 
425  typedef typename WordValue::first_type monoid_elt_value_t;
426  typedef typename monoid_elt_value_t::value_type letter_t;
427 
428  typedef typename algebra::mute_series_impl<SeriesValue,
429  semiring_elt_value_t,
430  monoid_elt_value_t>::ret
431  series_set_elt_value_t;
432 
433  typedef
434  listg::Graph<Kind,
435  monoid_elt_value_t,
436  semiring_elt_value_t,
437  series_set_elt_value_t,
438  letter_t,
439  Tag,
440  GeometryCoords>
441  ret;
442  };
443 
444  template <class Kind,
445  class WordValue,
446  class WeightValue,
447  class SeriesValue,
448  class Letter,
449  class Tag,
450  class GeometryCoords>
451  struct output_projection_traits<listg::Graph<Kind,
452  WordValue,
453  WeightValue,
454  SeriesValue,
455  Letter,
456  Tag, GeometryCoords> >
457  {
458  typedef listg::Graph<Kind, WordValue, WeightValue, SeriesValue,
459  Letter, Tag, GeometryCoords>
460  self_t;
461 
462  typedef typename automaton_traits<self_t>::semiring_elt_value_t
463  series_set_elt_value_t;
464 
465  typedef typename
466  algebra::series_traits<series_set_elt_value_t>::monoid_elt_value_t
467  monoid_elt_value_t;
468 
469  typedef typename
470  algebra::series_traits<series_set_elt_value_t>::semiring_elt_value_t
471  semiring_elt_value_t;
472 
473  typedef
474  listg::Graph<Kind,
475  monoid_elt_value_t,
476  semiring_elt_value_t,
477  series_set_elt_value_t,
478  Letter,
479  Tag,
480  GeometryCoords>
481  ret;
482  };
483 
484  // Output projection for FMP transducers.
485  template <class Kind,
486  class WordValue,
487  class WeightValue,
488  class SeriesValue,
489  class Letter,
490  class Tag,
491  class GeometryCoords>
492  struct fmp_output_projection_traits<listg::Graph<Kind,
493  WordValue,
494  WeightValue,
495  SeriesValue,
496  Letter,
497  Tag,
498  GeometryCoords> >
499  {
500  typedef listg::Graph<Kind, WordValue, WeightValue, SeriesValue,
501  Letter, Tag, GeometryCoords>
502  self_t;
503 
504  typedef typename WordValue::second_type monoid_elt_value_t;
505  typedef typename monoid_elt_value_t::value_type letter_t;
506 
507  typedef typename automaton_traits<self_t>::semiring_elt_value_t
508  semiring_elt_value_t;
509 
510  typedef typename algebra::mute_series_impl<SeriesValue,
511  semiring_elt_value_t,
512  monoid_elt_value_t>::ret series_set_elt_value_t;
513 
514  typedef
515  listg::Graph<Kind,
516  monoid_elt_value_t,
517  semiring_elt_value_t,
518  series_set_elt_value_t,
519  letter_t,
520  Tag,
521  GeometryCoords>
522  ret;
523  };
524 
525  // Explain how to extend an input automaton into a transducer.
526  template <class Kind,
527  class WordValue,
528  class WeightValue,
529  class SeriesValue,
530  class Letter,
531  class Tag,
532  class GeometryCoords>
533  struct extension_traits<listg::Graph<Kind,
534  WordValue,
535  WeightValue,
536  SeriesValue,
537  Letter,
538  Tag,
539  GeometryCoords> >
540  {
541  typedef listg::Graph<Kind, WordValue, WeightValue,
542  SeriesValue, Letter, Tag, GeometryCoords>
543  self_t;
544  typedef typename automaton_traits<self_t>::monoid_elt_value_t
545  monoid_elt_value_t;
546  typedef typename algebra::mute_series_impl<SeriesValue,
547  SeriesValue,
548  monoid_elt_value_t>::ret
549  series_set_elt_value_t;
550 
551  typedef
552  listg::Graph<Kind,
553  monoid_elt_value_t,
554  SeriesValue,
555  series_set_elt_value_t,
556  Letter,
557  Tag,
558  GeometryCoords>
559  ret;
560  };
561 } // Enf of namespace vcsn
562 
563 
564 # if !defined VCSN_USE_INTERFACE_ONLY || defined VCSN_USE_LIB
565 # include <vaucanson/automata/implementation/listg_graph_impl.hxx>
566 # endif // VCSN_USE_INTERFACE_ONLY
567 
568 #endif // ! VCSN_AUTOMATA_IMPLEMENTATION_LISTG_GRAPH_IMPL_HH
Generated on Sat Jul 14 2012 18:46:40 for Vaucanson by   doxygen 1.8.1.1