![]() |
Vcsn
2.3a
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... | |
bool | state_has_spontaneous_in (state_proper_t proper_s) const |
Whether the given state has incoming spontaneous transitions. More... | |
void | remover_on (state_proper_t proper_s) |
Wrapper around remover_on() which does a lookup of the dirty state. More... | |
aut_proper_t | operator() () |
Remove all the states with incoming spontaneous transitions. More... | |
aut_proper_t | get_proper () |
Return the proper part. Needed by lazy algorithm. More... | |
Private Types | |
using | automaton_t = std::remove_cv_t< Aut > |
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 | dirty_ctx_t = context< vcsn::oneset, weightset_t > |
Context for spontaneous automaton (only spontaneous transitions of the input automaton). More... | |
using | aut_dirty_t = mutable_automaton< dirty_ctx_t > |
Spontaneous automaton. More... | |
using | state_dirty_t = state_t_of< aut_dirty_t > |
using | proper_ctx_t = detail::proper_context< context_t_of< Aut >> |
Context for proper automaton (only proper transitions). More... | |
using | aut_proper_t = fresh_automaton_t_of< Aut, proper_ctx_t > |
Proper automaton. More... | |
using | state_proper_t = state_t_of< aut_proper_t > |
using | label_proper_t = label_t_of< aut_proper_t > |
using | profile_t = epsilon_profile< state_proper_t > |
Data used to compute the order of state processing. More... | |
using | heap_t = boost::heap::fibonacci_heap< profile_t > |
Max-heap to decide the order of state-elimination. More... | |
Private Member Functions | |
void | update_profile_ (state_proper_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_proper_t s) |
Update the heap for s. More... | |
profile_t * | profile_ (state_proper_t s) const |
The profile of state s, or nullptr if it is not to be processed. More... | |
void | remover_on (state_proper_t proper_s, state_dirty_t dirty_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 proper part. More... | |
aut_dirty_t | aut_dirty_ |
The sponteanous part. More... | |
const weightset_t & | ws_ |
Shorthand to the weightset. More... | |
heap_t | todo_ |
std::unordered_map< state_proper_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_proper_t > | d2p_ |
std::vector< state_dirty_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 33 of file epsilon-remover-separate.hh.
|
private |
Spontaneous automaton.
Definition at line 44 of file epsilon-remover-separate.hh.
|
private |
Proper automaton.
Definition at line 50 of file epsilon-remover-separate.hh.
|
private |
Definition at line 35 of file epsilon-remover-separate.hh.
|
private |
Context for spontaneous automaton (only spontaneous transitions of the input automaton).
Definition at line 42 of file epsilon-remover-separate.hh.
|
private |
Max-heap to decide the order of state-elimination.
Definition at line 433 of file epsilon-remover-separate.hh.
|
private |
Definition at line 52 of file epsilon-remover-separate.hh.
|
private |
Definition at line 38 of file epsilon-remover-separate.hh.
|
private |
Data used to compute the order of state processing.
Definition at line 104 of file epsilon-remover-separate.hh.
|
private |
Context for proper automaton (only proper transitions).
Definition at line 48 of file epsilon-remover-separate.hh.
|
private |
Definition at line 45 of file epsilon-remover-separate.hh.
|
private |
Definition at line 51 of file epsilon-remover-separate.hh.
|
private |
Definition at line 37 of file epsilon-remover-separate.hh.
|
private |
Definition at line 36 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.
|
inlineprivate |
Build the profiles and the heap for states with incoming spontaneous transitions.
Definition at line 124 of file epsilon-remover-separate.hh.
Referenced by vcsn::detail::epsilon_remover_separate< transpose_in_automaton_t >::operator()().
|
inline |
Return the proper part. Needed by lazy algorithm.
Definition at line 412 of file epsilon-remover-separate.hh.
|
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 322 of file epsilon-remover-separate.hh.
|
inlineprivate |
The profile of state s, or nullptr if it is not to be processed.
Definition at line 177 of file epsilon-remover-separate.hh.
Referenced by vcsn::detail::epsilon_remover_separate< transpose_in_automaton_t >::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.
Definition at line 197 of file epsilon-remover-separate.hh.
Referenced by vcsn::detail::epsilon_remover_separate< transpose_in_automaton_t >::operator()(), and vcsn::detail::epsilon_remover_separate< transpose_in_automaton_t >::remover_on().
|
inline |
Wrapper around remover_on() which does a lookup of the dirty state.
Definition at line 303 of file epsilon-remover-separate.hh.
|
inlineprivate |
Show the heap, for debugging.
Definition at line 139 of file epsilon-remover-separate.hh.
Referenced by vcsn::detail::epsilon_remover_separate< transpose_in_automaton_t >::operator()(), and vcsn::detail::epsilon_remover_separate< transpose_in_automaton_t >::update_heap_().
|
inline |
Whether the given state has incoming spontaneous transitions.
Definition at line 293 of file epsilon-remover-separate.hh.
|
inlineprivate |
Update the heap for s.
Definition at line 152 of file epsilon-remover-separate.hh.
Referenced by vcsn::detail::epsilon_remover_separate< transpose_in_automaton_t >::operator()().
|
inlineprivate |
Update the profile of s.
Definition at line 107 of file epsilon-remover-separate.hh.
Referenced by vcsn::detail::epsilon_remover_separate< transpose_in_automaton_t >::build_heap_(), and vcsn::detail::epsilon_remover_separate< transpose_in_automaton_t >::operator()().
|
private |
Definition at line 171 of file epsilon-remover-separate.hh.
|
private |
The sponteanous part.
Initialized to the spontaneous part of the input automaton. At the end, empty.
Definition at line 427 of file epsilon-remover-separate.hh.
Referenced by vcsn::detail::epsilon_remover_separate< transpose_in_automaton_t >::build_heap_(), vcsn::detail::epsilon_remover_separate< transpose_in_automaton_t >::epsilon_remover_separate(), vcsn::detail::epsilon_remover_separate< transpose_in_automaton_t >::operator()(), vcsn::detail::epsilon_remover_separate< transpose_in_automaton_t >::remover_on(), vcsn::detail::epsilon_remover_separate< transpose_in_automaton_t >::state_has_spontaneous_in(), and vcsn::detail::epsilon_remover_separate< transpose_in_automaton_t >::update_profile_().
|
private |
The proper part.
Initialized to the proper part of the input automaton. At the end, the result.
Definition at line 423 of file epsilon-remover-separate.hh.
Referenced by vcsn::detail::epsilon_remover_separate< transpose_in_automaton_t >::epsilon_remover_separate(), vcsn::detail::epsilon_remover_separate< transpose_in_automaton_t >::get_proper(), vcsn::detail::epsilon_remover_separate< transpose_in_automaton_t >::operator()(), vcsn::detail::epsilon_remover_separate< transpose_in_automaton_t >::remover_on(), and vcsn::detail::epsilon_remover_separate< transpose_in_automaton_t >::update_profile_().
|
private |
Definition at line 441 of file epsilon-remover-separate.hh.
Referenced by vcsn::detail::epsilon_remover_separate< transpose_in_automaton_t >::build_heap_(), vcsn::detail::epsilon_remover_separate< transpose_in_automaton_t >::epsilon_remover_separate(), vcsn::detail::epsilon_remover_separate< transpose_in_automaton_t >::operator()(), and vcsn::detail::epsilon_remover_separate< transpose_in_automaton_t >::remover_on().
|
private |
Debug level. The higher, the more details are reported.
Definition at line 419 of file epsilon-remover-separate.hh.
Referenced by vcsn::detail::epsilon_remover_separate< transpose_in_automaton_t >::operator()(), vcsn::detail::epsilon_remover_separate< transpose_in_automaton_t >::remover_on(), and vcsn::detail::epsilon_remover_separate< transpose_in_automaton_t >::update_heap_().
|
private |
Map: state -> heap-handle.
Definition at line 436 of file epsilon-remover-separate.hh.
Referenced by vcsn::detail::epsilon_remover_separate< transpose_in_automaton_t >::build_heap_(), vcsn::detail::epsilon_remover_separate< transpose_in_automaton_t >::operator()(), vcsn::detail::epsilon_remover_separate< transpose_in_automaton_t >::profile_(), and vcsn::detail::epsilon_remover_separate< transpose_in_automaton_t >::update_heap_().
|
private |
Definition at line 442 of file epsilon-remover-separate.hh.
Referenced by vcsn::detail::epsilon_remover_separate< transpose_in_automaton_t >::epsilon_remover_separate(), vcsn::detail::epsilon_remover_separate< transpose_in_automaton_t >::operator()(), vcsn::detail::epsilon_remover_separate< transpose_in_automaton_t >::remover_on(), vcsn::detail::epsilon_remover_separate< transpose_in_automaton_t >::state_has_spontaneous_in(), and vcsn::detail::epsilon_remover_separate< transpose_in_automaton_t >::update_profile_().
|
private |
Whether to prune states that become inaccessible.
Definition at line 439 of file epsilon-remover-separate.hh.
Referenced by vcsn::detail::properer< Aut >::remover_(), and vcsn::detail::epsilon_remover_separate< transpose_in_automaton_t >::remover_on().
|
private |
Definition at line 172 of file epsilon-remover-separate.hh.
|
private |
Definition at line 434 of file epsilon-remover-separate.hh.
Referenced by vcsn::detail::epsilon_remover_separate< transpose_in_automaton_t >::build_heap_(), vcsn::detail::epsilon_remover_separate< transpose_in_automaton_t >::operator()(), vcsn::detail::epsilon_remover_separate< transpose_in_automaton_t >::show_heap_(), and vcsn::detail::epsilon_remover_separate< transpose_in_automaton_t >::update_heap_().
|
private |
Shorthand to the weightset.
Definition at line 430 of file epsilon-remover-separate.hh.
Referenced by vcsn::detail::epsilon_remover_separate< transpose_in_automaton_t >::epsilon_remover_separate(), and vcsn::detail::epsilon_remover_separate< transpose_in_automaton_t >::remover_on().