|
Vaucanson 1.4
|
00001 // listg_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) 2005, 2006, 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 #ifndef VCSN_AUTOMATA_IMPLEMENTATION_LISTG_GRAPH_IMPL_HH 00018 # define VCSN_AUTOMATA_IMPLEMENTATION_LISTG_GRAPH_IMPL_HH 00019 00020 # include <set> 00021 # include <map> 00022 # include <vector> 00023 00024 # include <vaucanson/misc/static.hh> 00025 # include <vaucanson/misc/usual_macros.hh> 00026 00027 # include <vaucanson/misc/support.hh> 00028 # include <vaucanson/algebra/implementation/series/rat/exp.hh> 00029 # include <vaucanson/automata/concept/automata_base.hh> 00030 # include <vaucanson/automata/concept/automata.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 # include <vaucanson/automata/implementation/listg/iterator.hh> 00037 # include <vaucanson/automata/implementation/listg/listg_handlers.hh> 00038 # include <vaucanson/automata/implementation/listg/listg_sparse_interval.hh> 00039 00040 namespace vcsn 00041 { 00042 namespace listg 00043 { 00045 template <class K, class WordValue, class WeightValue, 00046 class SeriesValue, class Letter, class Tag, class GeometryCoords> 00047 class Graph 00048 { 00050 public: 00051 typedef Graph<K, WordValue, WeightValue, SeriesValue, 00052 Letter, Tag, GeometryCoords> self_t; 00053 00054 typedef WeightValue semiring_elt_value_t; 00055 typedef WordValue monoid_elt_value_t; 00056 typedef WordValue word_value_t; 00057 typedef SeriesValue series_set_elt_value_t; 00058 typedef Letter letter_t; 00059 typedef Tag tag_t; 00060 00062 typedef typename LabelOf<K, WordValue, WeightValue, SeriesValue, Letter> 00063 ::ret label_t; 00064 typedef unsigned hstate_value_t; 00065 typedef unsigned hedge_value_t; 00066 typedef handler<state_h, hstate_value_t> hstate_t; 00067 typedef handler<transition_h, hedge_value_t> htransition_t; 00068 typedef htransition_t hedge_t; 00069 00071 template<typename EdgeLabel> 00072 struct edge_value 00073 { 00074 inline edge_value(const hstate_t& h1, const hstate_t& h2, 00075 const EdgeLabel& l = EdgeLabel()) 00076 : label(l), 00077 from(h1), 00078 to(h2) 00079 {} 00080 00081 inline operator const EdgeLabel& () const 00082 { return label; } 00083 00084 inline operator EdgeLabel& () 00085 { return label; } 00086 00087 EdgeLabel label; 00088 hstate_t from; 00089 hstate_t to; 00090 }; 00091 00093 struct state_value 00094 { 00095 typedef std::set<hedge_t> edges_t; 00096 inline state_value() {} 00097 00098 edges_t output_edges; 00099 edges_t input_edges; 00100 }; 00101 00104 typedef misc::SparseInterval<hstate_t, std::set<hstate_t> > 00105 StateContainer; 00106 typedef misc::SparseInterval<hedge_t, std::set<hedge_t> > 00107 EdgeContainer; 00108 00109 typedef state_value state_value_t; 00110 typedef edge_value<label_t> edge_value_t; 00111 00112 typedef std::vector<state_value_t> state_data_t; 00113 typedef std::vector<edge_value_t> edge_data_t; 00114 00115 typedef StateContainer states_t; 00116 typedef EdgeContainer edges_t; 00117 00118 typedef std::map<hstate_t, series_set_elt_value_t> 00119 initial_t; 00120 typedef std::map<hstate_t, series_set_elt_value_t> 00121 final_t; 00122 00123 typedef misc::Support<initial_t> initial_support_t; 00124 typedef misc::Support<final_t> final_support_t; 00125 00126 typedef ::vcsn::listg::DeltaConstIterator<self_t, ::vcsn::listg::forward_iterator> 00127 delta_iterator; 00128 00129 typedef ::vcsn::listg::DeltaConstIterator<self_t, ::vcsn::listg::backward_iterator> 00130 rdelta_iterator; 00131 // we guarantee that the handlers of state are indexed from 0 to 00132 // initial_number_of_state - 1 when using this constructor. 00133 Graph(); 00134 Graph(unsigned initial_number_of_state, 00135 unsigned number_of_edge_initially_allocated); 00136 00138 states_t states() const; 00139 00141 edges_t edges() const; 00142 00144 initial_support_t initial() const; 00145 final_support_t final() const; 00146 00149 hstate_t get_state(int n) const; 00150 bool has_state(const hstate_t& n) const; 00151 hstate_t add_state(); 00152 00156 void del_state(const hstate_t& n); 00157 00173 void set_initial(const hstate_t& s, 00174 const series_set_elt_value_t& v, 00175 const series_set_elt_value_t& z); 00176 const series_set_elt_value_t& 00177 get_initial(const hstate_t&, 00178 const series_set_elt_value_t&) const; 00179 bool is_initial(const hstate_t& s, 00180 const series_set_elt_value_t&) const; 00181 00182 void clear_initial(); 00183 00190 void set_final(const hstate_t&, 00191 const series_set_elt_value_t&, 00192 const series_set_elt_value_t&); 00193 const series_set_elt_value_t& 00194 get_final(const hstate_t&, 00195 const series_set_elt_value_t&) const; 00196 bool is_final(const hstate_t& s, 00197 const series_set_elt_value_t&) const; 00198 00199 void clear_final(); 00205 bool has_edge(const hedge_t& n) const; 00206 00207 hedge_t add_edge(const hstate_t& h1, 00208 const hstate_t& h2, 00209 const label_t& v); 00210 void del_edge(const hedge_t& e); 00211 00212 hstate_t src_of(const hedge_t& e1) const; 00213 hstate_t dst_of(const hedge_t& e2) const; 00214 00215 const label_t& label_of(const hedge_t& n) const; 00216 void update(const hedge_t&, label_t); 00221 template <class S> 00222 bool exists(const AutomataBase<S>& s) const; 00223 00226 00227 self_t& clone() const; 00228 00231 tag_t& tag(); 00232 const tag_t& tag() const; 00237 typedef vcsn::geometry<hstate_t, hedge_t, GeometryCoords> 00238 geometry_t; 00239 geometry_t& geometry(); 00240 const geometry_t& geometry() const; 00243 geometry_t geometry_; 00244 00245 public: 00246 state_data_t states_; 00247 edge_data_t edges_; 00248 std::set<hstate_t> removed_states_; 00249 std::set<hedge_t> removed_edges_; 00250 tag_t tag_; 00251 final_t final_; 00252 initial_t initial_; 00253 }; 00254 00255 00256 # define TParam \ 00257 template <class S, class WordValue, class WeightValue, class SeriesValue, \ 00258 class Letter, class Tag, class GeometryCoords> 00259 # define GRAPH \ 00260 Graph<Kind, WordValue, WeightValue, SerieValue, \ 00261 Letter, Tag, GeometryCoords> 00262 00263 00264 00265 TParam 00266 ADAPT_ADD_LETTER_TRANSITION_TO_SERIES_LABEL(Graph<labels_are_series, 00267 WordValue, WeightValue, 00268 SeriesValue, Letter, Tag, 00269 GeometryCoords>); 00270 00271 TParam 00272 ADAPT_LETTER_OF_TO_SERIES_LABEL(Graph<labels_are_series, 00273 WordValue, WeightValue, 00274 SeriesValue, Letter, Tag, 00275 GeometryCoords>); 00276 00277 TParam 00278 ADAPT_WORD_OF_TO_SERIES_LABEL(Graph<labels_are_series, 00279 WordValue, WeightValue, 00280 SeriesValue, Letter, Tag, 00281 GeometryCoords>); 00282 00283 TParam 00284 ADAPT_WORD_OF_TO_LETTERS_LABEL(Graph<labels_are_letters, 00285 WordValue, WeightValue, 00286 SeriesValue, Letter, Tag, 00287 GeometryCoords>); 00288 00289 TParam 00290 ADAPT_SERIE_OF_TO_LETTERS_LABEL(Graph<labels_are_letters, 00291 WordValue, WeightValue, 00292 SeriesValue, Letter, Tag, 00293 GeometryCoords>); 00294 00295 TParam 00296 ADAPT_ADD_SERIE_TRANSITION_TO_LETTERS_LABEL(Graph<labels_are_letters, 00297 WordValue, WeightValue, 00298 SeriesValue, Letter, Tag, 00299 GeometryCoords>); 00300 00301 template <class Kind, class WordValue, class WeightValue, class SerieValue, 00302 class Letter, class Tag, class GeometryCoords, class I> 00303 Tag& op_tag(const AutomataBase<I>&, 00304 Graph<Kind, WordValue, WeightValue, 00305 SerieValue, Letter, Tag, 00306 GeometryCoords>&); 00307 00308 template <class Kind, class WordValue, class WeightValue, class SerieValue, 00309 class Letter, class Tag, class GeometryCoords, class I> 00310 const Tag& op_tag(const AutomataBase<I>&, 00311 const Graph<Kind, WordValue, WeightValue, 00312 SerieValue, Letter, Tag, GeometryCoords>&); 00313 00314 template <class Kind, class WordValue, class WeightValue, class SerieValue, 00315 class Letter, class Tag, class GeometryCoords, class I> 00316 typename GRAPH::geometry_t& 00317 op_geometry(const AutomataBase<I>&, 00318 Graph<Kind, WordValue, WeightValue, 00319 SerieValue, Letter, Tag, GeometryCoords>&); 00320 00321 template <class Kind, class WordValue, class WeightValue, class SerieValue, 00322 class Letter, class Tag, class GeometryCoords, class I> 00323 const typename GRAPH::geometry_t& 00324 op_geometry(const AutomataBase<I>&, 00325 const Graph<Kind, WordValue, 00326 WeightValue, SerieValue, Letter, Tag, 00327 GeometryCoords>&); 00328 # undef TParam 00329 # undef GRAPH 00330 00331 } // End of namespace listg 00332 00333 00334 // This implementation can be used as an implementation of automaton. 00335 VCSN_MAKE_AUTOMATON_TRAITS(listg::Graph); 00336 VCSN_MAKE_GENERALIZED_AUTOMATON_TRAITS(listg::Graph); 00337 VCSN_MAKE_MUTE_GRAPH_IMPL_TRAITS(listg::Graph); 00338 VCSN_MAKE_MUTE_GRAPH_IMPL_MONOID_TRAITS(listg::Graph); 00339 00340 // This implementation can be used as a transducer one. 00341 template <class Kind, 00342 class WordValue, 00343 class WeightValue, 00344 class SeriesValue, 00345 class Letter, 00346 class Tag, 00347 class GeometryCoords> 00348 struct transducer_traits<listg::Graph<Kind, 00349 WordValue, 00350 WeightValue, 00351 SeriesValue, 00352 Letter, 00353 Tag, 00354 GeometryCoords> > 00355 { 00356 typedef WordValue input_monoid_elt_value_t; 00357 typedef typename algebra::series_traits<WeightValue>::monoid_elt_value_t 00358 output_monoid_elt_value_t; 00359 typedef typename algebra::series_traits<WeightValue>::semiring_elt_value_t 00360 output_semiring_elt_value_t; 00361 }; 00362 00363 // Explain how to project type of transducer into input automaton type. 00364 template <class Kind, 00365 class WordValue, 00366 class WeightValue, 00367 class SeriesValue, 00368 class Letter, 00369 class Tag, 00370 class GeometryCoords> 00371 struct input_projection_traits<listg::Graph<Kind, 00372 WordValue, 00373 WeightValue, 00374 SeriesValue, 00375 Letter, 00376 Tag, 00377 GeometryCoords> > 00378 { 00379 typedef listg::Graph<Kind, WordValue, WeightValue, SeriesValue, 00380 Letter, Tag, GeometryCoords> 00381 self_t; 00382 typedef typename transducer_traits<self_t>::output_semiring_elt_value_t 00383 semiring_elt_value_t; 00384 typedef typename transducer_traits<self_t>::input_monoid_elt_value_t 00385 monoid_elt_value_t; 00386 typedef typename algebra::mute_series_impl<SeriesValue, 00387 semiring_elt_value_t, 00388 monoid_elt_value_t>::ret 00389 series_set_elt_value_t; 00390 00391 typedef 00392 listg::Graph<Kind, 00393 monoid_elt_value_t, 00394 semiring_elt_value_t, 00395 series_set_elt_value_t, 00396 Letter, 00397 Tag, 00398 GeometryCoords> 00399 ret; 00400 }; 00401 00402 // Input projection for FMP transducers. 00403 template <class Kind, 00404 class WordValue, 00405 class WeightValue, 00406 class SeriesValue, 00407 class Letter, 00408 class Tag, 00409 class GeometryCoords> 00410 struct fmp_input_projection_traits<listg::Graph<Kind, 00411 WordValue, 00412 WeightValue, 00413 SeriesValue, 00414 Letter, 00415 Tag, 00416 GeometryCoords> > 00417 { 00418 typedef listg::Graph<Kind, WordValue, WeightValue, SeriesValue, 00419 Letter, Tag, GeometryCoords> 00420 self_t; 00421 00422 typedef typename automaton_traits<self_t>::semiring_elt_value_t 00423 semiring_elt_value_t; 00424 00425 typedef typename WordValue::first_type monoid_elt_value_t; 00426 typedef typename monoid_elt_value_t::value_type letter_t; 00427 00428 typedef typename algebra::mute_series_impl<SeriesValue, 00429 semiring_elt_value_t, 00430 monoid_elt_value_t>::ret 00431 series_set_elt_value_t; 00432 00433 typedef 00434 listg::Graph<Kind, 00435 monoid_elt_value_t, 00436 semiring_elt_value_t, 00437 series_set_elt_value_t, 00438 letter_t, 00439 Tag, 00440 GeometryCoords> 00441 ret; 00442 }; 00443 00444 template <class Kind, 00445 class WordValue, 00446 class WeightValue, 00447 class SeriesValue, 00448 class Letter, 00449 class Tag, 00450 class GeometryCoords> 00451 struct output_projection_traits<listg::Graph<Kind, 00452 WordValue, 00453 WeightValue, 00454 SeriesValue, 00455 Letter, 00456 Tag, GeometryCoords> > 00457 { 00458 typedef listg::Graph<Kind, WordValue, WeightValue, SeriesValue, 00459 Letter, Tag, GeometryCoords> 00460 self_t; 00461 00462 typedef typename automaton_traits<self_t>::semiring_elt_value_t 00463 series_set_elt_value_t; 00464 00465 typedef typename 00466 algebra::series_traits<series_set_elt_value_t>::monoid_elt_value_t 00467 monoid_elt_value_t; 00468 00469 typedef typename 00470 algebra::series_traits<series_set_elt_value_t>::semiring_elt_value_t 00471 semiring_elt_value_t; 00472 00473 typedef 00474 listg::Graph<Kind, 00475 monoid_elt_value_t, 00476 semiring_elt_value_t, 00477 series_set_elt_value_t, 00478 Letter, 00479 Tag, 00480 GeometryCoords> 00481 ret; 00482 }; 00483 00484 // Output projection for FMP transducers. 00485 template <class Kind, 00486 class WordValue, 00487 class WeightValue, 00488 class SeriesValue, 00489 class Letter, 00490 class Tag, 00491 class GeometryCoords> 00492 struct fmp_output_projection_traits<listg::Graph<Kind, 00493 WordValue, 00494 WeightValue, 00495 SeriesValue, 00496 Letter, 00497 Tag, 00498 GeometryCoords> > 00499 { 00500 typedef listg::Graph<Kind, WordValue, WeightValue, SeriesValue, 00501 Letter, Tag, GeometryCoords> 00502 self_t; 00503 00504 typedef typename WordValue::second_type monoid_elt_value_t; 00505 typedef typename monoid_elt_value_t::value_type letter_t; 00506 00507 typedef typename automaton_traits<self_t>::semiring_elt_value_t 00508 semiring_elt_value_t; 00509 00510 typedef typename algebra::mute_series_impl<SeriesValue, 00511 semiring_elt_value_t, 00512 monoid_elt_value_t>::ret series_set_elt_value_t; 00513 00514 typedef 00515 listg::Graph<Kind, 00516 monoid_elt_value_t, 00517 semiring_elt_value_t, 00518 series_set_elt_value_t, 00519 letter_t, 00520 Tag, 00521 GeometryCoords> 00522 ret; 00523 }; 00524 00525 // Explain how to extend an input automaton into a transducer. 00526 template <class Kind, 00527 class WordValue, 00528 class WeightValue, 00529 class SeriesValue, 00530 class Letter, 00531 class Tag, 00532 class GeometryCoords> 00533 struct extension_traits<listg::Graph<Kind, 00534 WordValue, 00535 WeightValue, 00536 SeriesValue, 00537 Letter, 00538 Tag, 00539 GeometryCoords> > 00540 { 00541 typedef listg::Graph<Kind, WordValue, WeightValue, 00542 SeriesValue, Letter, Tag, GeometryCoords> 00543 self_t; 00544 typedef typename automaton_traits<self_t>::monoid_elt_value_t 00545 monoid_elt_value_t; 00546 typedef typename algebra::mute_series_impl<SeriesValue, 00547 SeriesValue, 00548 monoid_elt_value_t>::ret 00549 series_set_elt_value_t; 00550 00551 typedef 00552 listg::Graph<Kind, 00553 monoid_elt_value_t, 00554 SeriesValue, 00555 series_set_elt_value_t, 00556 Letter, 00557 Tag, 00558 GeometryCoords> 00559 ret; 00560 }; 00561 } // Enf of namespace vcsn 00562 00563 00564 # if !defined VCSN_USE_INTERFACE_ONLY || defined VCSN_USE_LIB 00565 # include <vaucanson/automata/implementation/listg_graph_impl.hxx> 00566 # endif // VCSN_USE_INTERFACE_ONLY 00567 00568 #endif // ! VCSN_AUTOMATA_IMPLEMENTATION_LISTG_GRAPH_IMPL_HH
1.7.4