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, hstate_t, ::vcsn::listg::forward_iterator>
00127 delta_state_iterator;
00128 typedef ::vcsn::listg::DeltaConstIterator<self_t, htransition_t, ::vcsn::listg::forward_iterator>
00129 delta_transition_iterator;
00130
00131 typedef ::vcsn::listg::DeltaConstIterator<self_t, hstate_t, ::vcsn::listg::backward_iterator>
00132 rdelta_state_iterator;
00133 typedef ::vcsn::listg::DeltaConstIterator<self_t, htransition_t, ::vcsn::listg::backward_iterator>
00134 rdelta_transition_iterator;
00135
00136
00137 Graph();
00138 Graph(unsigned initial_number_of_state,
00139 unsigned number_of_edge_initially_allocated);
00140
00142 states_t states() const;
00143
00145 edges_t edges() const;
00146
00148 initial_support_t initial() const;
00149 final_support_t final() const;
00150
00153 hstate_t get_state(int n) const;
00154 bool has_state(const hstate_t& n) const;
00155 hstate_t add_state();
00156
00160 void del_state(const hstate_t& n);
00161
00177 void set_initial(const hstate_t& s,
00178 const series_set_elt_value_t& v,
00179 const series_set_elt_value_t& z);
00180 const series_set_elt_value_t&
00181 get_initial(const hstate_t&,
00182 const series_set_elt_value_t&) const;
00183 bool is_initial(const hstate_t& s,
00184 const series_set_elt_value_t&) const;
00185
00186 void clear_initial();
00187
00194 void set_final(const hstate_t&,
00195 const series_set_elt_value_t&,
00196 const series_set_elt_value_t&);
00197 const series_set_elt_value_t&
00198 get_final(const hstate_t&,
00199 const series_set_elt_value_t&) const;
00200 bool is_final(const hstate_t& s,
00201 const series_set_elt_value_t&) const;
00202
00203 void clear_final();
00209 bool has_edge(const hedge_t& n) const;
00210
00211 hedge_t add_edge(const hstate_t& h1,
00212 const hstate_t& h2,
00213 const label_t& v);
00214 void del_edge(const hedge_t& e);
00215
00216 hstate_t src_of(const hedge_t& e1) const;
00217 hstate_t dst_of(const hedge_t& e2) const;
00218
00219 const label_t& label_of(const hedge_t& n) const;
00220 void update(const hedge_t&, label_t);
00225 template <class S>
00226 bool exists(const AutomataBase<S>& s) const;
00227
00229 # define DECLARE_DELTAC_FUNCTION(DeltaName, DKind) \
00230 template <typename Container, typename Query> \
00231 void DeltaName(Container& res, const hstate_t& from, \
00232 const Query& q, ::vcsn::delta_kind::DKind) const
00233 DECLARE_DELTAC_FUNCTION (deltac, states);
00234 DECLARE_DELTAC_FUNCTION (deltac, transitions);
00235 DECLARE_DELTAC_FUNCTION (rdeltac, states);
00236 DECLARE_DELTAC_FUNCTION (rdeltac, transitions);
00237 # undef DECLARE_DELTAC_FUNCTION
00238
00241
00242 self_t& clone() const;
00243
00246 tag_t& tag();
00247 const tag_t& tag() const;
00252 typedef vcsn::geometry<hstate_t, hedge_t, GeometryCoords>
00253 geometry_t;
00254 geometry_t& geometry();
00255 const geometry_t& geometry() const;
00258 geometry_t geometry_;
00259
00260 public:
00261 state_data_t states_;
00262 edge_data_t edges_;
00263 std::set<hstate_t> removed_states_;
00264 std::set<hedge_t> removed_edges_;
00265 tag_t tag_;
00266 final_t final_;
00267 initial_t initial_;
00268 };
00269
00270
00271 # define TParam \
00272 template <class S, class WordValue, class WeightValue, class SeriesValue, \
00273 class Letter, class Tag, class GeometryCoords>
00274 # define GRAPH \
00275 Graph<Kind, WordValue, WeightValue, SerieValue, \
00276 Letter, Tag, GeometryCoords>
00277
00278
00279
00280 TParam
00281 ADAPT_ADD_LETTER_TRANSITION_TO_SERIES_LABEL(Graph<labels_are_series,
00282 WordValue, WeightValue,
00283 SeriesValue, Letter, Tag,
00284 GeometryCoords>);
00285
00286 TParam
00287 ADAPT_LETTER_OF_TO_SERIES_LABEL(Graph<labels_are_series,
00288 WordValue, WeightValue,
00289 SeriesValue, Letter, Tag,
00290 GeometryCoords>);
00291
00292 TParam
00293 ADAPT_WORD_OF_TO_SERIES_LABEL(Graph<labels_are_series,
00294 WordValue, WeightValue,
00295 SeriesValue, Letter, Tag,
00296 GeometryCoords>);
00297
00298 TParam
00299 ADAPT_WORD_OF_TO_LETTERS_LABEL(Graph<labels_are_letters,
00300 WordValue, WeightValue,
00301 SeriesValue, Letter, Tag,
00302 GeometryCoords>);
00303
00304 TParam
00305 ADAPT_SERIE_OF_TO_LETTERS_LABEL(Graph<labels_are_letters,
00306 WordValue, WeightValue,
00307 SeriesValue, Letter, Tag,
00308 GeometryCoords>);
00309
00310 TParam
00311 ADAPT_ADD_SERIE_TRANSITION_TO_LETTERS_LABEL(Graph<labels_are_letters,
00312 WordValue, WeightValue,
00313 SeriesValue, Letter, Tag,
00314 GeometryCoords>);
00315
00316 template <class Kind, class WordValue, class WeightValue, class SerieValue,
00317 class Letter, class Tag, class GeometryCoords, class I>
00318 Tag& op_tag(const AutomataBase<I>&,
00319 Graph<Kind, WordValue, WeightValue,
00320 SerieValue, Letter, Tag,
00321 GeometryCoords>&);
00322
00323 template <class Kind, class WordValue, class WeightValue, class SerieValue,
00324 class Letter, class Tag, class GeometryCoords, class I>
00325 const Tag& op_tag(const AutomataBase<I>&,
00326 const Graph<Kind, WordValue, WeightValue,
00327 SerieValue, Letter, Tag, GeometryCoords>&);
00328
00329 template <class Kind, class WordValue, class WeightValue, class SerieValue,
00330 class Letter, class Tag, class GeometryCoords, class I>
00331 typename GRAPH::geometry_t&
00332 op_geometry(const AutomataBase<I>&,
00333 Graph<Kind, WordValue, WeightValue,
00334 SerieValue, Letter, Tag, GeometryCoords>&);
00335
00336 template <class Kind, class WordValue, class WeightValue, class SerieValue,
00337 class Letter, class Tag, class GeometryCoords, class I>
00338 const typename GRAPH::geometry_t&
00339 op_geometry(const AutomataBase<I>&,
00340 const Graph<Kind, WordValue,
00341 WeightValue, SerieValue, Letter, Tag,
00342 GeometryCoords>&);
00343 # undef TParam
00344 # undef GRAPH
00345
00346 }
00347
00348
00349
00350 VCSN_MAKE_AUTOMATON_TRAITS(listg::Graph);
00351 VCSN_MAKE_GENERALIZED_AUTOMATON_TRAITS(listg::Graph);
00352 VCSN_MAKE_MUTE_GRAPH_IMPL_TRAITS(listg::Graph);
00353 VCSN_MAKE_MUTE_GRAPH_IMPL_MONOID_TRAITS(listg::Graph);
00354
00355
00356 template <class Kind,
00357 class WordValue,
00358 class WeightValue,
00359 class SeriesValue,
00360 class Letter,
00361 class Tag,
00362 class GeometryCoords>
00363 struct transducer_traits<listg::Graph<Kind,
00364 WordValue,
00365 WeightValue,
00366 SeriesValue,
00367 Letter,
00368 Tag,
00369 GeometryCoords> >
00370 {
00371 typedef WordValue input_monoid_elt_value_t;
00372 typedef typename algebra::series_traits<WeightValue>::monoid_elt_value_t
00373 output_monoid_elt_value_t;
00374 typedef typename algebra::series_traits<WeightValue>::semiring_elt_value_t
00375 output_semiring_elt_value_t;
00376 };
00377
00378
00379 template <class Kind,
00380 class WordValue,
00381 class WeightValue,
00382 class SeriesValue,
00383 class Letter,
00384 class Tag,
00385 class GeometryCoords>
00386 struct input_projection_traits<listg::Graph<Kind,
00387 WordValue,
00388 WeightValue,
00389 SeriesValue,
00390 Letter,
00391 Tag,
00392 GeometryCoords> >
00393 {
00394 typedef listg::Graph<Kind, WordValue, WeightValue, SeriesValue,
00395 Letter, Tag, GeometryCoords>
00396 self_t;
00397 typedef typename transducer_traits<self_t>::output_semiring_elt_value_t
00398 semiring_elt_value_t;
00399 typedef typename transducer_traits<self_t>::input_monoid_elt_value_t
00400 monoid_elt_value_t;
00401 typedef typename algebra::mute_series_impl<SeriesValue,
00402 semiring_elt_value_t,
00403 monoid_elt_value_t>::ret
00404 series_set_elt_value_t;
00405
00406 typedef
00407 listg::Graph<Kind,
00408 monoid_elt_value_t,
00409 semiring_elt_value_t,
00410 series_set_elt_value_t,
00411 Letter,
00412 Tag,
00413 GeometryCoords>
00414 ret;
00415 };
00416
00417
00418 template <class Kind,
00419 class WordValue,
00420 class WeightValue,
00421 class SeriesValue,
00422 class Letter,
00423 class Tag,
00424 class GeometryCoords>
00425 struct fmp_input_projection_traits<listg::Graph<Kind,
00426 WordValue,
00427 WeightValue,
00428 SeriesValue,
00429 Letter,
00430 Tag,
00431 GeometryCoords> >
00432 {
00433 typedef listg::Graph<Kind, WordValue, WeightValue, SeriesValue,
00434 Letter, Tag, GeometryCoords>
00435 self_t;
00436
00437 typedef typename automaton_traits<self_t>::semiring_elt_value_t
00438 semiring_elt_value_t;
00439
00440 typedef typename WordValue::first_type monoid_elt_value_t;
00441 typedef typename monoid_elt_value_t::value_type letter_t;
00442
00443 typedef typename algebra::mute_series_impl<SeriesValue,
00444 semiring_elt_value_t,
00445 monoid_elt_value_t>::ret
00446 series_set_elt_value_t;
00447
00448 typedef
00449 listg::Graph<Kind,
00450 monoid_elt_value_t,
00451 semiring_elt_value_t,
00452 series_set_elt_value_t,
00453 letter_t,
00454 Tag,
00455 GeometryCoords>
00456 ret;
00457 };
00458
00459 template <class Kind,
00460 class WordValue,
00461 class WeightValue,
00462 class SeriesValue,
00463 class Letter,
00464 class Tag,
00465 class GeometryCoords>
00466 struct output_projection_traits<listg::Graph<Kind,
00467 WordValue,
00468 WeightValue,
00469 SeriesValue,
00470 Letter,
00471 Tag, GeometryCoords> >
00472 {
00473 typedef listg::Graph<Kind, WordValue, WeightValue, SeriesValue,
00474 Letter, Tag, GeometryCoords>
00475 self_t;
00476
00477 typedef typename automaton_traits<self_t>::semiring_elt_value_t
00478 series_set_elt_value_t;
00479
00480 typedef typename
00481 algebra::series_traits<series_set_elt_value_t>::monoid_elt_value_t
00482 monoid_elt_value_t;
00483
00484 typedef typename
00485 algebra::series_traits<series_set_elt_value_t>::semiring_elt_value_t
00486 semiring_elt_value_t;
00487
00488 typedef
00489 listg::Graph<Kind,
00490 monoid_elt_value_t,
00491 semiring_elt_value_t,
00492 series_set_elt_value_t,
00493 Letter,
00494 Tag,
00495 GeometryCoords>
00496 ret;
00497 };
00498
00499
00500 template <class Kind,
00501 class WordValue,
00502 class WeightValue,
00503 class SeriesValue,
00504 class Letter,
00505 class Tag,
00506 class GeometryCoords>
00507 struct fmp_output_projection_traits<listg::Graph<Kind,
00508 WordValue,
00509 WeightValue,
00510 SeriesValue,
00511 Letter,
00512 Tag,
00513 GeometryCoords> >
00514 {
00515 typedef listg::Graph<Kind, WordValue, WeightValue, SeriesValue,
00516 Letter, Tag, GeometryCoords>
00517 self_t;
00518
00519 typedef typename WordValue::second_type monoid_elt_value_t;
00520 typedef typename monoid_elt_value_t::value_type letter_t;
00521
00522 typedef typename automaton_traits<self_t>::semiring_elt_value_t
00523 semiring_elt_value_t;
00524
00525 typedef typename algebra::mute_series_impl<SeriesValue,
00526 semiring_elt_value_t,
00527 monoid_elt_value_t>::ret series_set_elt_value_t;
00528
00529 typedef
00530 listg::Graph<Kind,
00531 monoid_elt_value_t,
00532 semiring_elt_value_t,
00533 series_set_elt_value_t,
00534 letter_t,
00535 Tag,
00536 GeometryCoords>
00537 ret;
00538 };
00539
00540
00541 template <class Kind,
00542 class WordValue,
00543 class WeightValue,
00544 class SeriesValue,
00545 class Letter,
00546 class Tag,
00547 class GeometryCoords>
00548 struct extension_traits<listg::Graph<Kind,
00549 WordValue,
00550 WeightValue,
00551 SeriesValue,
00552 Letter,
00553 Tag,
00554 GeometryCoords> >
00555 {
00556 typedef listg::Graph<Kind, WordValue, WeightValue,
00557 SeriesValue, Letter, Tag, GeometryCoords>
00558 self_t;
00559 typedef typename automaton_traits<self_t>::monoid_elt_value_t
00560 monoid_elt_value_t;
00561 typedef typename algebra::mute_series_impl<SeriesValue,
00562 SeriesValue,
00563 monoid_elt_value_t>::ret
00564 series_set_elt_value_t;
00565
00566 typedef
00567 listg::Graph<Kind,
00568 monoid_elt_value_t,
00569 SeriesValue,
00570 series_set_elt_value_t,
00571 Letter,
00572 Tag,
00573 GeometryCoords>
00574 ret;
00575 };
00576 }
00577
00578
00579 # if !defined VCSN_USE_INTERFACE_ONLY || defined VCSN_USE_LIB
00580 # include <vaucanson/automata/implementation/listg_graph_impl.hxx>
00581 # endif // VCSN_USE_INTERFACE_ONLY
00582
00583 #endif // ! VCSN_AUTOMATA_IMPLEMENTATION_LISTG_GRAPH_IMPL_HH
