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

Generated on Sat Jul 29 17:13:09 2006 for Vaucanson by  doxygen 1.4.6