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