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