![]() |
Vcsn
2.1
Be Rational
|
This class contains the core of the proper algorithm. More...
#include <epsilon-remover.hh>
Public Member Functions | |
epsilon_remover (automaton_t &aut, bool prune=true) | |
Get ready to eliminate spontaneous transitions. More... | |
aut_proper_t | operator() () |
Private Types | |
using | automaton_t = Aut |
using | state_t = state_t_of< automaton_t > |
using | weightset_t = weightset_t_of< automaton_t > |
using | weight_t = typename weightset_t::value_t |
using | labelset_t = labelset_t_of< automaton_t > |
using | label_t = label_t_of< automaton_t > |
using | transition_t = transition_t_of< automaton_t > |
using | aut_proper_t = fresh_automaton_t_of< automaton_t, detail::proper_context< context_t_of< automaton_t >>> |
using | heap_t = boost::heap::fibonacci_heap< epsilon_profile< state_t >> |
Max-heap to decide the order of state-elimination. More... | |
Private Member Functions | |
void | update_profile_ (state_t s) |
The core of the (backward) epsilon-removal. More... | |
void | build_heap_ () |
Build the profiles and the heap for states with incoming spontaneous transitions. More... | |
void | show_heap_ () const |
Show the heap, for debugging. More... | |
void | update_heap_ (state_t s) |
Update the heap for s. More... | |
epsilon_profile< state_t > * | profile (state_t s) |
void | in_situ_remover_ (state_t s) |
For each state (s), for each incoming epsilon-transitions (t), if (t) is a loop, the star of its weight is computed, otherwise, (t) is stored into the closure list. More... | |
void | in_situ_remover_ () |
Remove all the states with incoming spontaneous transitions. More... | |
size_t | num_spontaneous_transitions_ () const |
The number of spontaneous transitions in aut_. More... | |
Private Attributes | |
unsigned | added_ = 0 |
unsigned | removed_ = 0 |
int | debug_ |
Debug level. The higher, the more details are reported. More... | |
automaton_t | aut_ |
The automaton we work on. More... | |
const weightset_t & | ws_ |
Shorthand to the weightset. More... | |
label_t | empty_word_ |
Shorthand to the empty word. More... | |
heap_t | todo_ |
std::unordered_map< state_t, typename heap_t::handle_type > | handles_ |
Map: state -> heap-handle. More... | |
bool | prune_ |
Whether to prune states that become inaccessible. More... | |
This class contains the core of the proper algorithm.
This class is specialized for labels_are_letter automata since all these methods become trivial.
Definition at line 38 of file epsilon-remover.hh.
|
private |
Definition at line 49 of file epsilon-remover.hh.
|
private |
Definition at line 40 of file epsilon-remover.hh.
|
private |
Max-heap to decide the order of state-elimination.
Definition at line 369 of file epsilon-remover.hh.
|
private |
Definition at line 45 of file epsilon-remover.hh.
|
private |
Definition at line 44 of file epsilon-remover.hh.
|
private |
Definition at line 41 of file epsilon-remover.hh.
|
private |
Definition at line 46 of file epsilon-remover.hh.
|
private |
Definition at line 43 of file epsilon-remover.hh.
|
private |
Definition at line 42 of file epsilon-remover.hh.
|
inline |
Get ready to eliminate spontaneous transitions.
aut | the automaton in which to remove them |
prune | whether to delete states that become inaccessible |
Definition at line 55 of file epsilon-remover.hh.
|
inlineprivate |
Build the profiles and the heap for states with incoming spontaneous transitions.
Definition at line 119 of file epsilon-remover.hh.
References vcsn::detail::epsilon_remover< Aut, has_one >::aut_, vcsn::detail::epsilon_remover< Aut, has_one >::empty_word_, vcsn::detail::epsilon_remover< Aut, has_one >::handles_, and vcsn::detail::epsilon_remover< Aut, has_one >::todo_.
Referenced by vcsn::detail::epsilon_remover< Aut, has_one >::in_situ_remover_().
|
inlineprivate |
For each state (s), for each incoming epsilon-transitions (t), if (t) is a loop, the star of its weight is computed, otherwise, (t) is stored into the closure list.
Then (t) is removed.
Because it is sometimes useful to be able to invoke proper on a single state, we kept this function free from any relation with the profiles and the heap.
For some reason, we get poorer performances if this function is moved higher, before the epsilon_profile definition.
Definition at line 193 of file epsilon-remover.hh.
References vcsn::detail::epsilon_remover< Aut, has_one >::aut_, vcsn::detail::epsilon_remover< Aut, has_one >::debug_, vcsn::detail::epsilon_remover< Aut, has_one >::empty_word_, vcsn::detail::make_vector(), vcsn::pair(), vcsn::detail::epsilon_remover< Aut, has_one >::prune_, and vcsn::detail::epsilon_remover< Aut, has_one >::ws_.
|
inlineprivate |
Remove all the states with incoming spontaneous transitions.
Set-up and maintain a heap to process states in an order that attempts to avoid useless introducing useless spontaneous transitions.
Think for instance of the applying proper to thompson(a?{n}): it is much more efficient to work "from final to initial states", than the converse (which is what the "implementation order" actually does). For n=2000, the "implementation order" takes 102s on my machine, while this order (and its implementation) takes 15.2s.
Definition at line 277 of file epsilon-remover.hh.
References vcsn::detail::epsilon_remover< Aut, has_one >::aut_, vcsn::detail::epsilon_remover< Aut, has_one >::build_heap_(), vcsn::detail::epsilon_remover< Aut, has_one >::debug_, vcsn::dot(), vcsn::detail::epsilon_remover< Aut, has_one >::handles_, vcsn::detail::epsilon_remover< Aut, has_one >::num_spontaneous_transitions_(), vcsn::detail::epsilon_remover< Aut, has_one >::show_heap_(), vcsn::detail::epsilon_remover< Aut, has_one >::todo_, vcsn::detail::epsilon_remover< Aut, has_one >::update_heap_(), and vcsn::detail::epsilon_remover< Aut, has_one >::update_profile_().
Referenced by vcsn::detail::epsilon_remover< Aut, has_one >::operator()().
|
inlineprivate |
The number of spontaneous transitions in aut_.
Duplicates info.hh, but since info.hh uses this file, we get an insane mutual dependency. Break it.
Definition at line 350 of file epsilon-remover.hh.
References vcsn::detail::epsilon_remover< Aut, has_one >::aut_.
Referenced by vcsn::detail::epsilon_remover< Aut, has_one >::in_situ_remover_().
|
inline |
Definition at line 63 of file epsilon-remover.hh.
References vcsn::detail::epsilon_remover< Aut, has_one >::aut_, vcsn::copy_into(), vcsn::detail::epsilon_remover< Aut, has_one >::in_situ_remover_(), vcsn::is_proper(), and vcsn::detail::make_proper_context().
|
inlineprivate |
Definition at line 173 of file epsilon-remover.hh.
References vcsn::detail::epsilon_remover< Aut, has_one >::handles_.
Referenced by vcsn::detail::epsilon_remover< Aut, has_one >::update_profile_().
|
inlineprivate |
Show the heap, for debugging.
Definition at line 136 of file epsilon-remover.hh.
References vcsn::detail::epsilon_remover< Aut, has_one >::todo_.
Referenced by vcsn::detail::epsilon_remover< Aut, has_one >::in_situ_remover_(), and vcsn::detail::epsilon_remover< Aut, has_one >::update_heap_().
|
inlineprivate |
Update the heap for s.
Definition at line 149 of file epsilon-remover.hh.
References vcsn::detail::epsilon_remover< Aut, has_one >::debug_, vcsn::detail::epsilon_remover< Aut, has_one >::handles_, vcsn::detail::epsilon_remover< Aut, has_one >::show_heap_(), and vcsn::detail::epsilon_remover< Aut, has_one >::todo_.
Referenced by vcsn::detail::epsilon_remover< Aut, has_one >::in_situ_remover_().
|
inlineprivate |
The core of the (backward) epsilon-removal.
For each state s if s has an epsilon-loop with weight w if w is not starrable, return false else compute ws = star(w) endif remove the loop else ws = 1 endif for each incoming epsilon transition e:p–>s with weight h for each outgoing transition s–a|k–>q add (and not set) transition p– a | h.ws.k –> q endfor if s is final with weight h add final weight h.ws to p endif remove e endfor endfor return true
If the method returns false, aut is corrupted.
aut | The automaton in which epsilon-transitions will be removed |
prune | Whether to remove states that become inaccessible. |
Definition at line 108 of file epsilon-remover.hh.
References vcsn::detail::epsilon_remover< Aut, has_one >::aut_, vcsn::detail::epsilon_remover< Aut, has_one >::empty_word_, and vcsn::detail::epsilon_remover< Aut, has_one >::profile().
Referenced by vcsn::detail::epsilon_remover< Aut, has_one >::in_situ_remover_().
|
private |
Definition at line 168 of file epsilon-remover.hh.
|
private |
The automaton we work on.
Definition at line 362 of file epsilon-remover.hh.
Referenced by vcsn::detail::epsilon_remover< Aut, has_one >::build_heap_(), vcsn::detail::epsilon_remover< Aut, has_one >::in_situ_remover_(), vcsn::detail::epsilon_remover< Aut, has_one >::num_spontaneous_transitions_(), vcsn::detail::epsilon_remover< Aut, has_one >::operator()(), vcsn::detail::epsilon_remover< Aut, false >::operator()(), and vcsn::detail::epsilon_remover< Aut, has_one >::update_profile_().
|
private |
Debug level. The higher, the more details are reported.
Definition at line 360 of file epsilon-remover.hh.
Referenced by vcsn::detail::epsilon_remover< Aut, has_one >::in_situ_remover_(), and vcsn::detail::epsilon_remover< Aut, has_one >::update_heap_().
|
private |
Shorthand to the empty word.
Definition at line 366 of file epsilon-remover.hh.
Referenced by vcsn::detail::epsilon_remover< Aut, has_one >::build_heap_(), vcsn::detail::epsilon_remover< Aut, has_one >::in_situ_remover_(), and vcsn::detail::epsilon_remover< Aut, has_one >::update_profile_().
|
private |
Map: state -> heap-handle.
Definition at line 372 of file epsilon-remover.hh.
Referenced by vcsn::detail::epsilon_remover< Aut, has_one >::build_heap_(), vcsn::detail::epsilon_remover< Aut, has_one >::in_situ_remover_(), vcsn::detail::epsilon_remover< Aut, has_one >::profile(), and vcsn::detail::epsilon_remover< Aut, has_one >::update_heap_().
|
private |
Whether to prune states that become inaccessible.
Definition at line 375 of file epsilon-remover.hh.
Referenced by vcsn::detail::epsilon_remover< Aut, has_one >::in_situ_remover_().
|
private |
Definition at line 169 of file epsilon-remover.hh.
|
private |
Definition at line 370 of file epsilon-remover.hh.
Referenced by vcsn::detail::epsilon_remover< Aut, has_one >::build_heap_(), vcsn::detail::epsilon_remover< Aut, has_one >::in_situ_remover_(), vcsn::detail::epsilon_remover< Aut, has_one >::show_heap_(), and vcsn::detail::epsilon_remover< Aut, has_one >::update_heap_().
|
private |
Shorthand to the weightset.
Definition at line 364 of file epsilon-remover.hh.
Referenced by vcsn::detail::epsilon_remover< Aut, has_one >::in_situ_remover_().