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/automata/concept/automata_base.hh>
00029 # include <vaucanson/automata/concept/transducer_base.hh>
00030 # include <vaucanson/automata/concept/automata_kind.hh>
00031 # include <vaucanson/automata/concept/tags.hh>
00032 # include <vaucanson/automata/implementation/kind_adapter.hh>
00033 # include <vaucanson/automata/implementation/geometry.hh>
00034 # include <vaucanson/automata/implementation/listg/iterator.hh>
00035 # include <vaucanson/automata/implementation/listg/listg_handlers.hh>
00036 # include <vaucanson/automata/implementation/listg/listg_sparse_interval.hh>
00037
00038 namespace vcsn
00039 {
00040 namespace listg
00041 {
00043 template <class K, class WordValue, class WeightValue,
00044 class SeriesValue, class Letter, class Tag, class GeometryCoords>
00045 class Graph
00046 {
00048 public:
00049 typedef Graph<K, WordValue, WeightValue, SeriesValue,
00050 Letter, Tag, GeometryCoords> self_t;
00051
00052 typedef WeightValue semiring_elt_value_t;
00053 typedef WordValue monoid_elt_value_t;
00054 typedef WordValue word_value_t;
00055 typedef SeriesValue series_set_elt_value_t;
00056 typedef Letter letter_t;
00057 typedef Tag tag_t;
00058
00060 typedef typename LabelOf<K, WordValue, WeightValue, SeriesValue, Letter>
00061 ::ret label_t;
00062 typedef unsigned hstate_value_t;
00063 typedef unsigned hedge_value_t;
00064 typedef handler<state_h, hstate_value_t> hstate_t;
00065 typedef handler<transition_h, hedge_value_t> htransition_t;
00066 typedef htransition_t hedge_t;
00067
00069 template<typename EdgeLabel>
00070 struct edge_value
00071 {
00072 inline edge_value(const hstate_t& h1, const hstate_t& h2,
00073 const EdgeLabel& l = EdgeLabel())
00074 : label(l),
00075 from(h1),
00076 to(h2)
00077 {}
00078
00079 inline operator const EdgeLabel& () const
00080 { return label; }
00081
00082 inline operator EdgeLabel& ()
00083 { return label; }
00084
00085 EdgeLabel label;
00086 hstate_t from;
00087 hstate_t to;
00088 };
00089
00091 struct state_value
00092 {
00093 typedef std::set<hedge_t> edges_t;
00094 inline state_value() {}
00095
00096 edges_t output_edges;
00097 edges_t input_edges;
00098 };
00099
00102 typedef misc::SparseInterval<hstate_t, std::set<hstate_t> >
00103 StateContainer;
00104 typedef misc::SparseInterval<hedge_t, std::set<hedge_t> >
00105 EdgeContainer;
00106
00107 typedef state_value state_value_t;
00108 typedef edge_value<label_t> edge_value_t;
00109
00110 typedef std::vector<state_value_t> state_data_t;
00111 typedef std::vector<edge_value_t> edge_data_t;
00112
00113 typedef StateContainer states_t;
00114 typedef EdgeContainer edges_t;
00115
00116 typedef std::map<hstate_t, series_set_elt_value_t>
00117 initial_t;
00118 typedef std::map<hstate_t, series_set_elt_value_t>
00119 final_t;
00120
00121 typedef misc::Support<initial_t> initial_support_t;
00122 typedef misc::Support<final_t> final_support_t;
00123
00124 typedef ::vcsn::listg::DeltaConstIterator<self_t, hstate_t, ::vcsn::listg::forward_iterator>
00125 delta_state_iterator;
00126 typedef ::vcsn::listg::DeltaConstIterator<self_t, htransition_t, ::vcsn::listg::forward_iterator>
00127 delta_transition_iterator;
00128
00129 typedef ::vcsn::listg::DeltaConstIterator<self_t, hstate_t, ::vcsn::listg::backward_iterator>
00130 rdelta_state_iterator;
00131 typedef ::vcsn::listg::DeltaConstIterator<self_t, htransition_t, ::vcsn::listg::backward_iterator>
00132 rdelta_transition_iterator;
00133
00134
00135 Graph();
00136 Graph(unsigned initial_number_of_state,
00137 unsigned number_of_edge_initially_allocated);
00138
00140 states_t states() const;
00141
00143 edges_t edges() const;
00144
00146 initial_support_t initial() const;
00147 final_support_t final() const;
00148
00151 hstate_t get_state(int n) const;
00152 bool has_state(const hstate_t& n) const;
00153 hstate_t add_state();
00154
00158 void del_state(const hstate_t& n);
00159
00175 void set_initial(const hstate_t& s,
00176 const series_set_elt_value_t& v,
00177 const series_set_elt_value_t& z);
00178 const series_set_elt_value_t&
00179 get_initial(const hstate_t&,
00180 const series_set_elt_value_t&) const;
00181 bool is_initial(const hstate_t& s,
00182 const series_set_elt_value_t&) const;
00183
00184 void clear_initial();
00185
00192 void set_final(const hstate_t&,
00193 const series_set_elt_value_t&,
00194 const series_set_elt_value_t&);
00195 const series_set_elt_value_t&
00196 get_final(const hstate_t&,
00197 const series_set_elt_value_t&) const;
00198 bool is_final(const hstate_t& s,
00199 const series_set_elt_value_t&) const;
00200
00201 void clear_final();
00207 bool has_edge(const hedge_t& n) const;
00208
00209 hedge_t add_edge(const hstate_t& h1,
00210 const hstate_t& h2,
00211 const label_t& v);
00212 void del_edge(const hedge_t& e);
00213
00214 hstate_t src_of(const hedge_t& e1) const;
00215 hstate_t dst_of(const hedge_t& e2) const;
00216
00217 const label_t& label_of(const hedge_t& n) const;
00218 void update(const hedge_t&, label_t);
00223 template <class S>
00224 bool exists(const AutomataBase<S>& s) const;
00225
00227 # define DECLARE_DELTA_FUNCTION(DeltaName, DKind) \
00228 template <class OutputIterator, typename Query> \
00229 void DeltaName(OutputIterator res, const hstate_t& from, \
00230 const Query& q, ::vcsn::delta_kind::DKind) const
00231 DECLARE_DELTA_FUNCTION (delta, states);
00232 DECLARE_DELTA_FUNCTION (delta, transitions);
00233 DECLARE_DELTA_FUNCTION (rdelta, states);
00234 DECLARE_DELTA_FUNCTION (rdelta, transitions);
00235 # undef DECLARE_DELTA_FUNCTION
00236
00237 # define DECLARE_DELTAF_BOOL_FUNCTION(DeltaName, DKind, IsBool) \
00238 template <class Functor, typename Query> \
00239 void DeltaName(Functor& fun, const hstate_t& from, \
00240 const Query& q, ::vcsn::delta_kind::DKind, \
00241 misc::IsBool ## _t) const
00242 DECLARE_DELTAF_BOOL_FUNCTION (deltaf, states, true);
00243 DECLARE_DELTAF_BOOL_FUNCTION (deltaf, states, false);
00244 DECLARE_DELTAF_BOOL_FUNCTION (deltaf, transitions, true);
00245 DECLARE_DELTAF_BOOL_FUNCTION (deltaf, transitions, false);
00246 DECLARE_DELTAF_BOOL_FUNCTION (rdeltaf, states, true);
00247 DECLARE_DELTAF_BOOL_FUNCTION (rdeltaf, states, false);
00248 DECLARE_DELTAF_BOOL_FUNCTION (rdeltaf, transitions, true);
00249 DECLARE_DELTAF_BOOL_FUNCTION (rdeltaf, transitions, false);
00250 # undef DECLARE_DELTAF_BOOL_FUNCTION
00251
00252 # define DECLARE_DELTAF_FUNCTION(DeltaName) \
00253 template <class Functor, typename Query, typename DKind> \
00254 void DeltaName(Functor& fun, const hstate_t& from, \
00255 const Query& q, ::vcsn::delta_kind::kind<DKind>) const
00256 DECLARE_DELTAF_FUNCTION (deltaf);
00257 DECLARE_DELTAF_FUNCTION (rdeltaf);
00258
00259 # undef DECLARE_DELTAF_FUNCTION
00260
00263
00264 self_t& clone() const;
00265
00268 tag_t& tag();
00269 const tag_t& tag() const;
00274 typedef geometry<hstate_t, hedge_t, GeometryCoords>
00275 geometry_t;
00276 geometry_t& geometry();
00277 const geometry_t& geometry() const;
00280 private:
00281 geometry_t geometry_;
00282
00283 public:
00284 state_data_t states_;
00285 edge_data_t edges_;
00286 std::set<hstate_t> removed_states_;
00287 std::set<hedge_t> removed_edges_;
00288 tag_t tag_;
00289 final_t final_;
00290 initial_t initial_;
00291 };
00292
00293
00294 # define TParam \
00295 template <class S, class WordValue, class WeightValue, class SeriesValue, \
00296 class Letter, class Tag, class GeometryCoords>
00297 # define GRAPH \
00298 Graph<Kind, WordValue, WeightValue, SerieValue, \
00299 Letter, Tag, GeometryCoords>
00300
00301
00302
00303 TParam
00304 ADAPT_ADD_LETTER_TRANSITION_TO_SERIES_LABEL(Graph<labels_are_series,
00305 WordValue, WeightValue,
00306 SeriesValue, Letter, Tag,
00307 GeometryCoords>);
00308
00309 TParam
00310 ADAPT_LETTER_OF_TO_SERIES_LABEL(Graph<labels_are_series,
00311 WordValue, WeightValue,
00312 SeriesValue, Letter, Tag,
00313 GeometryCoords>);
00314
00315 TParam
00316 ADAPT_WORD_OF_TO_SERIES_LABEL(Graph<labels_are_series,
00317 WordValue, WeightValue,
00318 SeriesValue, Letter, Tag,
00319 GeometryCoords>);
00320
00321 TParam
00322 ADAPT_WORD_OF_TO_LETTERS_LABEL(Graph<labels_are_letters,
00323 WordValue, WeightValue,
00324 SeriesValue, Letter, Tag,
00325 GeometryCoords>);
00326
00327 TParam
00328 ADAPT_SERIE_OF_TO_LETTERS_LABEL(Graph<labels_are_letters,
00329 WordValue, WeightValue,
00330 SeriesValue, Letter, Tag,
00331 GeometryCoords>);
00332
00333 TParam
00334 ADAPT_ADD_SERIE_TRANSITION_TO_LETTERS_LABEL(Graph<labels_are_letters,
00335 WordValue, WeightValue,
00336 SeriesValue, Letter, Tag,
00337 GeometryCoords>);
00338
00339 template <class Kind, class WordValue, class WeightValue, class SerieValue,
00340 class Letter, class Tag, class GeometryCoords, class I>
00341 Tag& op_tag(const AutomataBase<I>&,
00342 Graph<Kind, WordValue, WeightValue,
00343 SerieValue, Letter, Tag,
00344 GeometryCoords>&);
00345
00346 template <class Kind, class WordValue, class WeightValue, class SerieValue,
00347 class Letter, class Tag, class GeometryCoords, class I>
00348 const Tag& op_tag(const AutomataBase<I>&,
00349 const Graph<Kind, WordValue, WeightValue,
00350 SerieValue, Letter, Tag, GeometryCoords>&);
00351
00352 template <class Kind, class WordValue, class WeightValue, class SerieValue,
00353 class Letter, class Tag, class GeometryCoords, class I>
00354 typename GRAPH::geometry_t&
00355 op_geometry(const AutomataBase<I>&,
00356 Graph<Kind, WordValue, WeightValue,
00357 SerieValue, Letter, Tag, GeometryCoords>&);
00358
00359 template <class Kind, class WordValue, class WeightValue, class SerieValue,
00360 class Letter, class Tag, class GeometryCoords, class I>
00361 const typename GRAPH::geometry_t&
00362 op_geometry(const AutomataBase<I>&,
00363 const Graph<Kind, WordValue,
00364 WeightValue, SerieValue, Letter, Tag,
00365 GeometryCoords>&);
00366 # undef TParam
00367 # undef GRAPH
00368
00369 }
00370
00371
00372
00373 VCSN_MAKE_AUTOMATON_TRAITS(listg::Graph);
00374
00375
00376 template <class Kind,
00377 class WordValue,
00378 class WeightValue,
00379 class SeriesValue,
00380 class Letter,
00381 class Tag,
00382 class GeometryCoords>
00383 struct transducer_traits<listg::Graph<Kind,
00384 WordValue,
00385 WeightValue,
00386 SeriesValue,
00387 Letter,
00388 Tag,
00389 GeometryCoords> >
00390 {
00391 typedef WordValue input_monoid_elt_value_t;
00392 typedef typename algebra::series_traits<WeightValue>::monoid_elt_value_t
00393 output_monoid_elt_value_t;
00394 typedef typename algebra::series_traits<WeightValue>::semiring_elt_value_t
00395 output_semiring_elt_value_t;
00396 };
00397
00398
00399 template <class S,
00400 class Kind,
00401 class WordValue,
00402 class WeightValue,
00403 class SeriesValue,
00404 class Letter,
00405 class Tag,
00406 class GeometryCoords>
00407 struct projection_traits<S, listg::Graph<Kind,
00408 WordValue,
00409 WeightValue,
00410 SeriesValue,
00411 Letter,
00412 Tag,
00413 GeometryCoords> >
00414 {
00415 typedef listg::Graph<Kind, WordValue, WeightValue, SeriesValue,
00416 Letter, Tag, GeometryCoords>
00417 self_t;
00418 typedef typename transducer_traits<self_t>::output_semiring_elt_value_t
00419 semiring_elt_value_t;
00420 typedef typename transducer_traits<self_t>::input_monoid_elt_value_t
00421 monoid_elt_value_t;
00422 typedef typename algebra::mute_series_impl<SeriesValue,
00423 semiring_elt_value_t,
00424 monoid_elt_value_t>::ret
00425 series_set_elt_value_t;
00426
00427 typedef
00428 listg::Graph<Kind,
00429 monoid_elt_value_t,
00430 semiring_elt_value_t,
00431 series_set_elt_value_t,
00432 Letter,
00433 Tag,
00434 GeometryCoords>
00435 ret;
00436 };
00437
00438 template <class Kind,
00439 class WordValue,
00440 class WeightValue,
00441 class SeriesValue,
00442 class Letter,
00443 class Tag,
00444 class GeometryCoords>
00445 struct output_projection_traits<listg::Graph<Kind,
00446 WordValue,
00447 WeightValue,
00448 SeriesValue,
00449 Letter,
00450 Tag, GeometryCoords> >
00451 {
00452 typedef listg::Graph<Kind, WordValue, WeightValue, SeriesValue,
00453 Letter, Tag, GeometryCoords>
00454 self_t;
00455
00456 typedef typename automaton_traits<self_t>::semiring_elt_value_t
00457 series_set_elt_value_t;
00458
00459 typedef typename
00460 algebra::series_traits<series_set_elt_value_t>::monoid_elt_value_t
00461 monoid_elt_value_t;
00462
00463 typedef typename
00464 algebra::series_traits<series_set_elt_value_t>::semiring_elt_value_t
00465 semiring_elt_value_t;
00466
00467 typedef
00468 listg::Graph<Kind,
00469 monoid_elt_value_t,
00470 semiring_elt_value_t,
00471 series_set_elt_value_t,
00472 Letter,
00473 Tag,
00474 GeometryCoords>
00475 ret;
00476 };
00477
00478
00479 template <class Kind,
00480 class WordValue,
00481 class WeightValue,
00482 class SeriesValue,
00483 class Letter,
00484 class Tag,
00485 class GeometryCoords>
00486 struct extension_traits<listg::Graph<Kind,
00487 WordValue,
00488 WeightValue,
00489 SeriesValue,
00490 Letter,
00491 Tag,
00492 GeometryCoords> >
00493 {
00494 typedef listg::Graph<Kind, WordValue, WeightValue,
00495 SeriesValue, Letter, Tag, GeometryCoords>
00496 self_t;
00497 typedef typename automaton_traits<self_t>::monoid_elt_value_t
00498 monoid_elt_value_t;
00499 typedef typename algebra::mute_series_impl<SeriesValue,
00500 SeriesValue,
00501 monoid_elt_value_t>::ret
00502 series_set_elt_value_t;
00503
00504 typedef
00505 listg::Graph<Kind,
00506 monoid_elt_value_t,
00507 SeriesValue,
00508 series_set_elt_value_t,
00509 Letter,
00510 Tag,
00511 GeometryCoords>
00512 ret;
00513 };
00514 }
00515
00516
00517 # if !defined VCSN_USE_INTERFACE_ONLY || defined VCSN_USE_LIB
00518 # include <vaucanson/automata/implementation/listg_graph_impl.hxx>
00519 # endif // VCSN_USE_INTERFACE_ONLY
00520
00521 #endif // ! VCSN_AUTOMATA_IMPLEMENTATION_LISTG_GRAPH_IMPL_HH
