00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
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
00132
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 }
00332
00333
00334
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
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
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
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
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
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 }
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
