minimization_hopcroft.hxx

00001 // minimization_hopcroft.hxx: this file is part of the Vaucanson project.
00002 //
00003 // Vaucanson, a generic library for finite state machines.
00004 //
00005 // Copyright (C) 2001, 2002, 2003, 2004, 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_ALGORITHMS_MINIMIZATION_HOPCROFT_HXX
00018 # define VCSN_ALGORITHMS_MINIMIZATION_HOPCROFT_HXX
00019 
00020 # include <algorithm>
00021 # include <list>
00022 # include <queue>
00023 # include <set>
00024 # include <vector>
00025 
00026 # include <vaucanson/algebra/implementation/semiring/numerical_semiring.hh>
00027 # include <vaucanson/algorithms/minimization_hopcroft.hh>
00028 # include <vaucanson/automata/concept/automata_base.hh>
00029 # include <vaucanson/misc/usual_macros.hh>
00030 # include <vaucanson/misc/bitset.hh>
00031 
00032 namespace vcsn
00033 {
00034 
00035   namespace internal
00036   {
00037     namespace hopcroft_minimization_det
00038     {
00039 
00040 # define HOPCROFT_TYPES()                                               \
00041       typedef std::set<hstate_t> hstates_t;                             \
00042       typedef std::vector<hstates_t> partition_t;                       \
00043       typedef std::vector<unsigned> class_of_t;                         \
00044       typedef std::queue<std::pair<hstates_t*, unsigned> > to_treat_t;
00045 
00050       template <typename input_t>
00051       struct splitter_functor
00052       {
00053         AUTOMATON_TYPES (input_t);
00054         AUTOMATON_FREEMONOID_TYPES (input_t);
00055         HOPCROFT_TYPES ();
00056 
00057         const input_t& input_;
00058         hstates_t going_in_;
00059         class_of_t& class_of_;
00060         std::list<unsigned> maybe_splittable_;
00061         std::vector<unsigned> count_for_;
00062 
00063         splitter_functor (const input_t& input, hstate_t max_state,
00064                           class_of_t& class_of)
00065           : input_ (input), going_in_ (), class_of_(class_of),
00066             count_for_ (max_state)
00067         {}
00068 
00070         bool compute_states_going_in (const hstates_t& ss, letter_t l)
00071         {
00072           going_in_.clear ();
00073           maybe_splittable_.clear ();
00074           for_all_const (hstates_t, i, ss)
00075             input_.letter_rdeltaf (*this, *i, l, delta_kind::states ());
00076           return not going_in_.empty ();
00077         }
00078 
00080         void operator () (hstate_t state)
00081         {
00082           unsigned class_of_state = class_of_[state];
00083 
00084           if (count_for_[class_of_state] == 0)
00085             maybe_splittable_.push_back (class_of_state);
00086           count_for_[class_of_state]++;
00087           going_in_.insert (state);
00088         }
00089 
00091         void execute (partition_t& partition, to_treat_t& to_treat,
00092                       unsigned& n_partition)
00093         {
00094           for_all (std::list<unsigned>, inpartition, maybe_splittable_)
00095           {
00096             hstates_t& states = partition[*inpartition];
00097             if (states.size () == count_for_[*inpartition])
00098             { // All elements in states are predecessors, no split.
00099               count_for_[*inpartition] = 0;
00100               continue;
00101             }
00102             count_for_[*inpartition] = 0;
00103             hstates_t states_inter_going_in;
00104             hstates_t& states_minus_going_in = partition[n_partition];
00105             // Compute @a states \ @a going_in_.
00106             set_difference
00107               (states.begin (), states.end (),
00108                going_in_.begin (), going_in_.end (),
00109                std::insert_iterator<hstates_t> (states_minus_going_in,
00110                                                 states_minus_going_in.begin ()));
00111             // Compute @a states Inter @a going_in_.
00112             set_intersection
00113               (states.begin(), states.end (),
00114                going_in_.begin (), going_in_.end (),
00115                std::insert_iterator<hstates_t> (states_inter_going_in,
00116                                                 states_inter_going_in.begin ()));
00117             // A split MUST occur.
00118             assertion (not (states_inter_going_in.empty ()
00119                             or states_minus_going_in.empty ()));
00120             // @a states must be the bigger one.
00121             if (states_minus_going_in.size () > states_inter_going_in.size ())
00122             {
00123               states.swap (states_minus_going_in);
00124               states_minus_going_in.swap (states_inter_going_in);
00125             }
00126             else
00127               states.swap (states_inter_going_in);
00128             for_all (hstates_t, istate, states_minus_going_in)
00129               class_of_[*istate] = n_partition;
00130             to_treat.push (std::make_pair (&states_minus_going_in,
00131                                            n_partition++));
00132           }
00133         }
00134       };
00135 
00137       template <typename input_t, typename output_t>
00138       struct transition_adder_functor
00139       {
00140         AUTOMATON_TYPES (input_t);
00141         HOPCROFT_TYPES ();
00142 
00143         const input_t& input_;
00144         output_t& output_;
00145         const class_of_t& class_of_;
00146 
00147         hstate_t src_;
00148 
00149         transition_adder_functor (const input_t& input, output_t& output,
00150                                   const class_of_t& class_of)
00151           : input_ (input), output_ (output), class_of_ (class_of)
00152         {}
00153 
00155         void execute (hstate_t representative)
00156         {
00157           src_ = class_of_[representative];
00158           input_.deltaf (*this, representative, delta_kind::transitions ());
00159         }
00160 
00161         void operator () (htransition_t t)
00162         {
00163           output_.add_series_transition (src_, class_of_[input_.dst_of (t)],
00164                                          input_.series_of (t));
00165         }
00166       };
00167     }
00168   }
00169 
00170 
00171   template <typename A, typename input_t, typename output_t>
00172   void
00173   do_hopcroft_minimization_det(const AutomataBase<A>&   ,
00174                                output_t&                output,
00175                                const input_t&           input)
00176   {
00177     AUTOMATON_TYPES (input_t);
00178     AUTOMATON_FREEMONOID_TYPES (input_t);
00179     HOPCROFT_TYPES ();
00180 
00181     using namespace internal::hopcroft_minimization_det;
00182 
00183     unsigned max_state = input.states ().max () + 1;
00184     partition_t partition (max_state);
00185     class_of_t class_of (max_state);
00186     to_treat_t to_treat;
00187     unsigned n_partition = 0;
00188     const alphabet_t& alphabet =
00189       input.structure ().series ().monoid ().alphabet ();
00190 
00191     {
00192       // Initialize Partition = {Q \ F , F }
00193       hstates_t* finals = 0, * others = 0;
00194       int n_finals = -1, n_others = -1,
00195         count_finals = 0, count_others = 0;
00196 
00197 # define add_to_class(Name)                     \
00198       do {                                      \
00199         if (not Name)                           \
00200         {                                       \
00201           Name = &(partition[n_partition]);     \
00202           n_ ## Name = n_partition++;           \
00203         }                                       \
00204         count_ ## Name ++;                      \
00205         (*Name).insert (*state);                \
00206         class_of[*state] = n_ ## Name;          \
00207       } while (0)
00208 
00209       for_all_states (state, input)
00210         if (input.is_final (*state))
00211           add_to_class (finals);
00212         else
00213           add_to_class (others);
00214 # undef add_to_class
00215 
00216       if (n_partition == 0)
00217         return;
00218       if (n_partition == 1)
00219       {
00220         output = input;
00221         return;
00222       }
00223       // Put F or Q \ F in the "To treat" list T.
00224       if (count_finals > count_others)
00225         to_treat.push (std::make_pair (others, n_others));
00226       else
00227         to_treat.push (std::make_pair (finals, n_finals));
00228     }
00229 
00230     {
00231       splitter_functor<input_t> splitter (input, max_state, class_of);
00232 
00233       // While T is not empty,
00234       while (not to_treat.empty () && n_partition < max_state)
00235       {
00236         // Remove a set S of T ,
00237         hstates_t& states = *(to_treat.front ().first);
00238         to_treat.pop ();
00239 
00240         // For each letter l in Alphabet,
00241         for_all_letters (letter, alphabet)
00242           {
00243             if (not splitter.compute_states_going_in (states, *letter))
00244               continue;
00245             splitter.execute (partition, to_treat, n_partition);
00246             if (n_partition == max_state)
00247               break;
00248           }
00249       }
00250     }
00251 
00252     // Build the automaton.
00253     // Assume that states are numbers starting from 0.
00254     for (unsigned i = 0; i < n_partition; ++i)
00255       output.add_state ();
00256 
00257     transition_adder_functor<input_t, output_t>
00258       transition_adder (input, output, class_of);
00259 
00260     partition_t::iterator istates = partition.begin ();
00261     for (unsigned i = 0; i < n_partition; ++i, ++istates)
00262     {
00263       int representative = *(*istates).begin();
00264 
00265       if (input.is_final (representative))
00266         output.set_final (class_of[representative]);
00267       transition_adder.execute (representative);
00268     }
00269 
00270     for_all_initial_states (state, input)
00271       output.set_initial (class_of[*state]);
00272   }
00273 
00274 # undef HOPCROFT_TYPES
00275 
00284   template<typename A, typename T>
00285   Element<A, T>
00286   minimization_hopcroft(const Element<A, T>& a)
00287   {
00288     TIMER_SCOPED ("minimization_hopcroft");
00289     Element<A, T> output(a.structure());
00290     do_hopcroft_minimization_det(a.structure(), output, a);
00291     return output;
00292   }
00293 
00294 
00295   /*-------------------------------------.
00296   | Quotient with Boolean multiplicities |
00297   `-------------------------------------*/
00298   namespace internal
00299   {
00300     namespace hopcroft_minimization_undet
00301     {
00302 
00303 # define QUOTIENT_TYPES()                                               \
00304       typedef std::list<hstate_t> partition_t;                          \
00305       typedef std::vector<partition_t> partition_set_t;                 \
00306       typedef typename partition_t::iterator partition_iterator;        \
00307       typedef std::vector<partition_iterator> places_t;                 \
00308       typedef std::vector<unsigned> class_of_t;                         \
00309       typedef std::set<hstate_t> delta_ret_t;
00310 
00311       template <typename input_t>
00312       class quotient_splitter
00313       {
00314       public:
00315         AUTOMATON_TYPES(input_t);
00316         AUTOMATON_FREEMONOID_TYPES(input_t);
00317         QUOTIENT_TYPES();
00318         typedef std::vector<bool> going_in_t;
00319 
00320         quotient_splitter (const automaton_t& input, class_of_t& class_of,
00321                            unsigned max_states)
00322           : input_(input),
00323             class_(class_of),
00324             count_for_(max_states, 0),
00325             twin_(max_states, 0),
00326             going_in_(max_states, false)
00327         { }
00328 
00330         bool compute_going_in_states (partition_t& p, letter_t a)
00331         {
00332           for_all_(going_in_t, s, going_in_)
00333             *s = false;
00334 
00335           for_all_(partition_t, s, p)
00336             input_.letter_rdeltaf(*this, *s, a, delta_kind::states());
00337           return !met_class.empty();
00338         }
00339 
00341         void operator() (hstate_t s)
00342         {
00343           if (!going_in_[s])
00344           {
00345             going_in_[s] = true;
00346             unsigned i = class_[s];
00347             if (!count_for_[i])
00348               met_class.push_back(i);
00349             count_for_[i]++;
00350           }
00351         }
00352 
00354         void split (partition_set_t& part, unsigned& max_partitions)
00355         {
00356           std::queue<partition_iterator> to_erase;
00357 
00358           for_all_(std::list<unsigned>, p, met_class)
00359           {
00360             // if all states are predecessors there is no needed split
00361             if (count_for_[*p] == part[*p].size())
00362               continue;
00363 
00364             twin_[*p] = max_partitions;
00365             unsigned twin_class = max_partitions;
00366             ++max_partitions;
00367             partition_t::iterator q;
00368             int i = 0;
00369             for (partition_t::iterator next = part[*p].begin();
00370                  next != part[*p].end();)
00371             {
00372               q = next;
00373               ++next;
00374               if (going_in_[*q])
00375               {
00376                 class_[*q] = twin_class;
00377                 part[twin_class].insert(part[twin_class].end(), *q);
00378                 part[*p].erase(q);
00379                 i++;
00380               }
00381             }
00382           }
00383 
00384           for_all_(std::list<unsigned>, p, met_class)
00385           {
00386             count_for_[*p] = 0;
00387             twin_[*p] = 0;
00388           }
00389           met_class.clear();
00390         }
00391 
00392       private:
00393         const automaton_t& input_;
00394         class_of_t& class_;
00395         std::vector<unsigned> count_for_;
00396         std::vector<unsigned> twin_;
00397         going_in_t going_in_;
00398         std::list<unsigned> met_class;
00399       };
00400 
00401     }
00402   }
00403 
00404   template <typename A, typename input_t, typename output_t>
00405   void
00406   do_quotient(const AutomataBase<A>&,
00407               const algebra::NumericalSemiring&,
00408               SELECTOR(bool),
00409               output_t&                 output,
00410               const input_t&            input)
00411   {
00412     AUTOMATON_TYPES(input_t);
00413     AUTOMATON_FREEMONOID_TYPES(input_t);
00414     QUOTIENT_TYPES();
00415 
00416     using namespace internal::hopcroft_minimization_undet;
00417 
00418     const alphabet_t& alphabet_(input.series().monoid().alphabet());
00419     unsigned max_states = 0;
00420 
00421     for_all_states(i, input)
00422       max_states = std::max(unsigned(*i), max_states);
00423     ++max_states;
00424     // to avoid special case problem (one state initial and final ...)
00425     max_states = std::max(max_states, 2u);
00426 
00427     /*--------------------------.
00428     | To label the subsets of Q |
00429     `--------------------------*/
00430     unsigned max_partitions = 2;
00431 
00432     /*-----------------------------------------.
00433     | To manage efficiently the partition of Q |
00434     `-----------------------------------------*/
00435     class_of_t          class_(max_states);
00436     partition_set_t     part(max_states);
00437 
00438     /*-------------------------.
00439     | To have a list of (P, a) |
00440     `-------------------------*/
00441     typedef std::pair<unsigned, letter_t> pair_t;
00442     std::list<pair_t>   to_treat;
00443 
00444     /*-------------------------.
00445     | Initialize the partition |
00446     `-------------------------*/
00447 
00448     for_all_states (p, input)
00449     {
00450       unsigned c = input.is_final(*p) ? 1 : 0;
00451       class_[*p] = c;
00452       part[c].insert(part[c].end(), *p);
00453     }
00454 
00455     /*------------------------------.
00456     | Initialize the list of (P, a) |
00457     `------------------------------*/
00458 
00459     for_all_letters (e, alphabet_)
00460       to_treat.push_back(pair_t(0, *e));
00461 
00462     for_all_letters (e, alphabet_)
00463       to_treat.push_back(pair_t(1, *e));
00464 
00465     /*----------.
00466     | Main loop |
00467     `----------*/
00468     {
00469       quotient_splitter<input_t> splitter(input, class_, max_states);
00470       while (!to_treat.empty())
00471       {
00472         pair_t c = to_treat.front();
00473         to_treat.pop_front();
00474         unsigned p = c.first;
00475         letter_t a = c.second;
00476         unsigned old_max_partitions = max_partitions;
00477 
00478         if (!splitter.compute_going_in_states(part[p], a))
00479           continue;
00480         splitter.split(part, max_partitions);
00481 
00482         for (unsigned c = old_max_partitions; c < max_partitions; ++c)
00483           for_all_letters (e, alphabet_)
00484             to_treat.push_back(pair_t(c, *e));
00485       }
00486     }
00487 
00488     /*------------------------------------.
00489     | Construction of the ouput automaton |
00490     `------------------------------------*/
00491     // Create the states
00492     for (unsigned i = 0; i < max_partitions; ++i)
00493       output.add_state();
00494 
00495     delta_ret_t delta_ret;
00496     std::set<unsigned> already_linked;
00497     for (unsigned i = 0; i < max_partitions; ++i)
00498     {
00499       // Get the first state of the partition => each state has the
00500       // same behaviour
00501       hstate_t s = part[i].front();
00502 
00503       if (input.is_final(s))
00504         output.set_final(i);
00505 
00506       // Create the transitions
00507       for_all_letters (e, alphabet_)
00508       {
00509         delta_ret.clear();
00510         already_linked.clear();
00511 
00512         input.letter_deltac(delta_ret, s, *e, delta_kind::states());
00513         for_all_(delta_ret_t, out, delta_ret)
00514         {
00515           unsigned c = class_[*out];
00516           if (already_linked.find(c) == already_linked.end())
00517           {
00518             already_linked.insert(c);
00519             output.add_letter_transition(i, c, *e);
00520           }
00521         }
00522       }
00523     }
00524 
00525     // Set initial states.
00526     for_all_initial_states(i, input)
00527       output.set_initial(class_[*i]);
00528   }
00529 
00530 # undef QUOTIENT_TYPES
00531 
00532 
00533   /*----------------------------------------.
00534   | Quotient with multiplicities (covering) |
00535   `----------------------------------------*/
00536 
00537   template <class S, class T,
00538             typename A, typename input_t, typename output_t>
00539   void
00540   do_quotient(const AutomataBase<A>&    ,
00541               const S&                  ,
00542               const T&                  ,
00543               output_t&                 output,
00544               const input_t&            input)
00545   {
00546     AUTOMATON_TYPES(input_t);
00547     AUTOMATON_FREEMONOID_TYPES(input_t);
00548     using namespace std;
00549 
00550     /*----------------------------------------.
00551     | Declare data structures and variables.  |
00552     `----------------------------------------*/
00553 
00554     typedef set<htransition_t>                       set_transitions_t;
00555     typedef set<hstate_t>                      set_states_t;
00556     typedef set<semiring_elt_t>                set_semiring_elt_t;
00557     typedef vector<semiring_elt_t>             vector_semiring_elt_t;
00558     typedef pair<unsigned, letter_t>           pair_class_letter_t;
00559     typedef pair<hstate_t, semiring_elt_t>     pair_state_semiring_elt_t;
00560     typedef set<pair_state_semiring_elt_t>     set_pair_state_semiring_elt_t;
00561     typedef map<semiring_elt_t, unsigned>      map_semiring_elt_t;
00562 
00563     series_set_elt_t    null_series     = input.series().zero_;
00564     semiring_elt_t      weight_zero     = input.series().semiring().wzero_;
00565     monoid_elt_t        monoid_identity = input.series().monoid().vcsn_empty;
00566     const alphabet_t&   alphabet (input.series().monoid().alphabet());
00567 
00568     queue<pair_class_letter_t>                          the_queue;
00569 
00570     set<unsigned>       met_classes;
00571     set_transitions_t           transitions_leaving;
00572 
00573     unsigned    max_partition   = 0;
00574     //     unsigned     max_letters     = alphabet.size();
00575     unsigned    max_states      = 0;
00576 
00577     for_all_states(q, input)
00578       max_states = std::max(unsigned (*q), max_states);
00579     ++max_states;
00580     // Avoid special case problem (one initial and final state...)
00581     max_states = std::max(max_states, 2u);
00582 
00583     vector< vector<set_pair_state_semiring_elt_t> > inverse (max_states);
00584 
00585     map<letter_t, unsigned> pos_of_letter;
00586     {
00587       unsigned pos (0);
00588 
00589       for_all_letters(a, alphabet)
00590         pos_of_letter[*a] = pos++;
00591     }
00592 
00593     set_states_t                states_visited;
00594     set_semiring_elt_t          semiring_had_class;
00595     vector<set_states_t>        classes (max_states);
00596     vector<unsigned>            class_of_state (max_states);
00597     vector_semiring_elt_t       old_weight (max_states);
00598     map_semiring_elt_t          class_of_weight;
00599 
00600     for(unsigned i = 0; i < max_states; ++i)
00601       inverse[i].resize(max_states);
00602 
00603     for_all_states(q, input)
00604       for_all_letters(a, alphabet)
00605       {
00606 
00607         for_all_const_(set_states_t, r, states_visited)
00608           old_weight[*r] = weight_zero;
00609         states_visited.clear();
00610 
00611         set_transitions_t transitions_comming;
00612         input.letter_rdeltac(transitions_comming, *q, *a,
00613                              delta_kind::transitions());
00614 
00615         for_all_const_(set_transitions_t, e, transitions_comming)
00616           {
00617             hstate_t            p = input.src_of(*e);
00618             if (states_visited.find(p) != states_visited.end())
00619               inverse[*q][pos_of_letter[*a]].
00620                 erase(pair_state_semiring_elt_t (p, old_weight[p]));
00621             else
00622               states_visited.insert(p);
00623             series_set_elt_t    sd = input.series_of(*e);
00624             monoid_elt_t        md (input.structure().series().monoid(), *a);
00625             semiring_elt_t      wsd = sd.get(md);
00626             old_weight[p] += wsd;
00627             inverse[*q][pos_of_letter[*a]].
00628               insert(pair_state_semiring_elt_t (p, old_weight[p]));
00629           }
00630       }
00631 
00632     /*-----------------------------------------------------------.
00633     | Initialize the partition with as many classes as there are |
00634     | final values.                                              |
00635     `-----------------------------------------------------------*/
00636 
00637     bool         empty = true;
00638     unsigned     class_non_final (0);
00639 
00640     for_all_states(q, input)
00641       {
00642         if (not input.is_final(*q))
00643         {
00644           if (empty == true)
00645           {
00646             empty = false;
00647             class_non_final = max_partition;
00648             max_partition++;
00649           }
00650           classes[class_non_final].insert(*q);
00651           class_of_state[*q] = class_non_final;
00652         }
00653         else
00654         {
00655           semiring_elt_t w = input.get_final(*q).get(monoid_identity);
00656           if (semiring_had_class.find(w) == semiring_had_class.end())
00657           {
00658             semiring_had_class.insert(w);
00659             classes[max_partition].insert(*q);
00660             class_of_weight[w] = max_partition;
00661             class_of_state[*q] = max_partition;
00662             max_partition++;
00663           }
00664           else
00665           {
00666             classes[class_of_weight[w]].insert(*q);
00667             class_of_state[*q] = class_of_weight[w];
00668           }
00669         }
00670       }
00671 
00672     /*-----------------------------------------------------.
00673     | Initialize the queue with pairs <class_id, letter>.  |
00674     `-----------------------------------------------------*/
00675 
00676     for (unsigned i = 0; i < max_partition; i++)
00677       for_all_letters(a, alphabet)
00678         the_queue.push(pair_class_letter_t (i, *a));
00679 
00680     /*----------------.
00681     | The main loop.  |
00682     `----------------*/
00683 
00684     unsigned old_max_partition = max_partition;
00685 
00686     while(not the_queue.empty())
00687     {
00688       pair_class_letter_t pair = the_queue.front();
00689       the_queue.pop();
00690       //val.clear(); // FIXME: Is this line necessary?
00691       met_classes.clear();
00692       vector_semiring_elt_t val (max_states);
00693 
00694       for_all_states(q, input)
00695         val[*q] = 0;
00696 
00697       // First, calculcate val[state] and note met_classes.
00698       for_all_const_(set_states_t, q, classes[pair.first])
00699         for_all_const_(set_pair_state_semiring_elt_t, pair_,
00700                        inverse[*q][pos_of_letter[pair.second]])
00701         {
00702           unsigned  state = pair_->first;
00703           if (met_classes.find(class_of_state[state]) ==
00704               met_classes.end())
00705             met_classes.insert(class_of_state[state]);
00706           val[state] += pair_->second;
00707         }
00708 
00709       // Next, for each met class, do the partition.
00710       for_all_const_(set<unsigned>, class_id, met_classes)
00711       {
00712         if (classes[*class_id].size() == 1)
00713           continue ;
00714 
00715         queue<hstate_t> to_erase;
00716         semiring_elt_t  next_val;
00717         semiring_elt_t  first_val = val[*(classes[*class_id].begin())];
00718         class_of_weight.clear();
00719         semiring_had_class.clear();
00720 
00721         for_all_const_(set_states_t, p, classes[*class_id])
00722         {
00723           next_val = val[*p];
00724           // This state must be moved to another class!
00725           if (next_val != first_val)
00726           {
00727             if (semiring_had_class.find(next_val) ==
00728                 semiring_had_class.end()) // Must create a new class
00729             {
00730               classes[max_partition].insert(*p);
00731               class_of_state[*p] = max_partition;
00732               semiring_had_class.insert(next_val);
00733               class_of_weight[next_val] = max_partition;
00734               max_partition++;
00735             }
00736             else
00737             {
00738               classes[class_of_weight[next_val]].insert(*p);
00739               class_of_state[*p] = class_of_weight[next_val];
00740             }
00741             to_erase.push(*p);
00742           }
00743         }
00744 
00745         while(not to_erase.empty())
00746         {
00747           hstate_t s = to_erase.front();
00748           to_erase.pop();
00749           classes[*class_id].erase(s);
00750         }
00751 
00752         // Push pairs <new_class_id, letter> into the queue.
00753         for (unsigned i = old_max_partition; i < max_partition; i++)
00754           for_all_letters(b, alphabet)
00755             the_queue.push(pair_class_letter_t(i, *b));
00756         old_max_partition = max_partition;
00757       }
00758     }
00759 
00760     /*------------------.
00761     | Form the output.  |
00762     `------------------*/
00763 
00764     typedef vector<series_set_elt_t> vector_series_set_elt_t;
00765 
00766     std::vector<hstate_t>       out_states (max_partition);
00767 
00768     // typedef map<unsigned, series_set_elt_t> map_class_series_elt_t;
00769     // map_class_series_elt_t   seriesof;
00770 
00771     // Add states.
00772     for(unsigned i = 0; i < max_partition; i++)
00773     {
00774       out_states[i]  = output.add_state();
00775       hstate_t a_state = *classes[i].begin();
00776       series_set_elt_t a_serie = null_series;
00777 
00778       for_all_const_(set_states_t, state, classes[i])
00779         if(input.is_initial(*state))
00780           a_serie += input.get_initial(*state);
00781 
00782       output.set_initial(out_states[i] , a_serie);
00783 
00784       if (input.is_final(a_state))
00785         output.set_final(out_states[i] , input.get_final(a_state));
00786     }
00787 
00788     // Add transitions.
00789     vector_series_set_elt_t seriesof (max_partition, null_series);
00790 
00791     for(unsigned i = 0; i < max_partition; i++)
00792     {
00793       met_classes.clear();
00794 
00795       transitions_leaving.clear();
00796       input.deltac(transitions_leaving, *classes[i].begin(),
00797                    delta_kind::transitions());
00798 
00799       for_all_const_(set_transitions_t, e, transitions_leaving)
00800         {
00801           series_set_elt_t      se = input.series_of(*e);
00802           unsigned              cs = class_of_state[input.dst_of(*e)];
00803 
00804           if (met_classes.find(cs) == met_classes.end())
00805           {
00806             met_classes.insert(cs);
00807             seriesof[cs] = se;
00808           }
00809           else
00810             seriesof[cs] += se;
00811         }
00812 
00813       for_all_const_(set<unsigned>, cs, met_classes)
00814         output.add_series_transition(out_states[i],
00815                                      out_states[*cs],
00816                                      seriesof[*cs]);
00817     }
00818   }
00819 
00820   template<typename A, typename T>
00821   Element<A, T>
00822   quotient(const Element<A, T>& a)
00823   {
00824     TIMER_SCOPED ("quotient");
00825     typedef Element<A, T> auto_t;
00826     AUTOMATON_TYPES(auto_t);
00827     Element<A, T> output(a.structure());
00828     do_quotient(a.structure(), a.structure().series().semiring(),
00829                 SELECT(semiring_elt_value_t), output, a);
00830     return output;
00831   }
00832 
00833 } // vcsn
00834 
00835 #endif // ! VCSN_ALGORITHMS_MINIMIZATION_HOPCROFT_HXX

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