5 #include <unordered_map>
6 #include <unordered_set>
10 #include <boost/heap/fibonacci_heap.hpp>
14 #include <vcsn/algos/fwd.hh>
34 template <
typename Aut,
35 bool has_one = labelset_t_of<Aut>::has_one()>
41 using weight_t =
typename weightset_t::value_t;
60 ,
ws_(*aut->weightset())
62 ,
d2p_(aut->all_states().
back() + 1, aut->null_state())
63 ,
p2d_(aut->all_states().
back() + 1, aut->null_state())
67 aut_dirty_ = make_shared_ptr<aut_dirty_t>(dirty_ctx);
68 aut_proper_ = make_shared_ptr<aut_proper_t>(proper_ctx);
73 pcopier([](
state_t) {
return true; },
75 return !aut->labelset()->is_one(aut->label_of(t));
79 return (!aut->in(s, aut->labelset()->one()).empty()
80 || !aut->out(s, aut->labelset()->one()).empty());
83 return aut->labelset()->is_one(aut->label_of(t));
87 const auto& dorigins = dcopier.state_map();
88 const auto& porigins = pcopier.state_map();
89 for (
const auto& dp : dorigins)
91 auto pp = porigins.find(dp.first);
92 assert(pp != porigins.end());
93 d2p_[dp.second] = pp->second;
94 p2d_[pp->second] = dp.second;
104 if (
auto p =
profile(proper_s))
106 auto in_dirty =
aut_dirty_->in(dirty_s).size();
108 auto out_dirty =
aut_dirty_->out(dirty_s).size();
109 auto out_proper =
aut_proper_->all_out(proper_s).size();
111 p->update(in_dirty, in_proper + in_dirty,
112 out_dirty, out_proper + out_dirty);
125 auto proper_s =
d2p_[s];
127 {proper_s, 0, 0, 0, 0});
136 const char* sep =
"";
137 for (
auto i =
todo_.ordered_begin(), end =
todo_.ordered_end();
140 std::cerr << sep << *i;
151 std::cerr <<
"update heap (" << s <<
" : ";
156 todo_.update(i->second);
159 std::cerr <<
") => ";
161 std::cerr << std::endl;
201 using state_weight_t = std::pair<state_t, weight_t>;
202 std::vector<state_weight_t> closure;
203 for (
auto t : transitions)
208 star =
ws_.star(weight);
210 closure.emplace_back(src, weight);
238 for (
auto pair: closure)
253 for (
auto pair: closure)
261 unsigned added = (
aut_proper_->all_out(proper_s).size()
262 +
aut_dirty_->out(dirty_s).size()) * closure.size();
263 unsigned removed = transitions.size();
280 std::cerr <<
" -" << removed <<
"+" << added
281 <<
" (-" << removed_ <<
"+" << added_ <<
")";
314 std::unordered_set<state_t> neighbors;
315 while (!
todo_.empty())
319 std::cerr <<
"Before: ";
321 std::cerr << std::endl;
323 auto p =
todo_.top();
326 std::cerr <<
"Remove: " << p;
328 auto proper_s = p.state;
329 auto dirty_s =
p2d_[proper_s];
335 neighbors.emplace(n);
338 neighbors.emplace(n);
344 neighbors.emplace(
d2p_[n]);
347 neighbors.emplace(
d2p_[n]);
353 for (
auto n: neighbors)
355 for (
auto n: neighbors)
358 std::cerr <<
" #tr: "
365 std::cerr <<
"After: ";
367 std::cerr << std::endl;
375 std::cerr << std::endl;
379 std::cerr <<
"Total transitions -" << removed_
380 <<
"+" << added_ << std::endl;
398 using heap_t = boost::heap::fibonacci_heap<epsilon_profile<state_t>>;
401 std::unordered_map<state_t, typename heap_t::handle_type>
handles_;
410 template <
typename Aut>
labelset_t_of< automaton_t > labelset_t
std::unordered_map< state_t, typename heap_t::handle_type > handles_
Map: state -> heap-handle.
void update_heap_(state_t s)
Update the heap for s.
static int debug_level()
Debug level set in the user's environment.
aut_proper_t operator()()
typename detail::label_t_of_impl< base_t< ValueSet >>::type label_t_of
std::shared_ptr< const detail::label_base > label
aut_proper_t aut_proper_
The automata we work on.
transition_t_of< automaton_t > transition_t
Container::value_type back(const Container &container)
The last member of this Container.
void remover_on(state_t dirty_s, state_t proper_s)
For each state (s), for each incoming epsilon-transitions (t), if (t) is a loop, the star of its weig...
detail::copier< AutIn, AutOut > make_copier(const AutIn &in, AutOut &out)
Build an automaton copier.
void update_profile_(state_t proper_s)
Update the profile of s.
label_t_of< aut_proper_t > label_proper_t
std::string type(const automaton &a)
The implementation type of a.
epsilon_profile< state_t > * profile(state_t s)
state_t_of< automaton_t > state_t
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
weightset_t_of< automaton_t > weightset_t
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
This is used by some epsilon removal algorithms.
epsilon_remover_separate(const automaton_t &aut, bool)
std::vector< state_t > d2p_
typename Aut::element_type::template fresh_automaton_t< Context > fresh_automaton_t_of
int debug_
Debug level. The higher, the more details are reported.
auto make_proper_context(const context< LabelSet, WeightSet > &ctx) -> proper_context< context< LabelSet, WeightSet >>
From a context, its non-nullable context.
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.
std::shared_ptr< const detail::weight_base > weight
void show_heap_() const
Show the heap, for debugging.
aut_proper_t operator()()
Remove all the states with incoming spontaneous transitions.
boost::heap::fibonacci_heap< epsilon_profile< state_t >> heap_t
Max-heap to decide the order of state-elimination.
mutable_automaton< dirty_ctx_t > aut_dirty_t
const weightset_t & ws_
Shorthand to the weightset.
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
std::vector< transition_t > transitions_t
fresh_automaton_t_of< automaton_t > aut_proper_t
fresh_automaton_t_of< Aut, proper_ctx_t > aut_proper_t
typename std::remove_cv< Aut >::type automaton_t
typename detail::transition_t_of_impl< base_t< ValueSet >>::type transition_t_of
bool prune_
Whether to prune states that become inaccessible.
typename std::remove_cv< Aut >::type automaton_t
pair_automaton< Aut > pair(const Aut &aut, bool keep_initials=false)
void build_heap_()
Build the profiles and the heap for states with incoming spontaneous transitions. ...
std::ostream & dot(const Aut &aut, std::ostream &out, bool dot2tex=false)
This class contains the core of the proper algorithm.
typename weightset_t::value_t weight_t
std::vector< state_t > p2d_
epsilon_remover_separate(const automaton_t &aut, bool prune=true)
Get ready to eliminate spontaneous transitions.
std::shared_ptr< detail::mutable_automaton_impl< Context >> mutable_automaton