graph.hxx

00001 // graph.hxx: this file is part of the Vaucanson project.
00002 //
00003 // Vaucanson, a generic library for finite state machines.
00004 //
00005 // Copyright (C) 2005, 2006, 2007 The Vaucanson Group.
00006 //
00007 // This program is free software; you can redistribute it and/or
00008 // modify it under the terms of the GNU General Public License
00009 // as published by the Free Software Foundation; either version 2
00010 // of the License, or (at your option) any later version.
00011 //
00012 // The complete GNU General Public Licence Notice can be found as the
00013 // `COPYING' file in the root directory.
00014 //
00015 // The Vaucanson Group consists of people listed in the `AUTHORS' file.
00016 //
00017 #ifndef VCSN_AUTOMATA_IMPLEMENTATION_GRAPH_HXX
00018 # define VCSN_AUTOMATA_IMPLEMENTATION_GRAPH_HXX
00019 
00020 # include <fstream>
00021 # include <sstream>
00022 
00023 # include <algorithm>
00024 # include <utility>
00025 
00026 # include <vaucanson/automata/implementation/graph.hh>
00027 # include <vaucanson/misc/contract.hh>
00028 # include <vaucanson/misc/static.hh>
00029 
00030 namespace vcsn
00031 {
00032 
00033   /*---------------------------.
00034   | Decorators' implementation |
00035   `---------------------------*/
00036 
00037   template<typename EdgeLabel>
00038   edge_value<EdgeLabel>::edge_value(hstate_t h1, hstate_t h2,
00039                                     const EdgeLabel& l)
00040     : label(l),
00041       from(h1),
00042       to(h2)
00043   {}
00044 
00045   inline
00046   state_value::state_value()
00047   {}
00048 
00049 
00050   /*--------------------.
00051   | Convenient macros.  |
00052   `--------------------*/
00053 
00054 # define TParam                                                         \
00055   template <class Kind, class WordValue, class WeightValue,             \
00056             class SeriesValue, class Letter, class Tag, class Geometry>
00057 
00058 # define GClass                                                         \
00059   Graph<Kind, WordValue, WeightValue, SeriesValue, Letter, Tag, Geometry>
00060 
00061 
00062   /*-------------------------.
00063   | Graph's implementation.  |
00064   `-------------------------*/
00065 
00066   /*---------------.
00067   | Constructors.  |
00068   `---------------*/
00069 
00070   TParam
00071   GClass::Graph()
00072   { }
00073 
00074   TParam
00075   GClass::Graph (unsigned initial_number_of_state,
00076                  unsigned reserve_number_of_edge)
00077   {
00078     states_.resize(initial_number_of_state);
00079     edges_.reserve(reserve_number_of_edge);
00080   }
00081 
00082 
00083   /*------------------.
00084   | Basic accessors.  |
00085   `------------------*/
00086 
00087   TParam
00088   typename GClass::states_t
00089   GClass::states() const
00090   {
00091     return states_t(hstate_t(0),
00092                     hstate_t(states_.size()) - 1,
00093                     removed_states_);
00094   }
00095 
00096   TParam
00097   typename GClass::edges_t
00098   GClass::edges() const
00099   {
00100     return edges_t(hedge_t(0),
00101                    hedge_t(edges_.size()) - 1,
00102                    removed_edges_);
00103   }
00104 
00105   TParam
00106   typename GClass::initial_support_t
00107   GClass::initial() const
00108   {
00109     return initial_support_t(initial_);
00110   }
00111 
00112   TParam
00113   typename GClass::final_support_t
00114   GClass::final() const
00115   {
00116     return final_support_t(final_);
00117   }
00118 
00119 
00120   /*----------------------.
00121   | States manipulation.  |
00122   `----------------------*/
00123 
00124   TParam
00125   bool
00126   GClass::has_state(hstate_t n) const
00127   {
00128     bool res = ((removed_states_.find(n) == removed_states_.end())
00129                 && n >= 0
00130                 && n < int(states_.size()));
00131 # ifndef VCSN_NDEBUG
00132     if (res == false)
00133       for (int i = 0; i < int(edges_.size()); ++i)
00134         if (removed_edges_.find(hedge_t(i)) == removed_edges_.end())
00135           postcondition(edges_[i].from != n
00136                         && edges_[i].to != n);
00137 # endif // !VCSN_NDEBUG
00138     return res;
00139   }
00140 
00141   TParam
00142   hstate_t
00143   GClass::add_state()
00144   {
00145     if (removed_states_.size() == 0)
00146     {
00147       states_.push_back(state_value_t());
00148       return states_.size() - 1;
00149     }
00150 
00151     hstate_t n = *removed_states_.begin();
00152     removed_states_.erase(n);
00153     assertion(n < int(states_.size()));
00154 
00155     states_[n].output_edges.clear();
00156     states_[n].input_edges.clear();
00157 
00158     postcondition(has_state(n));
00159     return n;
00160   }
00161 
00162   TParam
00163   void
00164   GClass::del_state(hstate_t n)
00165   {
00166     precondition (has_state(n));
00167 
00168     const state_value_t& v = states_[n];
00169     state_value::edges_t::const_iterator e = v.output_edges.begin();
00170     state_value::edges_t::const_iterator end = v.output_edges.end();
00171     state_value::edges_t::const_iterator next = e;
00172 
00173     for (; e != end; e = next)
00174     {
00175       ++next;
00176       this->del_edge(*e);
00177     }
00178 
00179     e = v.input_edges.begin();
00180     end = v.input_edges.end();
00181     for (next = e; e != end; e = next)
00182     {
00183       ++next;
00184       this->del_edge(*e);
00185     }
00186 
00187     removed_states_.insert(n);
00188     initial_.erase(n);
00189     final_.erase(n);
00190     postcondition(!has_state(n));
00191   }
00192 
00193   TParam
00194   void
00195   GClass::set_initial(hstate_t n, const series_set_elt_value_t& v,
00196                       const series_set_elt_value_t& z)
00197   {
00198     if (z == v)
00199       initial_.erase(n);
00200     else
00201       initial_[n] = v;
00202   }
00203 
00204   TParam
00205   const typename GClass::series_set_elt_value_t&
00206   GClass::get_initial(hstate_t n, const series_set_elt_value_t& z) const
00207   {
00208     typename initial_t::const_iterator i = initial_.find(n);
00209     if (i == initial_.end())
00210       return z;
00211     return i->second;
00212   }
00213 
00214   TParam
00215   void
00216   GClass::clear_initial()
00217   {
00218     return initial_.clear();
00219   }
00220 
00221   TParam
00222   void
00223   GClass::set_final(hstate_t n, const series_set_elt_value_t& v,
00224                     const series_set_elt_value_t& z)
00225   {
00226     if (v == z)
00227       final_.erase(n);
00228     else
00229       final_[n] = v;
00230   }
00231 
00232   TParam
00233   const typename GClass::series_set_elt_value_t&
00234   GClass::get_final(hstate_t n, const series_set_elt_value_t& z) const
00235   {
00236     typename final_t::const_iterator i = final_.find(n);
00237     if (i == final_.end())
00238       return z;
00239     return i->second;
00240   }
00241 
00242   TParam
00243   void
00244   GClass::clear_final()
00245   {
00246     return final_.clear();
00247   }
00248 
00249 
00250   /*---------------------.
00251   | Edges manipulation.  |
00252   `---------------------*/
00253 
00254   TParam
00255   bool
00256   GClass::has_edge(hedge_t e) const
00257   {
00258     bool res = (removed_edges_.find(e) == removed_edges_.end()
00259                 && (e < int(edges_.size())));
00260 # ifndef VCSN_NDEBUG
00261     if (res == false)
00262       for (int i = 0; i < int(states_.size()); ++i)
00263         if (removed_states_.find(hstate_t(i)) == removed_states_.end())
00264           postcondition(states_[i].output_edges.find(e) ==
00265                         states_[i].output_edges.end());
00266 # endif // !VCSN_NDEBUG
00267     return res;
00268   }
00269 
00270   TParam
00271   hedge_t
00272   GClass::add_edge(hstate_t n1, hstate_t n2,
00273                    const label_t& v)
00274   {
00275     precondition(has_state(n1));
00276     precondition(has_state(n2));
00277     hedge_t e;
00278     if (removed_edges_.size() == 0)
00279     {
00280       edges_.push_back(edge_value_t(n1, n2, v));
00281       e = edges_.size() - 1;
00282     }
00283     else
00284     {
00285       e = *removed_edges_.begin();
00286       removed_edges_.erase(e);
00287       assertion(e < int(edges_.size()));
00288       edges_[e].from = n1;
00289       edges_[e].to = n2;
00290       edges_[e].label = v;
00291     }
00292     states_[n1].output_edges.insert(e);
00293     states_[n2].input_edges.insert(e);
00294 
00295     postcondition(has_edge(e));
00296     return e;
00297   }
00298 
00299   TParam
00300   void
00301   GClass::del_edge(hedge_t e)
00302   {
00303     if (!has_edge(e))
00304       return;
00305 
00306     const edge_value_t& ev = edges_[e];
00307     states_[ev.from].output_edges.erase(e);
00308     states_[ev.to].input_edges.erase(e);
00309     removed_edges_.insert(e);
00310 
00311     postcondition(!has_edge(e));
00312   }
00313 
00314 
00315   TParam
00316   hstate_t
00317   GClass::src_of(hedge_t e1) const
00318   {
00319     precondition(has_edge(e1));
00320     return edges_[e1].from;
00321   }
00322 
00323   TParam
00324   hstate_t
00325   GClass::dst_of(hedge_t e2) const
00326   {
00327     precondition(has_edge(e2));
00328     return edges_[e2].to;
00329   }
00330 
00331   TParam
00332   const typename GClass::label_t&
00333   GClass::label_of(hedge_t n) const
00334   {
00335     precondition(has_edge(n));
00336     return edges_[n];
00337   }
00338 
00339   TParam
00340   void
00341   GClass::update(hedge_t e, label_t l)
00342   {
00343     precondition(has_edge(e));
00344     edges_[e].label = l;
00345   }
00346 
00347 
00349   TParam
00350   template <class S>
00351   bool
00352   GClass::exists(const AutomataBase<S>& s) const
00353   {
00354     typename WordValue::iterator        it;
00355     typename label_t::const_iterator    r;
00356     label_t                             l;
00357     WordValue                           w;
00358 
00359     for (int i = 0; i < int(edges_.size()); ++i)
00360     {
00361       if (removed_edges_.find(hedge_t(i)) != removed_edges_.end())
00362         continue;
00363       // Make sure that source and destination of edge are part of the
00364       // automaton.
00365       if (!has_state(dst_of(hedge_t(i))) ||
00366           !has_state(src_of(hedge_t(i))))
00367         return false;
00368 
00369       // Make sure that every letter of the edge is in the alphabet.
00370       l = label_of(hedge_t(i));
00371       for (r = l.begin(); r != l.end(); ++r)
00372       {
00373         w = r->first;
00374         for (it = w.begin(); it != w.end(); ++it)
00375           if (!s.series().monoid().alphabet().contains(*it))
00376             return false;
00377       }
00378     }
00379     return true;
00380   }
00381 
00382   /*------------------.
00383   | Delta functions.  |
00384   `------------------*/
00385 
00386   // Classical ones.
00387 
00388 # define DEFINE_DELTA_FUNCTION(DeltaName, DKind, IO, WhatFromE)         \
00389   TParam                                                                \
00390   template <class OutputIterator, class Query>                          \
00391   void                                                                  \
00392   GClass::DeltaName(OutputIterator res,                                 \
00393                     hstate_t from,                                      \
00394                     const Query& query,                                 \
00395                     delta_kind::DKind) const                            \
00396   {                                                                     \
00397     assertion(has_state(from));                                         \
00398     const std::set<hedge_t>& edges = states_[from].IO ## _edges;        \
00399     for_all_const_(std::set<hedge_t>, e, edges)                         \
00400       if (query(*e))                                                    \
00401         *res++ = WhatFromE;                                             \
00402   }                                                                     \
00403 
00404   DEFINE_DELTA_FUNCTION (delta, edges, output, *e);
00405   DEFINE_DELTA_FUNCTION (delta, states, output, edges_[*e].to);
00406   DEFINE_DELTA_FUNCTION (rdelta, edges, input, *e);
00407   DEFINE_DELTA_FUNCTION (rdelta, states, input, edges_[*e].from);
00408 
00409 # undef DEFINE_DELTA_FUNCTION
00410 
00411   // Delta with functor.  Much more than the previous one, because
00412   // functor is statically checked for return type of its operator(),
00413   // and behave differently if it is bool: loop breaks if false is
00414   // returned.
00415 # define DEFINE_DELTAF_FUNCTION(DeltaName, DKind, IO, IsBool, Action)   \
00416   TParam                                                                \
00417   template <typename Functor, class Query>                              \
00418   void                                                                  \
00419   GClass::DeltaName(Functor& fun,                                       \
00420                     hstate_t from,                                      \
00421                     const Query& query,                                 \
00422                     delta_kind::DKind,                                  \
00423                     misc::IsBool ## _t) const                           \
00424   {                                                                     \
00425     assertion(has_state(from));                                         \
00426     const std::set<hedge_t>& edges = states_[from].IO ## _edges;        \
00427     for_all_const_(std::set<hedge_t>, e, edges)                         \
00428       if (query(*e))                                                    \
00429       { Action; }                                                       \
00430   }
00431 
00432   DEFINE_DELTAF_FUNCTION (deltaf, states, output, true,
00433                           if (not fun(edges_[*e].to)) break);
00434   DEFINE_DELTAF_FUNCTION (deltaf, states, output, false, fun(edges_[*e].to));
00435   DEFINE_DELTAF_FUNCTION (deltaf, edges, output, true,
00436                           if (not fun(*e)) break);
00437   DEFINE_DELTAF_FUNCTION (deltaf, edges, output, false, fun(*e));
00438 
00439   DEFINE_DELTAF_FUNCTION (rdeltaf, states, input, true,
00440                           if (not fun(edges_[*e].from)) break);
00441   DEFINE_DELTAF_FUNCTION (rdeltaf, states, input, false, fun(edges_[*e].from));
00442   DEFINE_DELTAF_FUNCTION (rdeltaf, edges, input, true,
00443                           if (not fun(*e)) break);
00444   DEFINE_DELTAF_FUNCTION (rdeltaf, edges, input, false, fun(*e));
00445 
00446 # undef DEFINE_DELTAF_FUNCTION
00447 
00448   // Helpers for static dispatch.
00449   namespace deltaf_helper {
00450     template <typename T, typename R, typename Arg>
00451     char is_returning_bool_helper (R (T::*) (Arg));
00452 
00453     template <typename T, typename Arg>
00454     int is_returning_bool_helper (bool (T::*) (Arg));
00455 
00456 # define is_returning_bool(T)                                           \
00457     (sizeof (deltaf_helper::is_returning_bool_helper (T)) == sizeof (int))
00458   }
00459 
00460 # define DEFINE_DELTAF_HELPER(DeltaName)                                \
00461   TParam                                                                \
00462   template <typename Functor, class Query, typename DKind>              \
00463   void                                                                  \
00464   GClass::DeltaName(Functor& fun,                                       \
00465                     hstate_t from,                                      \
00466                     const Query& query,                                 \
00467                     delta_kind::kind<DKind> k) const                    \
00468   {                                                                     \
00469     DeltaName (fun, from, query, k,                                     \
00470                BOOL_TO_TYPE (is_returning_bool (&Functor::operator ())) ()); \
00471   }
00472 
00473   DEFINE_DELTAF_HELPER (deltaf);
00474   DEFINE_DELTAF_HELPER (rdeltaf);
00475 
00476 # undef DEFINE_DELTAF_HELPER
00477 # undef is_returning_bool
00478 
00479   /*------.
00480   | Tag.  |
00481   `------*/
00482 
00483   TParam
00484   inline
00485   Tag& GClass::tag()
00486   {
00487     return tag_;
00488   }
00489 
00490   TParam
00491   const Tag& GClass::tag() const
00492   {
00493     return tag_;
00494   }
00495 
00496   template <class Kind, class WordValue, class WeightValue, class SerieValue,
00497             class Letter, class Tag, class Geometry, class I>
00498   Tag& op_tag(const AutomataBase<I>&,
00499               Graph<Kind, WordValue, WeightValue,
00500               SerieValue ,Letter, Tag, Geometry>& v)
00501   {
00502     return v.tag();
00503   }
00504 
00505   template <class Kind, class WordValue, class WeightValue, class SerieValue,
00506             class Letter, class Tag, class Geometry, class I>
00507   const Tag& op_tag(const AutomataBase<I>&,
00508                     const Graph<Kind, WordValue, WeightValue,
00509                     SerieValue ,Letter, Tag, Geometry>& v)
00510   {
00511     return v.tag();
00512   }
00513 
00514 
00515   /*-----------.
00516   | Geometry.  |
00517   `-----------*/
00518 
00519   template <class Kind, class WordValue, class WeightValue, class SerieValue,
00520             class Letter, class Tag, class Geometry, class I>
00521   Geometry&
00522   op_geometry(const AutomataBase<I>&,
00523               Graph<Kind, WordValue, WeightValue,
00524               SerieValue, Letter, Tag, Geometry>& v)
00525   {
00526     return v.geometry();
00527   }
00528 
00529   template <class Kind, class WordValue, class WeightValue, class SerieValue,
00530             class Letter, class Tag, class Geometry, class I>
00531   const Geometry&
00532   op_geometry(const AutomataBase<I>&,
00533               const Graph<Kind, WordValue, WeightValue,
00534               SerieValue, Letter, Tag, Geometry>& v)
00535   {
00536     return v.geometry();
00537   }
00538 
00539 
00540   TParam
00541   const Geometry&
00542   GClass::geometry() const
00543   {
00544     return geometry_;
00545   }
00546 
00547   TParam
00548   Geometry&
00549   GClass::geometry()
00550   {
00551     return geometry_;
00552   }
00553 
00554 
00555   // Remove macros to avoid name clashes.
00556 # undef TParam
00557 # undef GClass
00558 
00559 }
00560 
00561 #endif // ! VCSN_AUTOMATA_IMPLEMENTATION_GRAPH_HXX

Generated on Sun Jul 29 19:35:19 2007 for Vaucanson by  doxygen 1.5.2