3 #include <boost/heap/fibonacci_heap.hpp>
23 template <
typename Aut>
90 template <
typename Aut>
143 res = rat::make_info<expset_t>(
aut_->weight_of(t)).atom;
145 res = rat::size<expset_t>(
aut_->weight_of(t));
172 size_t size_loop = 0;
193 p.
size_ = (size_in * (outs - 1)
194 + size_out * (ins - 1)
195 + size_loop * (ins * outs - 1));
211 template <
typename Aut,
typename Profiler>
224 for (
auto s:
aut_->states())
231 if (s ==
aut_->null_state())
234 auto p =
todo_.top();
239 require(
aut_->has_state(s),
"not a valid state: ", s);
246 while (!
todo_.empty())
248 auto p =
todo_.top();
252 std::cerr <<
"Remove: " << p << std::endl;
262 std::cerr <<
"update heap: (";
266 if (s !=
aut_->pre() && s !=
aut_->post())
273 std::cerr <<
") => ";
275 std::cerr << std::endl;
282 const char* sep =
"";
283 for (
auto i =
todo_.ordered_begin(), end =
todo_.ordered_end();
286 std::cerr << sep << *i;
292 template <typename Kind = typename context_t_of<automaton_t>::kind_t>
300 const auto& ws_ = *
aut_->weightset();
303 auto loop = ws_.zero();
304 assert(
aut_->outin(s, s).size() <= 1);
309 loop = ws_.add(loop,
aut_->weight_of(t));
310 aut_->del_transition(t);
312 loop = ws_.star(loop);
315 auto outs =
aut_->all_out(s);
316 for (
auto in:
aut_->all_in(s))
319 auto src =
aut_->src_of(in);
320 auto dst =
aut_->dst_of(out);
321 auto t =
aut_->add_transition
324 ws_.mul(
aut_->weight_of(in), loop,
aut_->weight_of(out)));
344 template <
typename Kind>
352 const auto& rs_ = *
aut_->labelset();
355 auto loop = rs_.zero();
359 rs_.lmul(
aut_->weight_of(t),
aut_->label_of(t)));
360 aut_->del_transition(t);
362 loop = rs_.star(loop);
365 auto outs =
aut_->all_out(s);
366 for (
auto in:
aut_->all_in(s))
369 auto src =
aut_->src_of(in);
370 auto dst =
aut_->dst_of(out);
371 auto t =
aut_->add_transition
373 rs_.mul(rs_.lmul(
aut_->weight_of(in),
aut_->label_of(in)),
375 rs_.lmul(
aut_->weight_of(out),
aut_->label_of(out))));
391 using heap_t = boost::heap::fibonacci_heap<profile_t>;
394 std::vector<typename heap_t::handle_type>
handles_;
399 template <
typename Aut,
typename Profiler>
409 template <
typename Aut>
422 template <
typename Aut>
430 auto res = make_fresh_automaton<Aut>(aut);
433 if (s != aut->null_state())
435 require(aut->has_state(s),
"not a valid state: ", s);
436 s = copy.state_map().at(s);
451 template <
typename Aut,
typename Int>
455 const auto& a = aut->as<Aut>();
456 auto s = 0 <= state ? state + 2 : a->null_state();
467 template <
typename Aut,
469 typename ExpSet = expressionset<context_t_of<Aut>>>
470 typename ExpSet::value_t
475 return a->get_initial_weight(a->post());
486 template <
typename Aut,
487 typename ExpSet = expressionset<context_t_of<Aut>>>
488 typename ExpSet::value_t
493 auto a =
lift(aut, ids);
499 raise(
"next_state: invalid algorithm: best");
503 auto profiler = delgado_t(a);
504 return to_expression<decltype(a), delgado_t, ExpSet>(a, profiler);
509 auto profiler = delgado_t(a,
true);
510 return to_expression<decltype(a), delgado_t, ExpSet>(a, profiler);
515 auto profiler = naive_t(a);
516 return to_expression<decltype(a), naive_t, ExpSet>(a, profiler);
522 template <
typename Aut,
523 typename ExpSet = expressionset<context_t_of<Aut>>>
524 typename ExpSet::value_t
530 typename ExpSet::value_t
best;
531 auto best_size = std::numeric_limits<size_t>::max();
536 auto r = to_expression_heuristic<Aut, ExpSet>(aut,
ids, a);
537 auto s = rat::size<ExpSet>(
r);
548 return to_expression_heuristic<Aut, ExpSet>(aut,
ids, algo);
552 template <
typename Aut,
553 typename ExpSet = expressionset<context_t_of<Aut>>>
554 typename ExpSet::value_t
556 const std::string& algo)
558 static const auto map = std::map<std::string, to_expression_heuristic_t>
566 return to_expression<Aut, ExpSet>(a,
ids,
getargs(
"algorithm", map, algo));
578 template <
typename Aut,
typename Identities,
typename String>
581 const std::string& algo)
583 const auto& a = aut->as<Aut>();
586 auto rs = expressionset_t{a->context(), ids};
602 template <
typename Context,
typename Identities,
typename Label>
607 const auto& c = ctx->as<Context>();
608 const auto& l = lbl->as<Label>();
622 template <
typename ExpSet>
625 std::false_type, std::true_type)
626 ->
typename ExpSet::value_t
628 raise(
"letter_class: not implemented (is_expressionset)");
631 template <
typename ExpSet>
634 std::false_type, std::false_type)
635 ->
typename ExpSet::value_t
637 auto ls = *
rs.labelset();
639 using labelset_t = decltype(ls);
640 using letter_t =
typename labelset_t::letter_t;
642 auto ccs = std::set<std::pair<letter_t, letter_t>>{};
643 for (
const auto& cc: chars)
645 std::istringstream i1{cc.first};
646 std::istringstream i2{cc.second};
647 letter_t l1 = ls.get_letter(i1,
false);
648 letter_t l2 = ls.get_letter(i2,
false);
651 return rs.letter_class(ccs, accept);
654 template <
typename ExpSet>
657 std::true_type, std::false_type)
658 ->
typename ExpSet::value_t
673 template <
typename ExpressionSet>
674 typename ExpressionSet::value_t
679 using is_one_t = std::is_same<labelset_t, vcsn::oneset>;
682 is_one_t{}, is_expset_t{});
690 template <
typename Context,
typename Identities,
691 typename Letters,
typename Bool>
696 const auto& c = ctx->as<Context>();
std::vector< typename Cont::value_type > make_vector(const Cont &cont)
The content of cont as a vector.
state_t_of< automaton_t > state_t
size_t size_of_transition(transition_t t)
The "weight" of a transition.
expression to_expression(const automaton &aut, vcsn::rat::identities ids, const std::string &algo)
Bridge.
detail::lifted_automaton_t< Aut, Tapes...> lift(const Aut &a, vcsn::rat::identities ids={})
Lift some tapes of the transducer.
void operator()(state_t s)
Eliminate state s.
void invalidate_cache(transition_t)
std::shared_ptr< const detail::label_base > label
void show_heap_() const
Show the heap, for debugging.
weightset_mixin< detail::r_impl > r
ExpressionSet::value_t to_expression(const ExpressionSet &rs, const letter_class_t &letters, bool accept=true)
An expression matching one letter in a letter class.
std::shared_ptr< const detail::context_base > context
A dyn::context.
std::vector< size_t > transition_cache_
void operator()()
Eliminate all the states, in the order specified by next_state.
Container::value_type back(const Container &container)
The last member of this Container.
automaton_t aut_
The automaton we work on.
detail::copier< AutIn, AutOut > make_copier(const AutIn &in, AutOut &out)
Build an automaton copier.
expression to_expression_class(const context &ctx, rat::identities ids, const letter_class_t &letters, bool accept)
Bridge (to_expression).
std::string type(const automaton &a)
The implementation type of a.
C::mapped_type getargs(const std::string &kind, const C &map, const std::string &key)
Find a correspondance in a map.
state_profile make_state_profile(state_t state)
typename detail::context_t_of_impl< base_t< ValueSet >>::type context_t_of
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
std::set< std::pair< std::string, std::string >> letter_class_t
A set of letter ranges.
typename std::enable_if< Cond, T >::type enable_if_t
Aut & eliminate_state_here(Aut &res, state_t_of< Aut > s=Aut::element_type::null_state())
In place removal of state s from automaton res.
void invalidate_cache(transition_t t)
Updating transitions' size in the cache during the profiler's construction would be clearer but appea...
Eliminate states in an automaton whose labelset is oneset.
state_eliminator(automaton_t &aut, profiler_t &profiler)
naive_profiler(const automaton_t &aut)
expression to_expression_label(const context &ctx, rat::identities ids, const label &lbl)
Bridge (to_expression).
automaton eliminate_state(const automaton &aut, int state)
Bridge.
automaton make_automaton(const Aut &aut)
Build a dyn::automaton.
static dyn::context ctx(const driver &d)
Get the context of the driver.
AutOut copy(const AutIn &input, KeepState keep_state, KeepTrans keep_trans)
A copy of input keeping only its states that are accepted by keep_state.
auto eliminate_state_(state_t s) -> enable_if_t< std::is_same< Kind, labels_are_one >::value, void >
Eliminate state s in the case of labels are one.
bool operator<(const state_profile &rhs) const
ExpSet::value_t to_expression_heuristic(const Aut &aut, vcsn::rat::identities ids, to_expression_heuristic_t algo)
Provide a variadic mul on top of a binary mul(), and one().
boost::heap::fibonacci_heap< profile_t > heap_t
Max-heap to decide the order of state-elimination.
auto letter_class_impl(const ExpSet &, const letter_class_t &, bool, std::false_type, std::true_type) -> typename ExpSet::value_t
friend std::ostream & operator<<(std::ostream &o, const state_profile &p)
std::shared_ptr< detail::automaton_base > automaton
static identities ids(const driver &d)
Get the identities of the driver.
void update(state_profile &p)
The "weight" of a state, as defined by Delgado/Morais.
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
auto eliminate_state(const Aut &aut, state_t_of< Aut > s=Aut::element_type::null_state()) -> fresh_automaton_t_of< Aut >
A copy of automaton res without the state s.
transition_t_of< automaton_t > transition_t
void require(bool b, Args &&...args)
If b is not verified, raise an error with args as message.
typename profiler_t::state_profile profile_t
void update(state_profile &p)
typename detail::transition_t_of_impl< base_t< ValueSet >>::type transition_t_of
expressionset< Context > make_expressionset(const Context &ctx, rat::identities identities={})
Shorthand to expressionset constructor.
state_profile(state_t state)
An expressionset can implement several different sets of identities on expressions.
expression make_expression(const ExpSet &rs, const typename ExpSet::value_t &r)
typename std::remove_cv< Aut >::type automaton_t
ExpSet::value_t to_expression(Aut &a, Profiler &profiler)
state_profile make_state_profile(state_t state)
std::shared_ptr< detail::expression_base > expression
state_t_of< automaton_t > state_t
state_t_of< automaton_t > state_t
std::integral_constant< bool, B > bool_constant
auto eliminate_state_impl_(state_t s) -> enable_if_t< std::is_same< Kind, labels_are_expressions >::value, void >
Eliminate state s in the case of labels are expressions.
state_eliminator< Aut, Profiler > make_state_eliminator(Aut &a, Profiler &profiler)
state_profile(state_t state)
std::vector< typename heap_t::handle_type > handles_
Map: state -> heap-handle.
#define BUILTIN_UNREACHABLE()
std::unordered_set< state_t > neighbors_
bool operator<(const state_profile &rhs) const
transition_t_of< automaton_t > transition_t
delgado_profiler(const automaton_t &aut, bool count_labels=false)
friend std::ostream & operator<<(std::ostream &o, const state_profile &p)
to_expression_heuristic_t
profiler_t & profiler_
The profiler we work with. Corresponding to a specific heuristic.