Vaucanson: bmig_graph_impl.hh Source File

00001 // bmig_graph_impl.hh: this file is part of the Vaucanson project.
00002 //
00003 // Vaucanson, a generic library for finite state machines.
00004 //
00005 // Copyright (C) 2007, 2008 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 
00018 #ifndef VCSN_AUTOMATA_IMPLEMENTATION_BMIG_GRAPH_IMPL_HH_
00019 # define VCSN_AUTOMATA_IMPLEMENTATION_BMIG_GRAPH_IMPL_HH_
00020 # include <boost/dynamic_bitset.hpp>
00021 # include <boost/shared_ptr.hpp>
00022 
00023 # include <vaucanson/algebra/implementation/series/rat/exp.hh>
00024 # include <vaucanson/automata/implementation/bmig/vgraph_container.hh>
00025 # include <vaucanson/automata/implementation/bmig/bmig_handlers.hh>
00026 # include <vaucanson/automata/implementation/bmig/iterator.hh>
00027 # include <vaucanson/automata/concept/automata_base.hh>
00028 # include <vaucanson/automata/concept/automata.hh>
00029 # include <vaucanson/automata/concept/automata_kind.hh>
00030 # include <vaucanson/automata/implementation/bmig/bmig_support.hh>
00031 # include <vaucanson/automata/concept/transducer_base.hh>
00032 # include <vaucanson/automata/concept/smart_label.hh>
00033 # include <vaucanson/automata/implementation/kind_adapter.hh>
00034 # include <vaucanson/automata/implementation/geometry.hh>
00035 # include <vaucanson/automata/concept/tags.hh>
00036 # include <vaucanson/misc/hash.hh>
00037 # include <vaucanson/automata/implementation/bmig/initial_value.hh>
00038 # include <vaucanson/automata/implementation/bmig/graphcontainer.hh>
00039 # include <vaucanson/automata/implementation/bmig/edge_value.hh>
00040 # include <vaucanson/automata/implementation/bmig/bmig_functors.hh>
00041 # include <vaucanson/automata/implementation/bmig/initial_container.hh>
00042 
00043 namespace vcsn
00044 {
00045   namespace bmig
00046   {
00047 
00048     // class Graph.
00049     template <typename Kind, typename WordValue, typename WeightValue,
00050     typename SeriesValue, typename Letter, typename Tag, typename GeometryCoords>
00051     class Graph
00052     {
00053       public:
00054         /*
00055         ** Type definitions
00056         */
00057 
00058         // self definition.
00059         typedef Graph<Kind, WordValue, WeightValue,
00060                 SeriesValue, Letter, Tag, GeometryCoords>
00061                                                         self_t;
00062 
00063         typedef WeightValue                             semiring_elt_value_t;
00064         typedef WordValue                               monoid_elt_value_t;
00065         typedef WordValue                               word_value_t;
00066         typedef SeriesValue                             series_set_elt_value_t;
00067         typedef Letter                                  letter_t;
00068         typedef Tag                                     tag_t;
00069 
00070         typedef typename LabelOf<Kind, WordValue, WeightValue,
00071                 SeriesValue, Letter>::ret               label_t;
00072 
00073         //typedef typename SmartLabelContainer<label_t>::hlabel_t
00074         typedef label_t
00075                                                         hlabel_t;
00076 
00077         typedef boost::shared_ptr<std::size_t>          state_t;
00078         // State descriptor.
00079         //
00080         typedef handler<state_h, state_t>               hstate_t;
00081 
00082         typedef EdgeValue<state_t, label_t>             edge_data_t;
00083         //typedef EdgeValue<state_t, hlabel_t>          edge_data_t;
00084 
00085         typedef GraphContainer<state_t, label_t, edge_data_t>   graph_data_t;
00086         //typedef GraphContainer<state_t, hlabel_t, edge_data_t>        graph_data_t;
00087 
00088         // Transition descriptor.
00089         //
00090         // We store a pointer to an EdgeValue to avoid a new index on transitions and
00091         // get the data more quickly. Actually this is the adresse of an element
00092         // inserted in the multi_index.
00093         // We are allowed to do so since Boost::multi_index guaranties that the data
00094         // inserted will not be reallocated.
00095         //
00096         // We may need to try storing an iterator instead of a pointer. We haven't tried yet
00097         // since its size is higher than a simple pointer.
00098         typedef typename graph_data_t::iterator
00099                                                         edges_iterator;
00100         typedef handler<transition_h, edges_iterator>   htransition_t;
00101         typedef htransition_t                           hedge_t;
00102 
00103         //The graph stores  edges only, thus we can define this type.
00104         typedef VGraphContainer<edges_iterator, graph_data_t, htransition_t> edges_t;
00105         typedef std::vector<state_t>            states_data_t;
00106         typedef misc::Support<states_data_t>    states_t;
00107 
00108         //FIXME: find a better name than initial_container_t. The word initial
00109         //is ambiguous since we use it also for final_t
00110         typedef InitialValue<state_t, series_set_elt_value_t>
00111                                                           initial_value_t;
00112         typedef initial_value_t                           final_value_t;
00113         typedef InitialContainer<initial_value_t, state_t>
00114                                                           initial_container_t;
00115 
00116         typedef typename initial_container_t::Type        initial_t;
00117         typedef initial_t                                 final_t;
00118 
00119         typedef misc::Support<initial_container_t>        initial_support_t;
00120         typedef misc::Support<initial_container_t>        final_support_t;
00121 
00122         typedef GeometryCoords                            geometry_coords_t;
00123 
00124         typedef vcsn::geometry<hstate_t, htransition_t, GeometryCoords>
00125                                                           geometry_t;
00126 
00127         //Definition of various iterator types for the graph structure.
00128         typedef typename graph_data_t::iterator           iterator;
00129         typedef typename graph_data_t::const_iterator     const_iterator;
00130         typedef iterator                                  transition_iterator;
00131 
00132         typedef typename index_iterator<graph_data_t, src>::type
00133                                                           src_iterator;
00134         typedef src_iterator                              src_const_iterator;
00135         typedef typename index_iterator<graph_data_t, dst>::type
00136                                                           dst_iterator;
00137         typedef dst_iterator                              dst_const_iterator;
00138         typedef std::pair<src_iterator, src_iterator>     src_range;
00139         typedef std::pair<dst_iterator, dst_iterator>     dst_range;
00140 
00141 // FIXME: is it useful?
00142 //      typedef typename index_iterator<graph_data_t, pred>::type
00143 //                                                        pred_iterator;
00144 //      typedef pred_iterator                             pred_const_iterator;
00145 //      typedef std::pair<pred_iterator, pred_iterator>   pred_range;
00146         typedef typename index_iterator<graph_data_t, succ>::type
00147                                                           succ_iterator;
00148         typedef succ_iterator                             succ_const_iterator;
00149         typedef std::pair<succ_iterator, succ_iterator>   succ_range;
00150 
00151         typedef ::vcsn::bmig::DeltaConstIterator<self_t, hstate_t, src_iterator>
00152                                                           delta_state_iterator;
00153         typedef ::vcsn::bmig::DeltaConstIterator<self_t, htransition_t, src_iterator>
00154                                                           delta_transition_iterator;
00155         typedef ::vcsn::bmig::DeltaConstIterator<self_t, hstate_t, dst_iterator>
00156                                                           rdelta_state_iterator;
00157         typedef ::vcsn::bmig::DeltaConstIterator<self_t, htransition_t, dst_iterator>
00158                                                           rdelta_transition_iterator;
00159 
00160         Graph ();
00161         Graph (unsigned int reserve_number_of_state,
00162                unsigned int reserve_number_edge);
00163         Graph (const self_t&);
00164         ~Graph ();
00165 
00166         self_t& operator= (const self_t&);
00167 
00168         // FIXME: add const rettype& versions?
00169 
00170         states_t          states () const;
00171         edges_t           edges () const;
00172         initial_support_t initial () const;
00173         final_support_t   final () const;
00174 
00175         // state manipulations
00176         bool              has_state (const hstate_t& h) const;
00177         hstate_t          add_state ();
00178         hstate_t          get_state (unsigned h) const;
00179         void              del_state (const hstate_t& h);
00180 
00181         void              set_initial(const hstate_t& s,
00182                                       const series_set_elt_value_t& v,
00183                                       const series_set_elt_value_t& z);
00184         const series_set_elt_value_t&
00185                           get_initial(const hstate_t&,
00186                                       const series_set_elt_value_t&) const;
00187         bool              is_initial(const hstate_t& s,
00188                                      const series_set_elt_value_t&) const;
00189         void              clear_initial();
00190 
00191         void              set_final(const hstate_t&,
00192                                     const series_set_elt_value_t&,
00193                                     const series_set_elt_value_t&);
00194         const series_set_elt_value_t&
00195                           get_final(const hstate_t&,
00196                                     const series_set_elt_value_t&) const;
00197         bool              is_final(const hstate_t& s,
00198                                    const series_set_elt_value_t&) const;
00199         void              clear_final();
00200 
00201 
00202         // edge manipulations
00203         bool              has_edge (const hedge_t& h) const;
00204         hedge_t           add_edge (const hstate_t& from,
00205                                     const hstate_t& to,
00206                                     const label_t& l);
00207         void              del_edge (const hedge_t& h);
00208 
00209         hstate_t          src_of (const hedge_t& h) const;
00210         hstate_t          dst_of (const hedge_t& h) const;
00211 
00212         const label_t&    label_of (const hedge_t& h) const;
00213         void              update(const hedge_t& h, const label_t& l);
00214 
00215         // check the consistency of an automata
00216         template <class S>
00217         bool              exists (const AutomataBase<S>& s) const;
00218 
00219         self_t&           clone () const; // TODO
00220 
00221         tag_t&            tag ();
00222         const tag_t&      tag () const;
00223         geometry_t&       geometry ();
00224         const geometry_t& geometry () const;
00225 
00226         // Helper used in deltai.
00227         // Gives the htransition held by a boost iterator.
00228         // Avoid the burden of carrying a reference to the main hash table
00229         // when we are working on a sub-hash. (this is related to the projection).
00230         template <typename I>
00231         htransition_t     get_htransition(const I& i) const;
00232 
00233       /*
00234       ** delta...
00235       ** FIXME: nice comments
00236       */
00237 # define DECLARE_DELTAC_FUNCTION(FunName, DeltaKind)                    \
00238         template <typename Container, typename Query>                   \
00239         void FunName (Container& res, const hstate_t& from,             \
00240                       const Query& q, ::vcsn::delta_kind::DeltaKind) const
00241         DECLARE_DELTAC_FUNCTION (deltac, states);
00242         DECLARE_DELTAC_FUNCTION (deltac, transitions);
00243         DECLARE_DELTAC_FUNCTION (rdeltac, states);
00244         DECLARE_DELTAC_FUNCTION (rdeltac, transitions);
00245 # undef DECLARE_DELTAC_FUNCTION
00246 
00247         // Retrieve the (src|dst)_range from a given state
00248         // Used by the delta iterators
00249 # define DECLARE_DELTAI_FUNCTION(DeltaKind)                                     \
00250         std::pair<DeltaKind##_iterator, DeltaKind##_iterator>                   \
00251         deltai(const hstate_t& s, DeltaKind##_iterator) const
00252         DECLARE_DELTAI_FUNCTION(src);
00253         DECLARE_DELTAI_FUNCTION(dst);
00254 # undef DECLARE_DELTAI_FUNCTION
00255 
00256       private:
00257         typename graph_data_t::const_iterator
00258                           find_edge(const state_t&,
00259                                     const state_t&,
00260                                     const hlabel_t&) const;
00261 
00262         geometry_t        geometry_;
00263         graph_data_t      graph_;
00264         tag_t             tag_;
00265         final_t           final_;
00266         initial_t         initial_;
00267 
00268         //NEW ATTRIBUTES
00269         boost::dynamic_bitset<>  initial_bitset_;
00270         boost::dynamic_bitset<>  final_bitset_;
00271         unsigned          number_of_epsilon_;
00272 
00273         // number_of_state_ == 0 => there is no state.
00274         unsigned          number_of_state_;
00275         states_data_t     states_;
00276 
00277         SmartLabelContainer<label_t>
00278                           label_container_;
00279 
00280     }; // End of class Graph
00281 
00282     // FIXME: add some nice comments
00283 
00284 # define BMIGRAPH_TPARAM                                                      \
00285     template <class S, class WordValue, class WeightValue, class SeriesValue, \
00286               class Letter, class Tag, class GeometryCoords>
00287 
00288 # define BMIGRAPH_SERIES                                          \
00289     Graph<labels_are_series, WordValue, WeightValue, SeriesValue, \
00290           Letter, Tag, GeometryCoords>
00291 
00292     BMIGRAPH_TPARAM
00293     ADAPT_ADD_LETTER_TRANSITION_TO_SERIES_LABEL(BMIGRAPH_SERIES);
00294 
00295     BMIGRAPH_TPARAM
00296     ADAPT_LETTER_OF_TO_SERIES_LABEL(BMIGRAPH_SERIES);
00297 
00298     BMIGRAPH_TPARAM
00299     ADAPT_WORD_OF_TO_SERIES_LABEL(BMIGRAPH_SERIES);
00300 
00301 # undef BMIGRAPH_SERIES
00302 # define BMIGRAPH_LETTERS                                       \
00303   Graph<labels_are_letters, WordValue, WeightValue, SeriesValue,\
00304         Letter, Tag, GeometryCoords>
00305 
00306     BMIGRAPH_TPARAM
00307     ADAPT_WORD_OF_TO_LETTERS_LABEL(BMIGRAPH_LETTERS);
00308 
00309     BMIGRAPH_TPARAM
00310     ADAPT_SERIE_OF_TO_LETTERS_LABEL(BMIGRAPH_LETTERS);
00311 
00312     BMIGRAPH_TPARAM
00313     ADAPT_ADD_SERIE_TRANSITION_TO_LETTERS_LABEL(BMIGRAPH_LETTERS);
00314 
00315 # undef BMIGRAPH_LETTERS
00316 
00317 # define BMIGRAPH                                               \
00318     Graph<Kind, WordValue, WeightValue, SerieValue, \
00319           Letter, Tag, GeometryCoords>
00320 
00321     template <class Kind, class WordValue, class WeightValue, class SerieValue,
00322               class Letter, class Tag, class GeometryCoords, class I>
00323     Tag& op_tag(const AutomataBase<I>&, BMIGRAPH&);
00324 
00325     template <class Kind, class WordValue, class WeightValue, class SerieValue,
00326               class Letter, class Tag, class GeometryCoords, class I>
00327     const Tag& op_tag(const AutomataBase<I>&, BMIGRAPH&);
00328 
00329     template <class Kind, class WordValue, class WeightValue, class SerieValue,
00330               class Letter, class Tag, class GeometryCoords, class I>
00331     typename BMIGRAPH::geometry_t&
00332     op_geometry(const AutomataBase<I>&, BMIGRAPH&);
00333 
00334     template <class Kind, class WordValue, class WeightValue, class SerieValue,
00335               class Letter, class Tag, class GeometryCoords, class I>
00336     const typename BMIGRAPH::geometry_t&
00337     op_geometry(const AutomataBase<I>&, const BMIGRAPH&);
00338 
00339 # undef BMIGRAPH
00340 # undef BMIGRAPH_TPARAM
00341 
00342   } // End of namespace bmig
00343 
00344   // This implementation can be used as an implementation of automaton.
00345   VCSN_MAKE_AUTOMATON_TRAITS(bmig::Graph);
00346   VCSN_MAKE_GENERALIZED_AUTOMATON_TRAITS(bmig::Graph);
00347   VCSN_MAKE_MUTE_GRAPH_IMPL_TRAITS(bmig::Graph);
00348   VCSN_MAKE_MUTE_GRAPH_IMPL_MONOID_TRAITS(bmig::Graph);
00349 
00350   // This implementation can be used as a transducer one.
00351   template <class Kind,
00352             class WordValue,
00353             class WeightValue,
00354             class SeriesValue,
00355             class Letter,
00356             class Tag,
00357             class GeometryCoords>
00358   struct transducer_traits<bmig::Graph<Kind,
00359                                   WordValue,
00360                                   WeightValue,
00361                                   SeriesValue,
00362                                   Letter,
00363                                   Tag,
00364                                   GeometryCoords> >
00365   {
00366     typedef WordValue               input_monoid_elt_value_t;
00367     typedef typename algebra::series_traits<WeightValue>::monoid_elt_value_t
00368                                   output_monoid_elt_value_t;
00369     typedef typename algebra::series_traits<WeightValue>::semiring_elt_value_t
00370                                   output_semiring_elt_value_t;
00371   };
00372 
00373   // Explain how to project type of transducer into input automaton type.
00374   template <class Kind,
00375             class WordValue,
00376             class WeightValue,
00377             class SeriesValue,
00378             class Letter,
00379             class Tag,
00380             class GeometryCoords>
00381   struct input_projection_traits<bmig::Graph<Kind,
00382                                              WordValue,
00383                                              WeightValue,
00384                                              SeriesValue,
00385                                              Letter,
00386                                              Tag,
00387                                              GeometryCoords> >
00388   {
00389     typedef bmig::Graph<Kind, WordValue, WeightValue, SeriesValue,
00390                          Letter, Tag, GeometryCoords>
00391                                   self_t;
00392     typedef typename transducer_traits<self_t>::output_semiring_elt_value_t
00393                                   semiring_elt_value_t;
00394     typedef typename transducer_traits<self_t>::input_monoid_elt_value_t
00395                                   monoid_elt_value_t;
00396     typedef typename algebra::mute_series_impl<SeriesValue,
00397                                                 semiring_elt_value_t,
00398                                                 monoid_elt_value_t>::ret
00399                                   series_set_elt_value_t;
00400 
00401     typedef
00402     bmig::Graph<Kind,
00403           monoid_elt_value_t,
00404           semiring_elt_value_t,
00405           series_set_elt_value_t,
00406           Letter,
00407           Tag,
00408           GeometryCoords>
00409                                   ret;
00410   };
00411 
00412   // Input projection for FMP transducers.
00413   template <class Kind,
00414             class WordValue,
00415             class WeightValue,
00416             class SeriesValue,
00417             class Letter,
00418             class Tag,
00419             class GeometryCoords>
00420   struct fmp_input_projection_traits<bmig::Graph<Kind,
00421                                                  WordValue,
00422                                                  WeightValue,
00423                                                  SeriesValue,
00424                                                  Letter,
00425                                                  Tag,
00426                                                  GeometryCoords> >
00427   {
00428     typedef bmig::Graph<Kind, WordValue, WeightValue, SeriesValue,
00429                          Letter, Tag, GeometryCoords>
00430                                   self_t;
00431 
00432     typedef typename automaton_traits<self_t>::semiring_elt_value_t
00433                                   semiring_elt_value_t;
00434 
00435     typedef typename WordValue::first_type monoid_elt_value_t;
00436     typedef typename monoid_elt_value_t::value_type letter_t;
00437 
00438     typedef typename algebra::mute_series_impl<SeriesValue,
00439                                                semiring_elt_value_t,
00440                                                monoid_elt_value_t>::ret
00441                                   series_set_elt_value_t;
00442 
00443     typedef
00444     bmig::Graph<Kind,
00445           monoid_elt_value_t,
00446           semiring_elt_value_t,
00447           series_set_elt_value_t,
00448           letter_t,
00449           Tag,
00450           GeometryCoords>
00451                                   ret;
00452   };
00453 
00454   template <class Kind,
00455             class WordValue,
00456             class WeightValue,
00457             class SeriesValue,
00458             class Letter,
00459             class Tag,
00460             class GeometryCoords>
00461   struct output_projection_traits<bmig::Graph<Kind,
00462                                         WordValue,
00463                                         WeightValue,
00464                                         SeriesValue,
00465                                         Letter,
00466                                         Tag,
00467                                         GeometryCoords> >
00468   {
00469     typedef bmig::Graph<Kind, WordValue, WeightValue, SeriesValue,
00470                          Letter, Tag, GeometryCoords>
00471                                   self_t;
00472 
00473     typedef typename automaton_traits<self_t>::semiring_elt_value_t
00474                                   series_set_elt_value_t;
00475 
00476     typedef typename
00477     algebra::series_traits<series_set_elt_value_t>::monoid_elt_value_t
00478                                   monoid_elt_value_t;
00479 
00480     typedef typename
00481     algebra::series_traits<series_set_elt_value_t>::semiring_elt_value_t
00482                                   semiring_elt_value_t;
00483 
00484     typedef
00485     bmig::Graph<Kind,
00486           monoid_elt_value_t,
00487           semiring_elt_value_t,
00488           series_set_elt_value_t,
00489           Letter,
00490           Tag,
00491           GeometryCoords>
00492                                   ret;
00493   };
00494 
00495   // Output projection for FMP transducers.
00496   template <class Kind,
00497             class WordValue,
00498             class WeightValue,
00499             class SeriesValue,
00500             class Letter,
00501             class Tag,
00502             class GeometryCoords>
00503   struct fmp_output_projection_traits<bmig::Graph<Kind,
00504                                         WordValue,
00505                                         WeightValue,
00506                                         SeriesValue,
00507                                         Letter,
00508                                         Tag,
00509                                         GeometryCoords> >
00510   {
00511     typedef bmig::Graph<Kind, WordValue, WeightValue, SeriesValue,
00512                          Letter, Tag, GeometryCoords>
00513                                   self_t;
00514 
00515     typedef typename WordValue::second_type monoid_elt_value_t;
00516     typedef typename monoid_elt_value_t::value_type letter_t;
00517 
00518     typedef typename automaton_traits<self_t>::semiring_elt_value_t
00519                                   semiring_elt_value_t;
00520 
00521     typedef typename algebra::mute_series_impl<SeriesValue,
00522             semiring_elt_value_t,
00523             monoid_elt_value_t>::ret series_set_elt_value_t;
00524 
00525     typedef
00526     bmig::Graph<Kind,
00527           monoid_elt_value_t,
00528           semiring_elt_value_t,
00529           series_set_elt_value_t,
00530           letter_t,
00531           Tag,
00532           GeometryCoords>
00533                                   ret;
00534   };
00535 
00536   // Explain how to extend an input automaton into a transducer.
00537   template <class Kind,
00538             class WordValue,
00539             class WeightValue,
00540             class SeriesValue,
00541             class Letter,
00542             class Tag,
00543             class GeometryCoords>
00544   struct extension_traits<bmig::Graph<Kind,
00545                                 WordValue,
00546                                 WeightValue,
00547                                 SeriesValue,
00548                                 Letter,
00549                                 Tag,
00550                                 GeometryCoords> >
00551   {
00552     typedef bmig::Graph<Kind, WordValue, WeightValue,
00553                          SeriesValue, Letter, Tag, GeometryCoords>
00554                                   self_t;
00555     typedef typename automaton_traits<self_t>::monoid_elt_value_t
00556                                   monoid_elt_value_t;
00557     typedef typename algebra::mute_series_impl<SeriesValue,
00558                                                 SeriesValue,
00559                                                 monoid_elt_value_t>::ret
00560                                   series_set_elt_value_t;
00561 
00562     typedef
00563     bmig::Graph<Kind,
00564           monoid_elt_value_t,
00565           SeriesValue,
00566           series_set_elt_value_t,
00567           Letter,
00568           Tag,
00569           GeometryCoords>
00570                                   ret;
00571   };
00572 } // End of namespace vcsn
00573 
00574 # if !defined VCSN_USE_INTERFACE_ONLY || defined VCSN_USE_LIB
00575 #  include <vaucanson/automata/implementation/bmig_graph_impl.hxx>
00576 # endif // !VCSN_USE_INTERFACE_ONLY || VCSN_USE_LIB
00577 
00578 // FIXME __ITERATOR__  put back again later
00579 //# include <vaucanson/automata/implementation/bmig_graph_letters_spec.hh>
00580 
00581 #endif // !VCSN_AUTOMATA_IMPLEMENTATION_BMIG_GRAPH_IMPL_HH_ //
00582