Vcsn  2.2
Be Rational
Public Member Functions | Private Types | Private Member Functions | Private Attributes | List of all members
vcsn::detail::epsilon_remover_separate< Aut, has_one > Class Template Reference

This class contains the core of the proper algorithm. More...

#include <epsilon-remover-separate.hh>

Inheritance diagram for vcsn::detail::epsilon_remover_separate< Aut, has_one >:
Collaboration diagram for vcsn::detail::epsilon_remover_separate< Aut, has_one >:

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_
 

Detailed Description

template<Automaton Aut, bool has_one = labelset_t_of<Aut>::has_one()>
class vcsn::detail::epsilon_remover_separate< Aut, has_one >

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 37 of file epsilon-remover-separate.hh.

Member Typedef Documentation

template<Automaton Aut, bool has_one = labelset_t_of<Aut>::has_one()>
using vcsn::detail::epsilon_remover_separate< Aut, has_one >::aut_dirty_t = mutable_automaton<dirty_ctx_t>
private

Spontaneous automaton.

Definition at line 48 of file epsilon-remover-separate.hh.

template<Automaton Aut, bool has_one = labelset_t_of<Aut>::has_one()>
using vcsn::detail::epsilon_remover_separate< Aut, has_one >::aut_proper_t = fresh_automaton_t_of<Aut, proper_ctx_t>
private

Proper automaton.

Definition at line 54 of file epsilon-remover-separate.hh.

template<Automaton Aut, bool has_one = labelset_t_of<Aut>::has_one()>
using vcsn::detail::epsilon_remover_separate< Aut, has_one >::automaton_t = std::remove_cv_t<Aut>
private

Definition at line 39 of file epsilon-remover-separate.hh.

template<Automaton Aut, bool has_one = labelset_t_of<Aut>::has_one()>
using vcsn::detail::epsilon_remover_separate< Aut, has_one >::dirty_ctx_t = context<vcsn::oneset, weightset_t>
private

Context for spontaneous automaton (only spontaneous transitions of the input automaton).

Definition at line 46 of file epsilon-remover-separate.hh.

template<Automaton Aut, bool has_one = labelset_t_of<Aut>::has_one()>
using vcsn::detail::epsilon_remover_separate< Aut, has_one >::heap_t = boost::heap::fibonacci_heap<profile_t>
private

Max-heap to decide the order of state-elimination.

Definition at line 437 of file epsilon-remover-separate.hh.

template<Automaton Aut, bool has_one = labelset_t_of<Aut>::has_one()>
using vcsn::detail::epsilon_remover_separate< Aut, has_one >::label_proper_t = label_t_of<aut_proper_t>
private

Definition at line 56 of file epsilon-remover-separate.hh.

template<Automaton Aut, bool has_one = labelset_t_of<Aut>::has_one()>
using vcsn::detail::epsilon_remover_separate< Aut, has_one >::labelset_t = labelset_t_of<automaton_t>
private

Definition at line 42 of file epsilon-remover-separate.hh.

template<Automaton Aut, bool has_one = labelset_t_of<Aut>::has_one()>
using vcsn::detail::epsilon_remover_separate< Aut, has_one >::profile_t = epsilon_profile<state_proper_t>
private

Data used to compute the order of state processing.

Definition at line 108 of file epsilon-remover-separate.hh.

template<Automaton Aut, bool has_one = labelset_t_of<Aut>::has_one()>
using vcsn::detail::epsilon_remover_separate< Aut, has_one >::proper_ctx_t = detail::proper_context<context_t_of<Aut>>
private

Context for proper automaton (only proper transitions).

Definition at line 52 of file epsilon-remover-separate.hh.

template<Automaton Aut, bool has_one = labelset_t_of<Aut>::has_one()>
using vcsn::detail::epsilon_remover_separate< Aut, has_one >::state_dirty_t = state_t_of<aut_dirty_t>
private

Definition at line 49 of file epsilon-remover-separate.hh.

template<Automaton Aut, bool has_one = labelset_t_of<Aut>::has_one()>
using vcsn::detail::epsilon_remover_separate< Aut, has_one >::state_proper_t = state_t_of<aut_proper_t>
private

Definition at line 55 of file epsilon-remover-separate.hh.

template<Automaton Aut, bool has_one = labelset_t_of<Aut>::has_one()>
using vcsn::detail::epsilon_remover_separate< Aut, has_one >::weight_t = typename weightset_t::value_t
private

Definition at line 41 of file epsilon-remover-separate.hh.

template<Automaton Aut, bool has_one = labelset_t_of<Aut>::has_one()>
using vcsn::detail::epsilon_remover_separate< Aut, has_one >::weightset_t = weightset_t_of<automaton_t>
private

Definition at line 40 of file epsilon-remover-separate.hh.

Constructor & Destructor Documentation

template<Automaton Aut, bool has_one = labelset_t_of<Aut>::has_one()>
vcsn::detail::epsilon_remover_separate< Aut, has_one >::epsilon_remover_separate ( const automaton_t &  aut,
bool  prune = true 
)
inline

Get ready to eliminate spontaneous transitions.

Parameters
autthe automaton in which to remove them
prunewhether to delete states that become inaccessible

Definition at line 62 of file epsilon-remover-separate.hh.

Member Function Documentation

template<Automaton Aut, bool has_one = labelset_t_of<Aut>::has_one()>
void vcsn::detail::epsilon_remover_separate< Aut, has_one >::build_heap_ ( )
inlineprivate

Build the profiles and the heap for states with incoming spontaneous transitions.

Definition at line 128 of file epsilon-remover-separate.hh.

Referenced by vcsn::detail::epsilon_remover_separate< transpose_in_automaton_t >::operator()().

template<Automaton Aut, bool has_one = labelset_t_of<Aut>::has_one()>
aut_proper_t vcsn::detail::epsilon_remover_separate< Aut, has_one >::get_proper ( )
inline

Return the proper part. Needed by lazy algorithm.

Definition at line 416 of file epsilon-remover-separate.hh.

template<Automaton Aut, bool has_one = labelset_t_of<Aut>::has_one()>
aut_proper_t 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 326 of file epsilon-remover-separate.hh.

template<Automaton Aut, bool has_one = labelset_t_of<Aut>::has_one()>
profile_t* vcsn::detail::epsilon_remover_separate< Aut, has_one >::profile_ ( state_proper_t  s) const
inlineprivate

The profile of state s, or nullptr if it is not to be processed.

Definition at line 181 of file epsilon-remover-separate.hh.

Referenced by vcsn::detail::epsilon_remover_separate< transpose_in_automaton_t >::update_profile_().

template<Automaton Aut, bool has_one = labelset_t_of<Aut>::has_one()>
void vcsn::detail::epsilon_remover_separate< Aut, has_one >::remover_on ( state_proper_t  proper_s,
state_dirty_t  dirty_s 
)
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 201 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().

template<Automaton Aut, bool has_one = labelset_t_of<Aut>::has_one()>
void vcsn::detail::epsilon_remover_separate< Aut, has_one >::remover_on ( state_proper_t  proper_s)
inline

Wrapper around remover_on() which does a lookup of the dirty state.

Definition at line 307 of file epsilon-remover-separate.hh.

template<Automaton Aut, bool has_one = labelset_t_of<Aut>::has_one()>
void vcsn::detail::epsilon_remover_separate< Aut, has_one >::show_heap_ ( ) const
inlineprivate

Show the heap, for debugging.

Definition at line 143 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_().

template<Automaton Aut, bool has_one = labelset_t_of<Aut>::has_one()>
bool vcsn::detail::epsilon_remover_separate< Aut, has_one >::state_has_spontaneous_in ( state_proper_t  proper_s) const
inline

Whether the given state has incoming spontaneous transitions.

Definition at line 297 of file epsilon-remover-separate.hh.

template<Automaton Aut, bool has_one = labelset_t_of<Aut>::has_one()>
void vcsn::detail::epsilon_remover_separate< Aut, has_one >::update_heap_ ( state_proper_t  s)
inlineprivate

Update the heap for s.

Precondition
its profile is updated.

Definition at line 156 of file epsilon-remover-separate.hh.

Referenced by vcsn::detail::epsilon_remover_separate< transpose_in_automaton_t >::operator()().

template<Automaton Aut, bool has_one = labelset_t_of<Aut>::has_one()>
void vcsn::detail::epsilon_remover_separate< Aut, has_one >::update_profile_ ( state_proper_t  proper_s)
inlineprivate

Update the profile of s.

Definition at line 111 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()().

Member Data Documentation

template<Automaton Aut, bool has_one = labelset_t_of<Aut>::has_one()>
unsigned vcsn::detail::epsilon_remover_separate< Aut, has_one >::added_ = 0
private

Definition at line 175 of file epsilon-remover-separate.hh.

template<Automaton Aut, bool has_one = labelset_t_of<Aut>::has_one()>
aut_dirty_t vcsn::detail::epsilon_remover_separate< Aut, has_one >::aut_dirty_
private

The sponteanous part.

Initialized to the spontaneous part of the input automaton. At the end, empty.

Definition at line 431 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_().

template<Automaton Aut, bool has_one = labelset_t_of<Aut>::has_one()>
aut_proper_t vcsn::detail::epsilon_remover_separate< Aut, has_one >::aut_proper_
private

The proper part.

Initialized to the proper part of the input automaton. At the end, the result.

Definition at line 427 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_().

template<Automaton Aut, bool has_one = labelset_t_of<Aut>::has_one()>
std::vector<state_proper_t> vcsn::detail::epsilon_remover_separate< Aut, has_one >::d2p_
private

Definition at line 445 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().

template<Automaton Aut, bool has_one = labelset_t_of<Aut>::has_one()>
int vcsn::detail::epsilon_remover_separate< Aut, has_one >::debug_
private

Debug level. The higher, the more details are reported.

Definition at line 423 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_().

template<Automaton Aut, bool has_one = labelset_t_of<Aut>::has_one()>
std::unordered_map<state_proper_t, typename heap_t::handle_type> vcsn::detail::epsilon_remover_separate< Aut, has_one >::handles_
private

Map: state -> heap-handle.

Definition at line 440 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_().

template<Automaton Aut, bool has_one = labelset_t_of<Aut>::has_one()>
std::vector<state_dirty_t> vcsn::detail::epsilon_remover_separate< Aut, has_one >::p2d_
private

Definition at line 446 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_().

template<Automaton Aut, bool has_one = labelset_t_of<Aut>::has_one()>
bool vcsn::detail::epsilon_remover_separate< Aut, has_one >::prune_
private

Whether to prune states that become inaccessible.

Definition at line 443 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().

template<Automaton Aut, bool has_one = labelset_t_of<Aut>::has_one()>
unsigned vcsn::detail::epsilon_remover_separate< Aut, has_one >::removed_ = 0
private

Definition at line 176 of file epsilon-remover-separate.hh.

template<Automaton Aut, bool has_one = labelset_t_of<Aut>::has_one()>
heap_t vcsn::detail::epsilon_remover_separate< Aut, has_one >::todo_
private

Definition at line 438 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_().

template<Automaton Aut, bool has_one = labelset_t_of<Aut>::has_one()>
const weightset_t& vcsn::detail::epsilon_remover_separate< Aut, has_one >::ws_
private

Shorthand to the weightset.

Definition at line 434 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().

The documentation for this class was generated from the following file: