Vaucanson: bmig_graph_impl.hxx Source File

00001 // boost_graph.hxx: this file is part of the Vaucanson project.
00002 //
00003 // Vaucanson, a generic library for finite state machines.
00004 //
00005 // Copyright (C) 2007, 2008 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 
00018 #ifndef VCSN_AUTOMATA_IMPLEMENTATION_BMIG_GRAPH_IMPL_HXX_
00019 # define VCSN_AUTOMATA_IMPLEMENTATION_BMIG_GRAPH_IMPL_HXX_
00020 
00021 # include <vaucanson/automata/implementation/bmig_graph_impl.hh>
00022 
00023 namespace vcsn
00024 {
00025   namespace bmig
00026   {
00027 
00028     /*--------------------.
00029     | Convenient macros.  |
00030     `--------------------*/
00031 
00032 # define BMIGRAPH_TPARAM                                                \
00033     template <class Kind, class WordValue, class WeightValue,           \
00034               class SeriesValue, class Letter, class Tag, class GeometryCoords>
00035 
00036 # define BMIGRAPH                                                       \
00037     Graph<Kind, WordValue, WeightValue, SeriesValue, Letter, Tag, GeometryCoords>
00038 
00039     /*-------------------------.
00040     | Graph's implementation.  |
00041     `-------------------------*/
00042 
00043     /*---------------.
00044     | Constructors.  |
00045     `---------------*/
00046 
00047     BMIGRAPH_TPARAM
00048     BMIGRAPH::Graph ()
00049       : initial_bitset_(0),
00050         final_bitset_(0),
00051         number_of_epsilon_(0),
00052         number_of_state_(0)
00053     {
00054     }
00055 
00065     BMIGRAPH_TPARAM
00066     BMIGRAPH::Graph (unsigned initial_number_of_states,
00067                       unsigned)
00068       : initial_bitset_(initial_number_of_states),
00069         final_bitset_(initial_number_of_states),
00070         number_of_epsilon_(0),
00071         number_of_state_(initial_number_of_states),
00072         states_(initial_number_of_states)
00073     {
00074       for (unsigned i = 0; i < initial_number_of_states; ++i)
00075       {
00076         boost::shared_ptr<std::size_t> p(new std::size_t(i));
00077         states_[i] = p;
00078       }
00079     }
00080 
00081     BMIGRAPH_TPARAM
00082     BMIGRAPH::Graph (const self_t& g)
00083     {
00084       tag_ = g.tag_;
00085       initial_bitset_ = g.initial_bitset_;
00086       final_bitset_ = g.final_bitset_;
00087       number_of_epsilon_ = g.number_of_epsilon_;
00088       number_of_state_ = g.number_of_state_;
00089       label_container_ = g.label_container_;
00090       initial_.clear();
00091       final_.clear();
00092       states_.resize(g.number_of_state_);
00093       for (unsigned i = 0; i < g.number_of_state_; ++i)
00094       {
00095         boost::shared_ptr<std::size_t> p(new std::size_t(i));
00096         states_[i] = p;
00097       }
00098       graph_.clear();
00099       for (typename graph_data_t::const_iterator i = g.graph_.begin();
00100           i != g.graph_.end();
00101           ++i)
00102         graph_.insert(edge_data_t(states_[*i->from_],
00103                                   states_[*i->to_],
00104                                   i->label_));
00105 //                                label_container_.get_hlabel(g.label_container_.get_label(i->label_))));
00106   # define VCSN_COPY_I_T(Set)                                                                   \
00107       for (typename Set##t::const_iterator i = g.Set.begin();                                   \
00108           i != g.Set.end();                                                                     \
00109           ++i)                                                                                  \
00110         Set.insert(initial_value_t (states_[*i->first], i->second));
00111       VCSN_COPY_I_T(initial_)
00112       VCSN_COPY_I_T(final_)
00113   # undef VCSN_COPY_I_T
00114 
00115   # define VCSN_COPY_GEOMETRY(Type)                                                                     \
00116       {                                                                                                 \
00117         typename geometry_t::Type##_geometry_map_t& map_##Type = geometry_.Type();                      \
00118         map_##Type.clear();                                                                             \
00119         for (typename geometry_t::Type##_geometry_map_t::const_iterator i = g.geometry_.Type().begin(); \
00120             i != g.geometry_.Type().end();                                                              \
00121             ++i)                                                                                                \
00122         map_##Type[i->first] = i->second;                                                               \
00123       }
00124       VCSN_COPY_GEOMETRY(states)
00125       VCSN_COPY_GEOMETRY(initials)
00126       VCSN_COPY_GEOMETRY(finals)
00127 # undef VCSN_COPY_GEOMETRY
00128       {
00129         typename geometry_t::transitions_geometry_map_t& map_transitions = geometry_.transitions();
00130         map_transitions.clear();
00131         for (typename geometry_t::transitions_geometry_map_t::const_iterator i = g.geometry_.transitions().begin();
00132             i != g.geometry_.transitions().end();
00133             ++i)
00134         {
00135           typename graph_data_t::const_iterator tmp = find_edge(states_[*i->first.value()->from_],
00136               states_[*i->first.value()->to_],
00137               i->first.value()->label_);
00138           //label_container_.get_hlabel(g.label_container_.get_label(i->first.value()->label_)));
00139           if (tmp != graph_.end())
00140             map_transitions[htransition_t(tmp)] = i->second;
00141         }
00142       }
00143     }
00144 
00145     /*--------------.
00146     | Destructors.  |
00147     `--------------*/
00148 
00149     BMIGRAPH_TPARAM
00150     BMIGRAPH::~Graph ()
00151     {
00152     }
00153 
00154     BMIGRAPH_TPARAM
00155     typename BMIGRAPH::self_t&
00156     BMIGRAPH::operator= (const self_t& g)
00157     {
00158       if (this == &g)
00159         return *this;
00160       tag_ = g.tag_;
00161       initial_bitset_ = g.initial_bitset_;
00162       final_bitset_ = g.final_bitset_;
00163       number_of_epsilon_ = g.number_of_epsilon_;
00164       number_of_state_ = g.number_of_state_;
00165       label_container_ = g.label_container_;
00166       initial_.clear();
00167       final_.clear();
00168       states_.resize(g.number_of_state_);
00169       for (unsigned i = 0; i < g.number_of_state_; ++i)
00170       {
00171         boost::shared_ptr<std::size_t> p(new std::size_t(i));
00172         states_[i] = p;
00173       }
00174       graph_.clear();
00175       for (typename graph_data_t::const_iterator i = g.graph_.begin();
00176           i != g.graph_.end();
00177           ++i)
00178         graph_.insert(edge_data_t(states_[*i->from_],
00179               states_[*i->to_],
00180               i->label_));
00181 # define VCSN_COPY_I_T(Set)                                                                     \
00182       for (typename Set##t::const_iterator i = g.Set.begin();                                   \
00183           i != g.Set.end();                                                                     \
00184           ++i)                                                                                  \
00185       Set.insert(initial_value_t (states_[*i->first], i->second));
00186       VCSN_COPY_I_T(initial_)
00187       VCSN_COPY_I_T(final_)
00188 # undef VCSN_COPY_I_T
00189 
00190 # define VCSN_COPY_GEOMETRY(Type)                                                                       \
00191       {                                                                                                 \
00192         typename geometry_t::Type##_geometry_map_t& map_##Type = geometry_.Type();                      \
00193         map_##Type.clear();                                                                             \
00194         for (typename geometry_t::Type##_geometry_map_t::const_iterator i = g.geometry_.Type().begin(); \
00195             i != g.geometry_.Type().end();                                                              \
00196             ++i)                                                                                                \
00197         map_##Type[i->first] = i->second;                                                               \
00198       }
00199       VCSN_COPY_GEOMETRY(states)
00200       VCSN_COPY_GEOMETRY(initials)
00201       VCSN_COPY_GEOMETRY(finals)
00202 # undef VCSN_COPY_GEOMETRY
00203       {
00204         typename geometry_t::transitions_geometry_map_t& map_transitions = geometry_.transitions();
00205         map_transitions.clear();
00206         for (typename geometry_t::transitions_geometry_map_t::const_iterator i = g.geometry_.transitions().begin();
00207             i != g.geometry_.transitions().end();
00208             ++i)
00209         {
00210           typename graph_data_t::const_iterator tmp = find_edge(states_[*i->first.value()->from_],
00211               states_[*i->first.value()->to_],
00212               i->first.value()->label_);
00213           //label_container_.get_hlabel(g.label_container_.get_label(i->first.value()->label_)));
00214           if (tmp != graph_.end())
00215             map_transitions[htransition_t(tmp)] = i->second;
00216         }
00217       }
00218       return *this;
00219     }
00220 
00221     /*------------------.
00222     | Basic accessors.  |
00223     `------------------*/
00224 
00225     BMIGRAPH_TPARAM
00226     typename BMIGRAPH::states_t
00227     BMIGRAPH::states() const
00228     {
00229       return misc::Support<states_data_t>(states_);
00230     }
00231 
00232     BMIGRAPH_TPARAM
00233     typename BMIGRAPH::edges_t
00234     BMIGRAPH::edges() const
00235     {
00236       return edges_t(graph_);
00237     }
00238 
00239     BMIGRAPH_TPARAM
00240     typename BMIGRAPH::initial_support_t
00241     BMIGRAPH::initial () const
00242     {
00243       return initial_support_t(initial_);
00244     }
00245 
00246     BMIGRAPH_TPARAM
00247     typename BMIGRAPH::final_support_t
00248     BMIGRAPH::final () const
00249     {
00250       return final_support_t(final_);
00251     }
00252 
00253 
00254     /*----------------------.
00255     | State manipulations.  |
00256     `----------------------*/
00257 
00258     BMIGRAPH_TPARAM
00259     bool
00260     BMIGRAPH::has_state (const hstate_t& s) const
00261     {
00262       // May be we should add a set or a hashtable to have
00263       // a searching time better than linear
00264       bool b = false;
00265       for_all_iterator(states_data_t::const_iterator, i, states_)
00266         if (*i == s.value())
00267           b = true;
00268       return b;
00269     }
00270 
00271     BMIGRAPH_TPARAM
00272     typename BMIGRAPH::hstate_t
00273     BMIGRAPH::add_state ()
00274     {
00275       initial_bitset_.append(false);
00276       final_bitset_.append(false);
00277       boost::shared_ptr<std::size_t> p(new std::size_t(number_of_state_++));
00278       state_t h(p);
00279       states_.push_back(h);
00280       return hstate_t(h);
00281     }
00282 
00283     BMIGRAPH_TPARAM
00284     typename BMIGRAPH::hstate_t
00285     BMIGRAPH::get_state (unsigned s) const
00286     {
00287       precondition(s < states_.size());
00288       return hstate_t(states_[s]);
00289     }
00290 
00291     BMIGRAPH_TPARAM
00292     void
00293     BMIGRAPH::del_state (const hstate_t& s)
00294     {
00295       precondition (has_state(s));
00296 
00297       // One removes the state h
00298       graph_.template get<src>().erase(s.value());
00299       graph_.template get<dst>().erase(s.value());
00300 
00301       if (s != (number_of_state_ - 1) && (number_of_state_ - 1))
00302       {
00303         state_t lastone = states_.back();
00304         states_[s] = lastone;
00305   # define VCSN_UPDATE(Set)                                   \
00306         if (Set##bitset_[*lastone])                           \
00307         {                                                     \
00308           if (Set##bitset_[s])                                \
00309             Set.erase(s.value());                             \
00310           else                                                \
00311             Set##bitset_[s] = true;                           \
00312         }                                                     \
00313         else                                                  \
00314         {                                                     \
00315           if (Set##bitset_[s])                                \
00316           {                                                   \
00317             Set##bitset_[s] = false;                          \
00318             Set.erase(s.value());                             \
00319           }                                                   \
00320         }
00321 
00322         //Updating initial/final states information
00323         VCSN_UPDATE(initial_)
00324         VCSN_UPDATE(final_)
00325   # undef VCSN_UPDATE
00326         *lastone = *s.value();
00327       }
00328       else
00329       {
00330         initial_.erase(s.value());
00331         final_.erase(s.value());
00332       }
00333 
00334       --number_of_state_;
00335       states_.pop_back();
00336       postcondition(states_.size() == number_of_state_);
00337       //delete s.value();
00338       initial_bitset_.resize(number_of_state_);
00339       final_bitset_.resize(number_of_state_);
00340 
00341       //Useless postcondition since the states are 'renamed'
00342       //postcondition(!has_state(h));
00343     }
00344 
00345     BMIGRAPH_TPARAM
00346     void
00347     BMIGRAPH::set_initial (const hstate_t& s,
00348                            const series_set_elt_value_t& v,
00349                            const series_set_elt_value_t& z)
00350     {
00351       precondition(has_state(s));
00352       if (z == v)
00353       {
00354         initial_.erase (s.value());
00355         initial_bitset_[s] = false;
00356       }
00357       else if (!initial_bitset_[s])
00358       {
00359         initial_.insert (initial_value_t (s.value(), v));
00360         initial_bitset_[s] = true;
00361       }
00362       else
00363         initial_.modify(initial_.find(s.value()), update_label<initial_value_t>(v));
00364     }
00365 
00366     BMIGRAPH_TPARAM
00367     const typename BMIGRAPH::series_set_elt_value_t&
00368     BMIGRAPH::get_initial(const hstate_t& s, const series_set_elt_value_t &zero) const
00369     {
00370       precondition(has_state(s));
00371       typename initial_t::const_iterator it = initial_.find(s.value());
00372 
00373       if (it == initial_.end())
00374         return zero;
00375       return it->second;
00376     }
00377 
00378     BMIGRAPH_TPARAM
00379     bool
00380     BMIGRAPH::is_initial(const hstate_t& s, const series_set_elt_value_t&) const
00381     {
00382       precondition(has_state(s));
00383       return initial_bitset_[s];
00384     }
00385 
00386     BMIGRAPH_TPARAM
00387     void
00388     BMIGRAPH::clear_initial()
00389     {
00390       initial_.clear();
00391       initial_bitset_.reset();
00392     }
00393 
00394     BMIGRAPH_TPARAM
00395     void
00396     BMIGRAPH::set_final(const hstate_t& s,
00397                           const series_set_elt_value_t& v,
00398                           const series_set_elt_value_t& z)
00399     {
00400       precondition(has_state(s));
00401       if (z == v)
00402       {
00403         final_.erase (s.value());
00404         final_bitset_[s] = false;
00405       }
00406       else if (!final_bitset_[s])
00407       {
00408         final_.insert (initial_value_t (s.value(), v));
00409         final_bitset_[s] = true;
00410       }
00411       else
00412         final_.modify(final_.find(s.value()), update_label<final_value_t>(v));
00413     }
00414 
00415     BMIGRAPH_TPARAM
00416     const typename BMIGRAPH::series_set_elt_value_t&
00417     BMIGRAPH::get_final(const hstate_t& s, const series_set_elt_value_t &zero) const
00418     {
00419       precondition(has_state(s));
00420       typename final_t::const_iterator it = final_.find(s.value());
00421 
00422       if (it == final_.end())
00423         return zero;
00424       return it->second;
00425     }
00426 
00427     BMIGRAPH_TPARAM
00428     bool
00429     BMIGRAPH::is_final(const hstate_t& s, const series_set_elt_value_t&) const
00430     {
00431       precondition(has_state(s));
00432       return final_bitset_[s];
00433     }
00434 
00435     BMIGRAPH_TPARAM
00436     void
00437     BMIGRAPH::clear_final()
00438     {
00439       final_.clear();
00440       final_bitset_.reset();
00441     }
00442 
00443     /*---------------------.
00444     | Edge manipulations.  |
00445     `---------------------*/
00446 
00447     BMIGRAPH_TPARAM
00448     bool
00449     BMIGRAPH::has_edge (const hedge_t& h) const
00450     {
00451       succ_range r = graph_.equal_range(boost::make_tuple(h.value()->from_,
00452                                                     h.value()->label_));
00453       succ_iterator it;
00454       state_t to = h.value()->to_;
00455       for (it = r.first; it != r.second && it->to_ != to; ++it)
00456         /*Nothing*/;
00457 
00458       return it != r.second;
00459     }
00460 
00461     BMIGRAPH_TPARAM
00462     typename BMIGRAPH::hedge_t
00463     BMIGRAPH::add_edge (const hstate_t& from, const hstate_t& to, const label_t& l)
00464     {
00465       //hlabel_t hl = label_container_.insert (l);
00466       return hedge_t (graph_.insert (edge_data_t (from.value(), to.value(), l)).first);
00467     }
00468 
00469     BMIGRAPH_TPARAM
00470     void
00471     BMIGRAPH::del_edge (const hedge_t& h)
00472     {
00473       precondition (has_edge(h));
00474 
00475       hlabel_t l = h.value()->label_;
00476       graph_.erase(h.value());
00477       //label_container_.erase(l);
00478 
00479       // h points to an invalid edgeValue since it is already destroyed.
00480       // We can't check this postcondition anymore!
00481       //postcondition(!has_edge(h));
00482     }
00483 
00484     BMIGRAPH_TPARAM
00485     typename BMIGRAPH::hstate_t
00486     BMIGRAPH::src_of (const hedge_t& h) const
00487     {
00488       return hstate_t(h.value()->from_);
00489     }
00490 
00491     BMIGRAPH_TPARAM
00492     typename BMIGRAPH::hstate_t
00493     BMIGRAPH::dst_of (const hedge_t& h) const
00494     {
00495       return hstate_t(h.value()->to_);
00496     }
00497 
00498     BMIGRAPH_TPARAM
00499     const typename BMIGRAPH::label_t&
00500     BMIGRAPH::label_of (const hedge_t& h) const
00501     {
00502       return h.value()->label_;
00503 //      return label_container_.get_label(h.value()->label_);
00504     }
00505 
00506     BMIGRAPH_TPARAM
00507     void
00508     BMIGRAPH::update(const hedge_t& h, const label_t& l)
00509     {
00510       label_container_.update(h->label_, l);
00511       graph_.modify(h.value(), update_hlabel<hlabel_t>(h->label_));
00512     }
00513 
00514     BMIGRAPH_TPARAM
00515     template <class S>
00516     bool
00517     BMIGRAPH::exists (const AutomataBase<S>& s) const
00518     {
00519       typename WordValue::iterator      it;
00520       typename label_t::const_iterator  r;
00521       label_t                           l;
00522       WordValue                         w;
00523 
00524       for (typename graph_data_t::iterator i = graph_.begin(); i != graph_.end(); ++i)
00525       {
00526         // Make sure that source and destination of edge are part of the
00527         // automaton.
00528         if (!has_state(dst_of(hedge_t(i))) ||
00529             !has_state(src_of(hedge_t(i))))
00530           return false;
00531 
00532         // Make sure that every letter of the edge is in the alphabet.
00533         l = label_of(hedge_t(i));
00534         for (r = l.begin(); r != l.end(); ++r)
00535         {
00536           w = r->first;
00537           for (it = w.begin(); it != w.end(); ++it)
00538             if (!s.series().monoid().alphabet().contains(*it))
00539               return false;
00540         }
00541       }
00542       return true;
00543     }
00544 
00545     BMIGRAPH_TPARAM
00546     inline
00547     typename BMIGRAPH::tag_t&
00548     BMIGRAPH::tag ()
00549     {
00550       return tag_;
00551     }
00552 
00553     BMIGRAPH_TPARAM
00554     inline
00555     const typename BMIGRAPH::tag_t&
00556     BMIGRAPH::tag () const
00557     {
00558       return tag_;
00559     }
00560 
00561     BMIGRAPH_TPARAM
00562     inline
00563     typename BMIGRAPH::geometry_t&
00564     BMIGRAPH::geometry ()
00565     {
00566       return geometry_;
00567     }
00568 
00569     BMIGRAPH_TPARAM
00570     inline
00571     const typename BMIGRAPH::geometry_t&
00572     BMIGRAPH::geometry () const
00573     {
00574       return geometry_;
00575     }
00576 
00577     template <class Kind, class WordValue, class WeightValue, class SeriesValue,
00578               class Letter, class Tag, class GeometryCoords, class I>
00579     Tag&
00580     op_tag(const AutomataBase<I>&, BMIGRAPH &g)
00581     {
00582       return g.tag();
00583     }
00584 
00585     template <class Kind, class WordValue, class WeightValue, class SeriesValue,
00586               class Letter, class Tag, class GeometryCoords, class I>
00587     const Tag&
00588     op_tag(const AutomataBase<I>&, BMIGRAPH &g)
00589     {
00590       return g.tag();
00591     }
00592 
00593     template <class Kind, class WordValue, class WeightValue, class SeriesValue,
00594               class Letter, class Tag, class GeometryCoords, class I>
00595     typename BMIGRAPH::geometry_t&
00596     op_geometry(const AutomataBase<I>&, BMIGRAPH &g)
00597     {
00598       return g.geometry();
00599     }
00600 
00601     template <class Kind, class WordValue, class WeightValue, class SeriesValue,
00602               class Letter, class Tag, class GeometryCoords, class I>
00603     const typename BMIGRAPH::geometry_t&
00604     op_geometry(const AutomataBase<I>&, const BMIGRAPH &g)
00605     {
00606       return g.geometry();
00607     }
00608 
00609     BMIGRAPH_TPARAM
00610     typename BMIGRAPH::graph_data_t::const_iterator
00611     BMIGRAPH::find_edge(const state_t& from, const state_t& to,
00612                           const hlabel_t& label) const
00613     {
00614       succ_range r = graph_.equal_range(::boost::make_tuple(from, label));
00615       for (succ_iterator i = r.first; i != r.second; ++i)
00616         if (i->to_ == to)
00617           return i;
00618       return graph_.end();
00619     }
00620 
00621     /*------------------.
00622     | Delta functions.  |
00623     `------------------*/
00624 
00625   # define DEFINE_DELTAI_FUNCTION(DeltaKind)                                    \
00626     BMIGRAPH_TPARAM                                                             \
00627     std::pair<typename BMIGRAPH::DeltaKind##_iterator,                          \
00628               typename BMIGRAPH::DeltaKind##_iterator>                          \
00629     BMIGRAPH::deltai(const hstate_t& s, DeltaKind##_iterator) const             \
00630     {                                                                           \
00631       assertion(has_state(s));                                                  \
00632       return graph_.template get<DeltaKind>().equal_range(s.value());           \
00633     }
00634 
00635     DEFINE_DELTAI_FUNCTION(src);
00636     DEFINE_DELTAI_FUNCTION(dst);
00637   # undef DEFINE_DELTAI_FUNCTION
00638 
00639     BMIGRAPH_TPARAM
00640     template <typename I>
00641     typename BMIGRAPH::htransition_t
00642     BMIGRAPH::get_htransition(const I& i) const
00643     {
00644       return htransition_t(graph_.project<0>(i));
00645     }
00646 
00647     // End of syntactic sugar
00648 # undef BMIGRAPH_TPARAM
00649 # undef BMIGRAPH
00650   } // End of namespace bmig
00651 } // End of namespace vcsn
00652 
00653 #endif // !VCSN_AUTOMATA_IMPLEMENTATION_BMIG_GRAPH_IMPL_HXX_ //