graph.hh

00001 // graph.hh: this file is part of the Vaucanson project.
00002 //
00003 // Vaucanson, a generic library for finite state machines.
00004 //
00005 // Copyright (C) 2005, 2006, 2007 The Vaucanson Group.
00006 //
00007 // This program is free software; you can redistribute it and/or
00008 // modify it under the terms of the GNU General Public License
00009 // as published by the Free Software Foundation; either version 2
00010 // of the License, or (at your option) any later version.
00011 //
00012 // The complete GNU General Public Licence Notice can be found as the
00013 // `COPYING' file in the root directory.
00014 //
00015 // The Vaucanson Group consists of people listed in the `AUTHORS' file.
00016 //
00017 #ifndef VCSN_AUTOMATA_IMPLEMENTATION_GRAPH_HH
00018 # define VCSN_AUTOMATA_IMPLEMENTATION_GRAPH_HH
00019 
00020 # include <set>
00021 # include <map>
00022 # include <vector>
00023 
00024 # include <vaucanson/misc/sparse_interval.hh>
00025 # include <vaucanson/misc/support.hh>
00026 # include <vaucanson/misc/static.hh>
00027 # include <vaucanson/misc/usual_macros.hh>
00028 
00029 # include <vaucanson/automata/concept/handlers.hh>
00030 # include <vaucanson/automata/concept/automata_base.hh>
00031 # include <vaucanson/automata/concept/transducer_base.hh>
00032 # include <vaucanson/automata/concept/automata_kind.hh>
00033 # include <vaucanson/automata/concept/tags.hh>
00034 # include <vaucanson/automata/implementation/kind_adapter.hh>
00035 # include <vaucanson/automata/implementation/geometry.hh>
00036 
00037 
00038 namespace vcsn
00039 {
00040 
00041 
00042   typedef htransition_t hedge_t;
00043   namespace delta_kind
00044   {
00045     typedef transitions edges;
00046   }
00047 
00049   template<typename EdgeLabel>
00050   struct edge_value
00051   {
00052       edge_value(hstate_t, hstate_t, const EdgeLabel& v = EdgeLabel());
00053 
00054       operator const EdgeLabel& () const
00055       { return label; }
00056       operator EdgeLabel& ()
00057       { return label; }
00058 
00059       EdgeLabel label;
00060       hstate_t  from;
00061       hstate_t  to;
00062   };
00063 
00065   struct state_value
00066   {
00067       typedef std::set<hedge_t> edges_t;
00068       state_value();
00069 
00070       edges_t output_edges;
00071       edges_t input_edges;
00072   };
00073 
00076   typedef misc::SparseInterval<hstate_t, std::set<hstate_t> > StateContainer;
00077   typedef misc::SparseInterval<hedge_t, std::set<hedge_t> > EdgeContainer;
00078 
00079 
00081   template <class K, class WordValue, class WeightValue,
00082             class SeriesValue, class Letter, class Tag, class Geometry>
00083   class Graph
00084   {
00086     public:
00087       typedef Graph<K, WordValue, WeightValue, SeriesValue,
00088                     Letter, Tag, Geometry>                      self_t;
00089 
00091     public:
00092       typedef typename LabelOf<K, WordValue, WeightValue, SeriesValue, Letter>
00093       ::ret label_t;
00094 
00095       typedef state_value                       state_value_t;
00096       typedef edge_value<label_t>               edge_value_t;
00097 
00098       typedef std::vector<state_value_t>        state_data_t;
00099       typedef std::vector<edge_value_t>         edge_data_t;
00100 
00101       typedef StateContainer            states_t;
00102       typedef EdgeContainer             edges_t;
00103 
00104       typedef SeriesValue                       series_set_elt_value_t;
00105 
00106       typedef std::map<hstate_t, series_set_elt_value_t> initial_t;
00107       typedef std::map<hstate_t, series_set_elt_value_t> final_t;
00108 
00109       typedef misc::Support<initial_t>  initial_support_t;
00110       typedef misc::Support<final_t>    final_support_t;
00111 
00112     public:
00113       // we guarantee that the handlers of state are indexed from 0 to
00114       // initial_number_of_state - 1 when using this constructor.
00115       Graph();
00116       Graph(unsigned initial_number_of_state,
00117             unsigned number_of_edge_initially_allocated);
00118 
00120       states_t states() const;
00121 
00123       edges_t edges() const;
00124 
00126       initial_support_t initial() const;
00127       final_support_t final() const;
00128 
00131     public:
00132       bool has_state(hstate_t n) const;
00133 
00134     public:
00135       hstate_t add_state();
00136 
00140       void del_state(hstate_t n);
00141 
00142     public:
00158       void set_initial(hstate_t s,
00159                        const series_set_elt_value_t& v,
00160                        const series_set_elt_value_t& z);
00161       const series_set_elt_value_t&
00162       get_initial(hstate_t, const series_set_elt_value_t&) const;
00163       void clear_initial();
00164 
00171       void set_final(hstate_t,
00172                      const series_set_elt_value_t&,
00173                      const series_set_elt_value_t&);
00174       const series_set_elt_value_t&
00175       get_final(hstate_t, const series_set_elt_value_t&) const;
00176       void clear_final();
00182     public:
00183       bool has_edge(hedge_t n) const;
00184 
00185     public:
00186       hedge_t add_edge(hstate_t h1, hstate_t h2, const label_t& v);
00187       void del_edge(hedge_t e);
00188 
00189     public:
00190       hstate_t src_of(hedge_t e1) const;
00191       hstate_t dst_of(hedge_t e2) const;
00192 
00193     public:
00194       const label_t& label_of(hedge_t n) const;
00195       void update(hedge_t, label_t);
00200     public:
00201       template <class S>
00202       bool exists(const AutomataBase<S>& s) const;
00203 
00204     public:
00205 
00207 # define DECLARE_DELTA_FUNCTION(DeltaName, DKind)                       \
00208     template <class OutputIterator, typename Query>                     \
00209     void DeltaName(OutputIterator res, hstate_t from,                   \
00210                    const Query& q, delta_kind::DKind) const
00211       DECLARE_DELTA_FUNCTION (delta, states);
00212       DECLARE_DELTA_FUNCTION (delta, edges);
00213       DECLARE_DELTA_FUNCTION (rdelta, states);
00214       DECLARE_DELTA_FUNCTION (rdelta, edges);
00215 # undef DECLARE_DELTA_FUNCTION
00216 
00217 # define DECLARE_DELTAF_BOOL_FUNCTION(DeltaName, DKind, IsBool)         \
00218     template <class Functor, typename Query>                            \
00219     void DeltaName(Functor& fun, hstate_t from,                         \
00220                    const Query& q, delta_kind::DKind,                   \
00221                    misc::IsBool ## _t) const
00222       DECLARE_DELTAF_BOOL_FUNCTION (deltaf, states, true);
00223       DECLARE_DELTAF_BOOL_FUNCTION (deltaf, states, false);
00224       DECLARE_DELTAF_BOOL_FUNCTION (deltaf, edges, true);
00225       DECLARE_DELTAF_BOOL_FUNCTION (deltaf, edges, false);
00226       DECLARE_DELTAF_BOOL_FUNCTION (rdeltaf, states, true);
00227       DECLARE_DELTAF_BOOL_FUNCTION (rdeltaf, states, false);
00228       DECLARE_DELTAF_BOOL_FUNCTION (rdeltaf, edges, true);
00229       DECLARE_DELTAF_BOOL_FUNCTION (rdeltaf, edges, false);
00230 # undef DECLARE_DELTAF_BOOL_FUNCTION
00231 
00232 # define DECLARE_DELTAF_FUNCTION(DeltaName)                             \
00233     template <class Functor, typename Query, typename DKind>            \
00234     void DeltaName(Functor& fun, hstate_t from,                         \
00235                    const Query& q, delta_kind::kind<DKind>) const
00236       DECLARE_DELTAF_FUNCTION (deltaf);
00237       DECLARE_DELTAF_FUNCTION (rdeltaf);
00238 
00239 # undef DECLARE_DELTAF_FUNCTION
00240 
00243     public:
00245       self_t& clone() const;
00246 
00249     public:
00250       typedef Tag tag_t;
00251       tag_t& tag();
00252       const tag_t& tag() const;
00257     public:
00258       typedef Geometry geometry_t;
00259       geometry_t& geometry();
00260       const geometry_t& geometry() const;
00263     private:
00264       geometry_t                geometry_;
00265 
00266     public:
00267       state_data_t              states_;
00268       edge_data_t               edges_;
00269       std::set<hstate_t>        removed_states_;
00270       std::set<hedge_t>         removed_edges_;
00271       tag_t                     tag_;
00272       final_t                   final_;
00273       initial_t                 initial_;
00274   };
00275 
00276 
00277 # define TParam                                                         \
00278   template <class S, class WordValue, class WeightValue, class SeriesValue, \
00279             class Letter, class Tag, class Geometry>
00280 
00281   TParam
00282   ADAPT_ADD_LETTER_TRANSITION_TO_SERIES_LABEL(Graph<labels_are_series,
00283                                               WordValue, WeightValue,
00284                                               SeriesValue, Letter, Tag, Geometry>);
00285 
00286 
00287   TParam
00288   ADAPT_LETTER_OF_TO_SERIES_LABEL(Graph<labels_are_series,
00289                                   WordValue, WeightValue,
00290                                   SeriesValue, Letter, Tag, Geometry>);
00291 
00292   TParam
00293   ADAPT_WORD_OF_TO_SERIES_LABEL(Graph<labels_are_series,
00294                                 WordValue, WeightValue,
00295                                 SeriesValue, Letter, Tag, Geometry>);
00296 
00297   TParam
00298   ADAPT_WORD_OF_TO_LETTERS_LABEL(Graph<labels_are_letters,
00299                                  WordValue, WeightValue,
00300                                  SeriesValue, Letter, Tag, Geometry>);
00301 
00302   TParam
00303   ADAPT_SERIE_OF_TO_LETTERS_LABEL(Graph<labels_are_letters,
00304                                   WordValue, WeightValue,
00305                                   SeriesValue, Letter, Tag, Geometry>);
00306 
00307   TParam
00308   ADAPT_ADD_SERIE_TRANSITION_TO_LETTERS_LABEL(Graph<labels_are_letters,
00309                                               WordValue, WeightValue,
00310                                               SeriesValue, Letter, Tag, Geometry>);
00311 
00312   template <class Kind, class WordValue, class WeightValue, class SerieValue,
00313             class Letter, class Tag, class Geometry, class I>
00314   Tag& op_tag(const AutomataBase<I>&,
00315               Graph<Kind, WordValue, WeightValue,
00316               SerieValue, Letter, Tag, Geometry>&);
00317 
00318   template <class Kind, class WordValue, class WeightValue, class SerieValue,
00319             class Letter, class Tag, class Geometry, class I>
00320   const Tag& op_tag(const AutomataBase<I>&,
00321                     const Graph<Kind, WordValue, WeightValue,
00322                     SerieValue, Letter, Tag, Geometry>&);
00323 
00324   template <class Kind, class WordValue, class WeightValue, class SerieValue,
00325             class Letter, class Tag, class Geometry, class I>
00326   Geometry&
00327   op_geometry(const AutomataBase<I>&,
00328               Graph<Kind, WordValue, WeightValue,
00329               SerieValue, Letter, Tag, Geometry>&);
00330 
00331   template <class Kind, class WordValue, class WeightValue, class SerieValue,
00332             class Letter, class Tag, class Geometry, class I>
00333   const Geometry&
00334   op_geometry(const AutomataBase<I>&,
00335               const Graph<Kind, WordValue, WeightValue,
00336               SerieValue, Letter, Tag, Geometry>&);
00337 
00338 
00339 
00340 # undef TParam
00341 
00342   // This implementation can be used as an implementation of automaton.
00343   template <class Kind,
00344             class WordValue,
00345             class WeightValue,
00346             class SeriesValue,
00347             class Letter,
00348             class Tag,
00349             class Geometry>
00350   struct automaton_traits<Graph<Kind,
00351                                 WordValue,
00352                                 WeightValue,
00353                                 SeriesValue,
00354                                 Letter,
00355                                 Tag,
00356                                 Geometry>  >
00357   {
00358       typedef SeriesValue                               series_set_elt_value_t;
00359       typedef WordValue                                 word_value_t;
00360       typedef WordValue                                 monoid_elt_value_t;
00361       typedef WeightValue                               semiring_elt_value_t;
00362       typedef Letter                                    letter_t;
00363       typedef typename LabelOf<Kind, WordValue, WeightValue, SeriesValue, Letter>
00364       ::ret                                             label_t;
00365       typedef Tag                                       tag_t;
00366       typedef edge_value<label_t>                       transition_value_t;
00367       typedef state_value                               state_value_t;
00368       typedef std::vector<state_value_t>                state_data_t;
00369       typedef std::vector<transition_value_t>           transition_data_t;
00370 
00371       typedef StateContainer                            states_t;
00372       typedef EdgeContainer                             transitions_t;
00373 
00374       typedef typename states_t::iterator               state_iterator;
00375       typedef typename transitions_t::iterator          transition_iterator;
00376 
00377       typedef std::map<hstate_t, series_set_elt_value_t>        initial_t;
00378       typedef std::map<hstate_t, series_set_elt_value_t>        final_t;
00379       typedef misc::Support<initial_t>                  initial_support_t;
00380       typedef misc::Support<final_t>                    final_support_t;
00381       typedef typename initial_support_t::iterator      initial_iterator;
00382       typedef typename final_support_t::iterator        final_iterator;
00383 
00384       typedef Geometry                                  geometry_t;
00385   };
00386 
00387   // This implementation can be used as a transducer one.
00388   template <class Kind,
00389             class WordValue,
00390             class WeightValue,
00391             class SeriesValue,
00392             class Letter,
00393             class Tag,
00394             class Geometry>
00395   struct transducer_traits<Graph<Kind,
00396                                  WordValue,
00397                                  WeightValue,
00398                                  SeriesValue,
00399                                  Letter,
00400                                  Tag,
00401                                  Geometry>  >
00402   {
00403       typedef WordValue                 input_monoid_elt_value_t;
00404       typedef typename algebra::series_traits<WeightValue>::monoid_elt_value_t
00405       output_monoid_elt_value_t;
00406       typedef typename algebra::series_traits<WeightValue>::semiring_elt_value_t
00407       output_semiring_elt_value_t;
00408   };
00409 
00410   // Explain how to project type of transducer into input automaton type.
00411   template <class S,
00412             class Kind,
00413             class WordValue,
00414             class WeightValue,
00415             class SeriesValue,
00416             class Letter,
00417             class Tag,
00418             class Geometry>
00419   struct projection_traits<S, Graph<Kind,
00420                                     WordValue,
00421                                     WeightValue,
00422                                     SeriesValue,
00423                                     Letter,
00424                                     Tag,
00425                                     Geometry>  >
00426   {
00427       typedef Graph<Kind, WordValue, WeightValue, SeriesValue,
00428                     Letter, Tag, Geometry>                      self_t;
00429       typedef typename transducer_traits<self_t>::output_semiring_elt_value_t
00430       semiring_elt_value_t;
00431       typedef typename transducer_traits<self_t>::input_monoid_elt_value_t
00432       monoid_elt_value_t;
00433       typedef typename algebra::mute_series_impl<SeriesValue,
00434                                                  semiring_elt_value_t,
00435                                                  monoid_elt_value_t>
00436       ::ret series_set_elt_value_t;
00437 
00438       typedef
00439       Graph<Kind,
00440             monoid_elt_value_t,
00441             semiring_elt_value_t,
00442             series_set_elt_value_t,
00443             Letter,
00444             Tag,
00445             Geometry>
00446       ret;
00447   };
00448 
00449   template <class Kind,
00450             class WordValue,
00451             class WeightValue,
00452             class SeriesValue,
00453             class Letter,
00454             class Tag,
00455             class Geometry>
00456   struct output_projection_traits<Graph<Kind,
00457                                         WordValue,
00458                                         WeightValue,
00459                                         SeriesValue,
00460                                         Letter,
00461                                         Tag, Geometry>  >
00462   {
00463       typedef Graph<Kind, WordValue, WeightValue, SeriesValue,
00464                     Letter, Tag, Geometry>                      self_t;
00465 
00466       typedef typename automaton_traits<self_t>::semiring_elt_value_t
00467       series_set_elt_value_t;
00468 
00469       typedef typename
00470       algebra::series_traits<series_set_elt_value_t>::monoid_elt_value_t
00471       monoid_elt_value_t;
00472 
00473       typedef typename
00474       algebra::series_traits<series_set_elt_value_t>::semiring_elt_value_t
00475       semiring_elt_value_t;
00476 
00477       typedef
00478       Graph<Kind,
00479             monoid_elt_value_t,
00480             semiring_elt_value_t,
00481             series_set_elt_value_t,
00482             Letter,
00483             Tag,
00484             Geometry>
00485       ret;
00486   };
00487 
00488   // Explain how to extend an input automaton into a transducer.
00489   template <class Kind,
00490             class WordValue,
00491             class WeightValue,
00492             class SeriesValue,
00493             class Letter,
00494             class Tag,
00495             class Geometry>
00496   struct extension_traits<Graph<Kind,
00497                                 WordValue,
00498                                 WeightValue,
00499                                 SeriesValue,
00500                                 Letter,
00501                                 Tag,
00502                                 Geometry>  >
00503   {
00504       typedef Graph<Kind, WordValue, WeightValue,
00505                     SeriesValue, Letter, Tag, Geometry>         self_t;
00506       typedef typename automaton_traits<self_t>::monoid_elt_value_t
00507       monoid_elt_value_t;
00508       typedef typename algebra::mute_series_impl<SeriesValue, SeriesValue, monoid_elt_value_t>
00509       ::ret series_set_elt_value_t;
00510 
00511       typedef
00512       Graph<Kind,
00513             monoid_elt_value_t,
00514             SeriesValue,
00515             series_set_elt_value_t,
00516             Letter,
00517             Tag,
00518             Geometry>
00519       ret;
00520   };
00521 
00522 }
00523 
00524 
00525 # if !defined VCSN_USE_INTERFACE_ONLY || defined VCSN_USE_LIB
00526 #  include <vaucanson/automata/implementation/graph.hxx>
00527 # endif // VCSN_USE_INTERFACE_ONLY
00528 
00529 #endif // ! VCSN_AUTOMATA_IMPLEMENTATION_GRAPH_HH

Generated on Sun Jul 29 19:35:19 2007 for Vaucanson by  doxygen 1.5.2