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_DELTA_FUNCTION(DeltaName, DKind) \
00230 template <class OutputIterator, typename Query> \
00231 void DeltaName(OutputIterator res, const hstate_t& from, \
00232 const Query& q, ::vcsn::delta_kind::DKind) const
00233 DECLARE_DELTA_FUNCTION (delta, states);
00234 DECLARE_DELTA_FUNCTION (delta, transitions);
00235 DECLARE_DELTA_FUNCTION (rdelta, states);
00236 DECLARE_DELTA_FUNCTION (rdelta, transitions);
00237 # undef DECLARE_DELTA_FUNCTION
00238
00239 # define DECLARE_DELTAF_BOOL_FUNCTION(DeltaName, DKind, IsBool) \
00240 template <class Functor, typename Query> \
00241 void DeltaName(Functor& fun, const hstate_t& from, \
00242 const Query& q, ::vcsn::delta_kind::DKind, \
00243 misc::IsBool ## _t) const
00244 DECLARE_DELTAF_BOOL_FUNCTION (deltaf, states, true);
00245 DECLARE_DELTAF_BOOL_FUNCTION (deltaf, states, false);
00246 DECLARE_DELTAF_BOOL_FUNCTION (deltaf, transitions, true);
00247 DECLARE_DELTAF_BOOL_FUNCTION (deltaf, transitions, false);
00248 DECLARE_DELTAF_BOOL_FUNCTION (rdeltaf, states, true);
00249 DECLARE_DELTAF_BOOL_FUNCTION (rdeltaf, states, false);
00250 DECLARE_DELTAF_BOOL_FUNCTION (rdeltaf, transitions, true);
00251 DECLARE_DELTAF_BOOL_FUNCTION (rdeltaf, transitions, false);
00252 # undef DECLARE_DELTAF_BOOL_FUNCTION
00253
00254 # define DECLARE_DELTAF_FUNCTION(DeltaName) \
00255 template <class Functor, typename Query, typename DKind> \
00256 void DeltaName(Functor& fun, const hstate_t& from, \
00257 const Query& q, ::vcsn::delta_kind::kind<DKind>) const
00258 DECLARE_DELTAF_FUNCTION (deltaf);
00259 DECLARE_DELTAF_FUNCTION (rdeltaf);
00260
00261 # undef DECLARE_DELTAF_FUNCTION
00262
00265
00266 self_t& clone() const;
00267
00270 tag_t& tag();
00271 const tag_t& tag() const;
00276 typedef geometry<hstate_t, hedge_t, GeometryCoords>
00277 geometry_t;
00278 geometry_t& geometry();
00279 const geometry_t& geometry() const;
00282 private:
00283 geometry_t geometry_;
00284
00285 public:
00286 state_data_t states_;
00287 edge_data_t edges_;
00288 std::set<hstate_t> removed_states_;
00289 std::set<hedge_t> removed_edges_;
00290 tag_t tag_;
00291 final_t final_;
00292 initial_t initial_;
00293 };
00294
00295
00296 # define TParam \
00297 template <class S, class WordValue, class WeightValue, class SeriesValue, \
00298 class Letter, class Tag, class GeometryCoords>
00299 # define GRAPH \
00300 Graph<Kind, WordValue, WeightValue, SerieValue, \
00301 Letter, Tag, GeometryCoords>
00302
00303
00304
00305 TParam
00306 ADAPT_ADD_LETTER_TRANSITION_TO_SERIES_LABEL(Graph<labels_are_series,
00307 WordValue, WeightValue,
00308 SeriesValue, Letter, Tag,
00309 GeometryCoords>);
00310
00311 TParam
00312 ADAPT_LETTER_OF_TO_SERIES_LABEL(Graph<labels_are_series,
00313 WordValue, WeightValue,
00314 SeriesValue, Letter, Tag,
00315 GeometryCoords>);
00316
00317 TParam
00318 ADAPT_WORD_OF_TO_SERIES_LABEL(Graph<labels_are_series,
00319 WordValue, WeightValue,
00320 SeriesValue, Letter, Tag,
00321 GeometryCoords>);
00322
00323 TParam
00324 ADAPT_WORD_OF_TO_LETTERS_LABEL(Graph<labels_are_letters,
00325 WordValue, WeightValue,
00326 SeriesValue, Letter, Tag,
00327 GeometryCoords>);
00328
00329 TParam
00330 ADAPT_SERIE_OF_TO_LETTERS_LABEL(Graph<labels_are_letters,
00331 WordValue, WeightValue,
00332 SeriesValue, Letter, Tag,
00333 GeometryCoords>);
00334
00335 TParam
00336 ADAPT_ADD_SERIE_TRANSITION_TO_LETTERS_LABEL(Graph<labels_are_letters,
00337 WordValue, WeightValue,
00338 SeriesValue, Letter, Tag,
00339 GeometryCoords>);
00340
00341 template <class Kind, class WordValue, class WeightValue, class SerieValue,
00342 class Letter, class Tag, class GeometryCoords, class I>
00343 Tag& op_tag(const AutomataBase<I>&,
00344 Graph<Kind, WordValue, WeightValue,
00345 SerieValue, Letter, Tag,
00346 GeometryCoords>&);
00347
00348 template <class Kind, class WordValue, class WeightValue, class SerieValue,
00349 class Letter, class Tag, class GeometryCoords, class I>
00350 const Tag& op_tag(const AutomataBase<I>&,
00351 const Graph<Kind, WordValue, WeightValue,
00352 SerieValue, Letter, Tag, GeometryCoords>&);
00353
00354 template <class Kind, class WordValue, class WeightValue, class SerieValue,
00355 class Letter, class Tag, class GeometryCoords, class I>
00356 typename GRAPH::geometry_t&
00357 op_geometry(const AutomataBase<I>&,
00358 Graph<Kind, WordValue, WeightValue,
00359 SerieValue, Letter, Tag, GeometryCoords>&);
00360
00361 template <class Kind, class WordValue, class WeightValue, class SerieValue,
00362 class Letter, class Tag, class GeometryCoords, class I>
00363 const typename GRAPH::geometry_t&
00364 op_geometry(const AutomataBase<I>&,
00365 const Graph<Kind, WordValue,
00366 WeightValue, SerieValue, Letter, Tag,
00367 GeometryCoords>&);
00368 # undef TParam
00369 # undef GRAPH
00370
00371 }
00372
00373
00374
00375 VCSN_MAKE_AUTOMATON_TRAITS(listg::Graph);
00376 VCSN_MAKE_GENERALIZED_AUTOMATON_TRAITS(listg::Graph);
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 transducer_traits<listg::Graph<Kind,
00387 WordValue,
00388 WeightValue,
00389 SeriesValue,
00390 Letter,
00391 Tag,
00392 GeometryCoords> >
00393 {
00394 typedef WordValue input_monoid_elt_value_t;
00395 typedef typename algebra::series_traits<WeightValue>::monoid_elt_value_t
00396 output_monoid_elt_value_t;
00397 typedef typename algebra::series_traits<WeightValue>::semiring_elt_value_t
00398 output_semiring_elt_value_t;
00399 };
00400
00401
00402 template <class Kind,
00403 class WordValue,
00404 class WeightValue,
00405 class SeriesValue,
00406 class Letter,
00407 class Tag,
00408 class GeometryCoords>
00409 struct projection_traits<listg::Graph<Kind,
00410 WordValue,
00411 WeightValue,
00412 SeriesValue,
00413 Letter,
00414 Tag,
00415 GeometryCoords> >
00416 {
00417 typedef listg::Graph<Kind, WordValue, WeightValue, SeriesValue,
00418 Letter, Tag, GeometryCoords>
00419 self_t;
00420 typedef typename transducer_traits<self_t>::output_semiring_elt_value_t
00421 semiring_elt_value_t;
00422 typedef typename transducer_traits<self_t>::input_monoid_elt_value_t
00423 monoid_elt_value_t;
00424 typedef typename algebra::mute_series_impl<SeriesValue,
00425 semiring_elt_value_t,
00426 monoid_elt_value_t>::ret
00427 series_set_elt_value_t;
00428
00429 typedef
00430 listg::Graph<Kind,
00431 monoid_elt_value_t,
00432 semiring_elt_value_t,
00433 series_set_elt_value_t,
00434 Letter,
00435 Tag,
00436 GeometryCoords>
00437 ret;
00438 };
00439
00440
00441 template <class Kind,
00442 class WordValue,
00443 class WeightValue,
00444 class SeriesValue,
00445 class Letter,
00446 class Tag,
00447 class GeometryCoords>
00448 struct fmp_projection_traits<listg::Graph<Kind,
00449 WordValue,
00450 WeightValue,
00451 SeriesValue,
00452 Letter,
00453 Tag,
00454 GeometryCoords> >
00455 {
00456 typedef listg::Graph<Kind, WordValue, WeightValue, SeriesValue,
00457 Letter, Tag, GeometryCoords>
00458 self_t;
00459
00460 typedef typename automaton_traits<self_t>::semiring_elt_value_t
00461 semiring_elt_value_t;
00462
00463 typedef typename WordValue::first_type monoid_elt_value_t;
00464 typedef typename monoid_elt_value_t::value_type letter_t;
00465
00466 typedef typename algebra::mute_series_impl<SeriesValue,
00467 semiring_elt_value_t,
00468 monoid_elt_value_t>::ret
00469 series_set_elt_value_t;
00470
00471 typedef
00472 listg::Graph<Kind,
00473 monoid_elt_value_t,
00474 semiring_elt_value_t,
00475 series_set_elt_value_t,
00476 letter_t,
00477 Tag,
00478 GeometryCoords>
00479 ret;
00480 };
00481
00482 template <class Kind,
00483 class WordValue,
00484 class WeightValue,
00485 class SeriesValue,
00486 class Letter,
00487 class Tag,
00488 class GeometryCoords>
00489 struct output_projection_traits<listg::Graph<Kind,
00490 WordValue,
00491 WeightValue,
00492 SeriesValue,
00493 Letter,
00494 Tag, GeometryCoords> >
00495 {
00496 typedef listg::Graph<Kind, WordValue, WeightValue, SeriesValue,
00497 Letter, Tag, GeometryCoords>
00498 self_t;
00499
00500 typedef typename automaton_traits<self_t>::semiring_elt_value_t
00501 series_set_elt_value_t;
00502
00503 typedef typename
00504 algebra::series_traits<series_set_elt_value_t>::monoid_elt_value_t
00505 monoid_elt_value_t;
00506
00507 typedef typename
00508 algebra::series_traits<series_set_elt_value_t>::semiring_elt_value_t
00509 semiring_elt_value_t;
00510
00511 typedef
00512 listg::Graph<Kind,
00513 monoid_elt_value_t,
00514 semiring_elt_value_t,
00515 series_set_elt_value_t,
00516 Letter,
00517 Tag,
00518 GeometryCoords>
00519 ret;
00520 };
00521
00522
00523 template <class Kind,
00524 class WordValue,
00525 class WeightValue,
00526 class SeriesValue,
00527 class Letter,
00528 class Tag,
00529 class GeometryCoords>
00530 struct fmp_output_projection_traits<listg::Graph<Kind,
00531 WordValue,
00532 WeightValue,
00533 SeriesValue,
00534 Letter,
00535 Tag,
00536 GeometryCoords> >
00537 {
00538 typedef listg::Graph<Kind, WordValue, WeightValue, SeriesValue,
00539 Letter, Tag, GeometryCoords>
00540 self_t;
00541
00542 typedef typename WordValue::second_type monoid_elt_value_t;
00543 typedef typename monoid_elt_value_t::value_type letter_t;
00544
00545 typedef typename automaton_traits<self_t>::semiring_elt_value_t
00546 semiring_elt_value_t;
00547
00548 typedef typename algebra::mute_series_impl<SeriesValue,
00549 semiring_elt_value_t,
00550 monoid_elt_value_t>::ret series_set_elt_value_t;
00551
00552 typedef
00553 listg::Graph<Kind,
00554 monoid_elt_value_t,
00555 semiring_elt_value_t,
00556 series_set_elt_value_t,
00557 letter_t,
00558 Tag,
00559 GeometryCoords>
00560 ret;
00561 };
00562
00563
00564 template <class Kind,
00565 class WordValue,
00566 class WeightValue,
00567 class SeriesValue,
00568 class Letter,
00569 class Tag,
00570 class GeometryCoords>
00571 struct extension_traits<listg::Graph<Kind,
00572 WordValue,
00573 WeightValue,
00574 SeriesValue,
00575 Letter,
00576 Tag,
00577 GeometryCoords> >
00578 {
00579 typedef listg::Graph<Kind, WordValue, WeightValue,
00580 SeriesValue, Letter, Tag, GeometryCoords>
00581 self_t;
00582 typedef typename automaton_traits<self_t>::monoid_elt_value_t
00583 monoid_elt_value_t;
00584 typedef typename algebra::mute_series_impl<SeriesValue,
00585 SeriesValue,
00586 monoid_elt_value_t>::ret
00587 series_set_elt_value_t;
00588
00589 typedef
00590 listg::Graph<Kind,
00591 monoid_elt_value_t,
00592 SeriesValue,
00593 series_set_elt_value_t,
00594 Letter,
00595 Tag,
00596 GeometryCoords>
00597 ret;
00598 };
00599 }
00600
00601
00602 # if !defined VCSN_USE_INTERFACE_ONLY || defined VCSN_USE_LIB
00603 # include <vaucanson/automata/implementation/listg_graph_impl.hxx>
00604 # endif // VCSN_USE_INTERFACE_ONLY
00605
00606 #endif // ! VCSN_AUTOMATA_IMPLEMENTATION_LISTG_GRAPH_IMPL_HH