![]() |
Vcsn
2.1
Be Rational
|
This class contains the core of the proper algorithm. More...
#include <epsilon-remover-separate.hh>
Public Member Functions | |
epsilon_remover_separate (const automaton_t &aut, bool prune=true) | |
Get ready to eliminate spontaneous transitions. More... | |
aut_proper_t | operator() () |
Remove all the states with incoming spontaneous transitions. More... | |
Private Types | |
using | automaton_t = typename std::remove_cv< Aut >::type |
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 | transition_t = transition_t_of< automaton_t > |
using | transitions_t = std::vector< transition_t > |
using | proper_ctx_t = detail::proper_context< context_t_of< Aut >> |
using | dirty_ctx_t = context< vcsn::oneset, weightset_t > |
using | aut_dirty_t = mutable_automaton< dirty_ctx_t > |
using | aut_proper_t = fresh_automaton_t_of< Aut, proper_ctx_t > |
using | label_proper_t = label_t_of< aut_proper_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 proper_s) |
Update the profile of s. 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 | 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 weight is computed, otherwise, (t) is stored into the closure list. More... | |
Private Attributes | |
unsigned | added_ = 0 |
unsigned | removed_ = 0 |
int | debug_ |
Debug level. The higher, the more details are reported. More... | |
aut_proper_t | aut_proper_ |
The automata we work on. More... | |
aut_dirty_t | aut_dirty_ |
const weightset_t & | ws_ |
Shorthand to the weightset. 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... | |
std::vector< state_t > | d2p_ |
std::vector< state_t > | p2d_ |
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 36 of file epsilon-remover-separate.hh.
|
private |
Definition at line 49 of file epsilon-remover-separate.hh.
|
private |
Definition at line 50 of file epsilon-remover-separate.hh.
|
private |
Definition at line 38 of file epsilon-remover-separate.hh.
|
private |
Definition at line 47 of file epsilon-remover-separate.hh.
|
private |
Max-heap to decide the order of state-elimination.
Definition at line 398 of file epsilon-remover-separate.hh.
|
private |
Definition at line 52 of file epsilon-remover-separate.hh.
|
private |
Definition at line 42 of file epsilon-remover-separate.hh.
|
private |
Definition at line 46 of file epsilon-remover-separate.hh.
|
private |
Definition at line 39 of file epsilon-remover-separate.hh.
|
private |
Definition at line 43 of file epsilon-remover-separate.hh.
|
private |
Definition at line 44 of file epsilon-remover-separate.hh.
|
private |
Definition at line 41 of file epsilon-remover-separate.hh.
|
private |
Definition at line 40 of file epsilon-remover-separate.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 58 of file epsilon-remover-separate.hh.
References vcsn::detail::epsilon_remover_separate< Aut, has_one >::aut_dirty_, vcsn::detail::epsilon_remover_separate< Aut, has_one >::aut_proper_, vcsn::detail::epsilon_remover_separate< Aut, has_one >::d2p_, vcsn::make_copier(), vcsn::detail::make_proper_context(), vcsn::detail::epsilon_remover_separate< Aut, has_one >::p2d_, and vcsn::detail::epsilon_remover_separate< Aut, has_one >::ws_.
|
inlineprivate |
Build the profiles and the heap for states with incoming spontaneous transitions.
Definition at line 118 of file epsilon-remover-separate.hh.
References vcsn::detail::epsilon_remover_separate< Aut, has_one >::aut_dirty_, vcsn::detail::epsilon_remover_separate< Aut, has_one >::d2p_, vcsn::detail::epsilon_remover_separate< Aut, has_one >::handles_, vcsn::detail::epsilon_remover_separate< Aut, has_one >::todo_, and vcsn::detail::epsilon_remover_separate< Aut, has_one >::update_profile_().
Referenced by vcsn::detail::epsilon_remover_separate< Aut, has_one >::operator()().
|
inline |
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 299 of file epsilon-remover-separate.hh.
References vcsn::detail::epsilon_remover_separate< Aut, has_one >::aut_dirty_, vcsn::detail::epsilon_remover_separate< Aut, has_one >::aut_proper_, vcsn::detail::epsilon_remover_separate< Aut, has_one >::build_heap_(), vcsn::detail::epsilon_remover_separate< Aut, has_one >::d2p_, vcsn::detail::epsilon_remover_separate< Aut, has_one >::debug_, vcsn::dot(), vcsn::detail::epsilon_remover_separate< Aut, has_one >::handles_, vcsn::detail::epsilon_remover_separate< Aut, has_one >::p2d_, vcsn::detail::epsilon_remover_separate< Aut, has_one >::remover_on(), vcsn::detail::epsilon_remover_separate< Aut, has_one >::show_heap_(), vcsn::detail::epsilon_remover_separate< Aut, has_one >::todo_, vcsn::detail::epsilon_remover_separate< Aut, has_one >::update_heap_(), and vcsn::detail::epsilon_remover_separate< Aut, has_one >::update_profile_().
|
inlineprivate |
Definition at line 171 of file epsilon-remover-separate.hh.
References vcsn::detail::epsilon_remover_separate< Aut, has_one >::handles_.
Referenced by vcsn::detail::epsilon_remover_separate< Aut, has_one >::update_profile_().
|
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.
The state s corresponds to a dirty state id.
Definition at line 193 of file epsilon-remover-separate.hh.
References vcsn::detail::epsilon_remover_separate< Aut, has_one >::aut_dirty_, vcsn::detail::epsilon_remover_separate< Aut, has_one >::aut_proper_, vcsn::detail::epsilon_remover_separate< Aut, has_one >::d2p_, vcsn::detail::epsilon_remover_separate< Aut, has_one >::debug_, vcsn::pair(), vcsn::detail::epsilon_remover_separate< Aut, has_one >::prune_, and vcsn::detail::epsilon_remover_separate< Aut, has_one >::ws_.
Referenced by vcsn::detail::epsilon_remover_separate< Aut, has_one >::operator()().
|
inlineprivate |
Show the heap, for debugging.
Definition at line 134 of file epsilon-remover-separate.hh.
References vcsn::detail::epsilon_remover_separate< Aut, has_one >::todo_.
Referenced by vcsn::detail::epsilon_remover_separate< Aut, has_one >::operator()(), and vcsn::detail::epsilon_remover_separate< Aut, has_one >::update_heap_().
|
inlineprivate |
Update the heap for s.
Definition at line 147 of file epsilon-remover-separate.hh.
References vcsn::detail::epsilon_remover_separate< Aut, has_one >::debug_, vcsn::detail::epsilon_remover_separate< Aut, has_one >::handles_, vcsn::detail::epsilon_remover_separate< Aut, has_one >::show_heap_(), and vcsn::detail::epsilon_remover_separate< Aut, has_one >::todo_.
Referenced by vcsn::detail::epsilon_remover_separate< Aut, has_one >::operator()().
|
inlineprivate |
Update the profile of s.
Definition at line 101 of file epsilon-remover-separate.hh.
References vcsn::detail::epsilon_remover_separate< Aut, has_one >::aut_dirty_, vcsn::detail::epsilon_remover_separate< Aut, has_one >::aut_proper_, vcsn::detail::epsilon_remover_separate< Aut, has_one >::p2d_, and vcsn::detail::epsilon_remover_separate< Aut, has_one >::profile().
Referenced by vcsn::detail::epsilon_remover_separate< Aut, has_one >::build_heap_(), and vcsn::detail::epsilon_remover_separate< Aut, has_one >::operator()().
|
private |
Definition at line 166 of file epsilon-remover-separate.hh.
|
private |
Definition at line 392 of file epsilon-remover-separate.hh.
Referenced by vcsn::detail::epsilon_remover_separate< Aut, has_one >::build_heap_(), vcsn::detail::epsilon_remover_separate< Aut, has_one >::epsilon_remover_separate(), vcsn::detail::epsilon_remover_separate< Aut, has_one >::operator()(), vcsn::detail::epsilon_remover_separate< Aut, has_one >::remover_on(), and vcsn::detail::epsilon_remover_separate< Aut, has_one >::update_profile_().
|
private |
The automata we work on.
Definition at line 391 of file epsilon-remover-separate.hh.
Referenced by vcsn::detail::epsilon_remover_separate< Aut, has_one >::epsilon_remover_separate(), vcsn::detail::epsilon_remover_separate< Aut, has_one >::operator()(), vcsn::detail::epsilon_remover_separate< Aut, has_one >::remover_on(), and vcsn::detail::epsilon_remover_separate< Aut, has_one >::update_profile_().
|
private |
Definition at line 406 of file epsilon-remover-separate.hh.
Referenced by vcsn::detail::epsilon_remover_separate< Aut, has_one >::build_heap_(), vcsn::detail::epsilon_remover_separate< Aut, has_one >::epsilon_remover_separate(), vcsn::detail::epsilon_remover_separate< Aut, has_one >::operator()(), and vcsn::detail::epsilon_remover_separate< Aut, has_one >::remover_on().
|
private |
Debug level. The higher, the more details are reported.
Definition at line 388 of file epsilon-remover-separate.hh.
Referenced by vcsn::detail::epsilon_remover_separate< Aut, has_one >::operator()(), vcsn::detail::epsilon_remover_separate< Aut, has_one >::remover_on(), and vcsn::detail::epsilon_remover_separate< Aut, has_one >::update_heap_().
|
private |
Map: state -> heap-handle.
Definition at line 401 of file epsilon-remover-separate.hh.
Referenced by vcsn::detail::epsilon_remover_separate< Aut, has_one >::build_heap_(), vcsn::detail::epsilon_remover_separate< Aut, has_one >::operator()(), vcsn::detail::epsilon_remover_separate< Aut, has_one >::profile(), and vcsn::detail::epsilon_remover_separate< Aut, has_one >::update_heap_().
|
private |
Definition at line 407 of file epsilon-remover-separate.hh.
Referenced by vcsn::detail::epsilon_remover_separate< Aut, has_one >::epsilon_remover_separate(), vcsn::detail::epsilon_remover_separate< Aut, has_one >::operator()(), and vcsn::detail::epsilon_remover_separate< Aut, has_one >::update_profile_().
|
private |
Whether to prune states that become inaccessible.
Definition at line 404 of file epsilon-remover-separate.hh.
Referenced by vcsn::detail::epsilon_remover_separate< Aut, has_one >::remover_on().
|
private |
Definition at line 167 of file epsilon-remover-separate.hh.
|
private |
Definition at line 399 of file epsilon-remover-separate.hh.
Referenced by vcsn::detail::epsilon_remover_separate< Aut, has_one >::build_heap_(), vcsn::detail::epsilon_remover_separate< Aut, has_one >::operator()(), vcsn::detail::epsilon_remover_separate< Aut, has_one >::show_heap_(), and vcsn::detail::epsilon_remover_separate< Aut, has_one >::update_heap_().
|
private |
Shorthand to the weightset.
Definition at line 395 of file epsilon-remover-separate.hh.
Referenced by vcsn::detail::epsilon_remover_separate< Aut, has_one >::epsilon_remover_separate(), and vcsn::detail::epsilon_remover_separate< Aut, has_one >::remover_on().