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