|
Vaucanson 1.4
|
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 typedef typename index_iterator<graph_data_t, succ>::type 00142 succ_iterator; 00143 typedef succ_iterator succ_const_iterator; 00144 typedef std::pair<succ_iterator, succ_iterator> succ_range; 00145 00146 typedef ::vcsn::bmig::DeltaConstIterator<self_t, src_iterator> 00147 delta_iterator; 00148 typedef ::vcsn::bmig::DeltaConstIterator<self_t, dst_iterator> 00149 rdelta_iterator; 00150 00151 Graph (); 00152 Graph (unsigned int reserve_number_of_state, 00153 unsigned int reserve_number_edge); 00154 Graph (const self_t&); 00155 ~Graph (); 00156 00157 self_t& operator= (const self_t&); 00158 00159 // FIXME: add const rettype& versions? 00160 00161 states_t states () const; 00162 edges_t edges () const; 00163 initial_support_t initial () const; 00164 final_support_t final () const; 00165 00166 // state manipulations 00167 bool has_state (const hstate_t& h) const; 00168 hstate_t add_state (); 00169 hstate_t get_state (unsigned h) const; 00170 void del_state (const hstate_t& h); 00171 00172 void set_initial(const hstate_t& s, 00173 const series_set_elt_value_t& v, 00174 const series_set_elt_value_t& z); 00175 const series_set_elt_value_t& 00176 get_initial(const hstate_t&, 00177 const series_set_elt_value_t&) const; 00178 bool is_initial(const hstate_t& s, 00179 const series_set_elt_value_t&) const; 00180 void clear_initial(); 00181 00182 void set_final(const hstate_t&, 00183 const series_set_elt_value_t&, 00184 const series_set_elt_value_t&); 00185 const series_set_elt_value_t& 00186 get_final(const hstate_t&, 00187 const series_set_elt_value_t&) const; 00188 bool is_final(const hstate_t& s, 00189 const series_set_elt_value_t&) const; 00190 void clear_final(); 00191 00192 00193 // edge manipulations 00194 bool has_edge (const hedge_t& h) const; 00195 hedge_t add_edge (const hstate_t& from, 00196 const hstate_t& to, 00197 const label_t& l); 00198 void del_edge (const hedge_t& h); 00199 00200 hstate_t src_of (const hedge_t& h) const; 00201 hstate_t dst_of (const hedge_t& h) const; 00202 00203 const label_t& label_of (const hedge_t& h) const; 00204 void update(const hedge_t& h, const label_t& l); 00205 00206 // check the consistency of an automata 00207 template <class S> 00208 bool exists (const AutomataBase<S>& s) const; 00209 00210 self_t& clone () const; // TODO 00211 00212 tag_t& tag (); 00213 const tag_t& tag () const; 00214 geometry_t& geometry (); 00215 const geometry_t& geometry () const; 00216 00217 // Helper used in deltai. 00218 // Gives the htransition held by a boost iterator. 00219 // Avoid the burden of carrying a reference to the main hash table 00220 // when we are working on a sub-hash. (this is related to the projection). 00221 template <typename I> 00222 htransition_t get_htransition(const I& i) const; 00223 00224 // Retrieve the (src|dst)_range from a given state 00225 // Used by the delta iterators 00226 # define DECLARE_DELTAI_FUNCTION(DeltaKind) \ 00227 std::pair<DeltaKind##_iterator, DeltaKind##_iterator> \ 00228 deltai(const hstate_t& s, DeltaKind##_iterator) const 00229 DECLARE_DELTAI_FUNCTION(src); 00230 DECLARE_DELTAI_FUNCTION(dst); 00231 # undef DECLARE_DELTAI_FUNCTION 00232 00233 private: 00234 typename graph_data_t::const_iterator 00235 find_edge(const state_t&, 00236 const state_t&, 00237 const hlabel_t&) const; 00238 00239 geometry_t geometry_; 00240 graph_data_t graph_; 00241 tag_t tag_; 00242 final_t final_; 00243 initial_t initial_; 00244 00245 //NEW ATTRIBUTES 00246 boost::dynamic_bitset<> initial_bitset_; 00247 boost::dynamic_bitset<> final_bitset_; 00248 unsigned number_of_epsilon_; 00249 00250 // number_of_state_ == 0 => there is no state. 00251 unsigned number_of_state_; 00252 states_data_t states_; 00253 00254 SmartLabelContainer<label_t> 00255 label_container_; 00256 00257 }; // End of class Graph 00258 00259 // FIXME: add some nice comments 00260 00261 # define BMIGRAPH_TPARAM \ 00262 template <class S, class WordValue, class WeightValue, class SeriesValue, \ 00263 class Letter, class Tag, class GeometryCoords> 00264 00265 # define BMIGRAPH_SERIES \ 00266 Graph<labels_are_series, WordValue, WeightValue, SeriesValue, \ 00267 Letter, Tag, GeometryCoords> 00268 00269 BMIGRAPH_TPARAM 00270 ADAPT_ADD_LETTER_TRANSITION_TO_SERIES_LABEL(BMIGRAPH_SERIES); 00271 00272 BMIGRAPH_TPARAM 00273 ADAPT_LETTER_OF_TO_SERIES_LABEL(BMIGRAPH_SERIES); 00274 00275 BMIGRAPH_TPARAM 00276 ADAPT_WORD_OF_TO_SERIES_LABEL(BMIGRAPH_SERIES); 00277 00278 # undef BMIGRAPH_SERIES 00279 # define BMIGRAPH_LETTERS \ 00280 Graph<labels_are_letters, WordValue, WeightValue, SeriesValue,\ 00281 Letter, Tag, GeometryCoords> 00282 00283 BMIGRAPH_TPARAM 00284 ADAPT_WORD_OF_TO_LETTERS_LABEL(BMIGRAPH_LETTERS); 00285 00286 BMIGRAPH_TPARAM 00287 ADAPT_SERIE_OF_TO_LETTERS_LABEL(BMIGRAPH_LETTERS); 00288 00289 BMIGRAPH_TPARAM 00290 ADAPT_ADD_SERIE_TRANSITION_TO_LETTERS_LABEL(BMIGRAPH_LETTERS); 00291 00292 # undef BMIGRAPH_LETTERS 00293 00294 # define BMIGRAPH \ 00295 Graph<Kind, WordValue, WeightValue, SerieValue, \ 00296 Letter, Tag, GeometryCoords> 00297 00298 template <class Kind, class WordValue, class WeightValue, class SerieValue, 00299 class Letter, class Tag, class GeometryCoords, class I> 00300 Tag& op_tag(const AutomataBase<I>&, BMIGRAPH&); 00301 00302 template <class Kind, class WordValue, class WeightValue, class SerieValue, 00303 class Letter, class Tag, class GeometryCoords, class I> 00304 const Tag& op_tag(const AutomataBase<I>&, BMIGRAPH&); 00305 00306 template <class Kind, class WordValue, class WeightValue, class SerieValue, 00307 class Letter, class Tag, class GeometryCoords, class I> 00308 typename BMIGRAPH::geometry_t& 00309 op_geometry(const AutomataBase<I>&, BMIGRAPH&); 00310 00311 template <class Kind, class WordValue, class WeightValue, class SerieValue, 00312 class Letter, class Tag, class GeometryCoords, class I> 00313 const typename BMIGRAPH::geometry_t& 00314 op_geometry(const AutomataBase<I>&, const BMIGRAPH&); 00315 00316 # undef BMIGRAPH 00317 # undef BMIGRAPH_TPARAM 00318 00319 } // End of namespace bmig 00320 00321 // This implementation can be used as an implementation of automaton. 00322 VCSN_MAKE_AUTOMATON_TRAITS(bmig::Graph); 00323 VCSN_MAKE_GENERALIZED_AUTOMATON_TRAITS(bmig::Graph); 00324 VCSN_MAKE_MUTE_GRAPH_IMPL_TRAITS(bmig::Graph); 00325 VCSN_MAKE_MUTE_GRAPH_IMPL_MONOID_TRAITS(bmig::Graph); 00326 00327 // This implementation can be used as a transducer one. 00328 template <class Kind, 00329 class WordValue, 00330 class WeightValue, 00331 class SeriesValue, 00332 class Letter, 00333 class Tag, 00334 class GeometryCoords> 00335 struct transducer_traits<bmig::Graph<Kind, 00336 WordValue, 00337 WeightValue, 00338 SeriesValue, 00339 Letter, 00340 Tag, 00341 GeometryCoords> > 00342 { 00343 typedef WordValue input_monoid_elt_value_t; 00344 typedef typename algebra::series_traits<WeightValue>::monoid_elt_value_t 00345 output_monoid_elt_value_t; 00346 typedef typename algebra::series_traits<WeightValue>::semiring_elt_value_t 00347 output_semiring_elt_value_t; 00348 }; 00349 00350 // Explain how to project type of transducer into input automaton type. 00351 template <class Kind, 00352 class WordValue, 00353 class WeightValue, 00354 class SeriesValue, 00355 class Letter, 00356 class Tag, 00357 class GeometryCoords> 00358 struct input_projection_traits<bmig::Graph<Kind, 00359 WordValue, 00360 WeightValue, 00361 SeriesValue, 00362 Letter, 00363 Tag, 00364 GeometryCoords> > 00365 { 00366 typedef bmig::Graph<Kind, WordValue, WeightValue, SeriesValue, 00367 Letter, Tag, GeometryCoords> 00368 self_t; 00369 typedef typename transducer_traits<self_t>::output_semiring_elt_value_t 00370 semiring_elt_value_t; 00371 typedef typename transducer_traits<self_t>::input_monoid_elt_value_t 00372 monoid_elt_value_t; 00373 typedef typename algebra::mute_series_impl<SeriesValue, 00374 semiring_elt_value_t, 00375 monoid_elt_value_t>::ret 00376 series_set_elt_value_t; 00377 00378 typedef 00379 bmig::Graph<Kind, 00380 monoid_elt_value_t, 00381 semiring_elt_value_t, 00382 series_set_elt_value_t, 00383 Letter, 00384 Tag, 00385 GeometryCoords> 00386 ret; 00387 }; 00388 00389 // Input projection for FMP transducers. 00390 template <class Kind, 00391 class WordValue, 00392 class WeightValue, 00393 class SeriesValue, 00394 class Letter, 00395 class Tag, 00396 class GeometryCoords> 00397 struct fmp_input_projection_traits<bmig::Graph<Kind, 00398 WordValue, 00399 WeightValue, 00400 SeriesValue, 00401 Letter, 00402 Tag, 00403 GeometryCoords> > 00404 { 00405 typedef bmig::Graph<Kind, WordValue, WeightValue, SeriesValue, 00406 Letter, Tag, GeometryCoords> 00407 self_t; 00408 00409 typedef typename automaton_traits<self_t>::semiring_elt_value_t 00410 semiring_elt_value_t; 00411 00412 typedef typename WordValue::first_type monoid_elt_value_t; 00413 typedef typename monoid_elt_value_t::value_type letter_t; 00414 00415 typedef typename algebra::mute_series_impl<SeriesValue, 00416 semiring_elt_value_t, 00417 monoid_elt_value_t>::ret 00418 series_set_elt_value_t; 00419 00420 typedef 00421 bmig::Graph<Kind, 00422 monoid_elt_value_t, 00423 semiring_elt_value_t, 00424 series_set_elt_value_t, 00425 letter_t, 00426 Tag, 00427 GeometryCoords> 00428 ret; 00429 }; 00430 00431 template <class Kind, 00432 class WordValue, 00433 class WeightValue, 00434 class SeriesValue, 00435 class Letter, 00436 class Tag, 00437 class GeometryCoords> 00438 struct output_projection_traits<bmig::Graph<Kind, 00439 WordValue, 00440 WeightValue, 00441 SeriesValue, 00442 Letter, 00443 Tag, 00444 GeometryCoords> > 00445 { 00446 typedef bmig::Graph<Kind, WordValue, WeightValue, SeriesValue, 00447 Letter, Tag, GeometryCoords> 00448 self_t; 00449 00450 typedef typename automaton_traits<self_t>::semiring_elt_value_t 00451 series_set_elt_value_t; 00452 00453 typedef typename 00454 algebra::series_traits<series_set_elt_value_t>::monoid_elt_value_t 00455 monoid_elt_value_t; 00456 00457 typedef typename 00458 algebra::series_traits<series_set_elt_value_t>::semiring_elt_value_t 00459 semiring_elt_value_t; 00460 00461 typedef 00462 bmig::Graph<Kind, 00463 monoid_elt_value_t, 00464 semiring_elt_value_t, 00465 series_set_elt_value_t, 00466 Letter, 00467 Tag, 00468 GeometryCoords> 00469 ret; 00470 }; 00471 00472 // Output projection for FMP transducers. 00473 template <class Kind, 00474 class WordValue, 00475 class WeightValue, 00476 class SeriesValue, 00477 class Letter, 00478 class Tag, 00479 class GeometryCoords> 00480 struct fmp_output_projection_traits<bmig::Graph<Kind, 00481 WordValue, 00482 WeightValue, 00483 SeriesValue, 00484 Letter, 00485 Tag, 00486 GeometryCoords> > 00487 { 00488 typedef bmig::Graph<Kind, WordValue, WeightValue, SeriesValue, 00489 Letter, Tag, GeometryCoords> 00490 self_t; 00491 00492 typedef typename WordValue::second_type monoid_elt_value_t; 00493 typedef typename monoid_elt_value_t::value_type letter_t; 00494 00495 typedef typename automaton_traits<self_t>::semiring_elt_value_t 00496 semiring_elt_value_t; 00497 00498 typedef typename algebra::mute_series_impl<SeriesValue, 00499 semiring_elt_value_t, 00500 monoid_elt_value_t>::ret series_set_elt_value_t; 00501 00502 typedef 00503 bmig::Graph<Kind, 00504 monoid_elt_value_t, 00505 semiring_elt_value_t, 00506 series_set_elt_value_t, 00507 letter_t, 00508 Tag, 00509 GeometryCoords> 00510 ret; 00511 }; 00512 00513 // Explain how to extend an input automaton into a transducer. 00514 template <class Kind, 00515 class WordValue, 00516 class WeightValue, 00517 class SeriesValue, 00518 class Letter, 00519 class Tag, 00520 class GeometryCoords> 00521 struct extension_traits<bmig::Graph<Kind, 00522 WordValue, 00523 WeightValue, 00524 SeriesValue, 00525 Letter, 00526 Tag, 00527 GeometryCoords> > 00528 { 00529 typedef bmig::Graph<Kind, WordValue, WeightValue, 00530 SeriesValue, Letter, Tag, GeometryCoords> 00531 self_t; 00532 typedef typename automaton_traits<self_t>::monoid_elt_value_t 00533 monoid_elt_value_t; 00534 typedef typename algebra::mute_series_impl<SeriesValue, 00535 SeriesValue, 00536 monoid_elt_value_t>::ret 00537 series_set_elt_value_t; 00538 00539 typedef 00540 bmig::Graph<Kind, 00541 monoid_elt_value_t, 00542 SeriesValue, 00543 series_set_elt_value_t, 00544 Letter, 00545 Tag, 00546 GeometryCoords> 00547 ret; 00548 }; 00549 } // End of namespace vcsn 00550 00551 # if !defined VCSN_USE_INTERFACE_ONLY || defined VCSN_USE_LIB 00552 # include <vaucanson/automata/implementation/bmig_graph_impl.hxx> 00553 # endif // !VCSN_USE_INTERFACE_ONLY || VCSN_USE_LIB 00554 00555 // FIXME __ITERATOR__ put back again later 00556 //# include <vaucanson/automata/implementation/bmig_graph_letters_spec.hh> 00557 00558 #endif // !VCSN_AUTOMATA_IMPLEMENTATION_BMIG_GRAPH_IMPL_HH_ // 00559
1.7.4