Vcsn  2.4
Be Rational
vcsn::detail::epsilon_remover< Aut, has_one > Class Template Reference

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

#include <epsilon-remover.hh>

Collaboration diagram for vcsn::detail::epsilon_remover< Aut, has_one >:

Public Member Functions

 epsilon_remover (automaton_t &aut, bool prune=true)
 The core of the (backward) epsilon-removal. More...
 
aut_proper_t operator() ()
 
void in_situ_remover ()
 

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)
 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 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_tws_ = *aut_->weightset()
 Shorthand to the weightset. More...
 
label_t empty_word_ = aut_->labelset()->one()
 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...
 

Detailed Description

template<Automaton Aut, bool has_one = labelset_t_of<Aut>::has_one()>
class vcsn::detail::epsilon_remover< 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 34 of file epsilon-remover.hh.

Member Typedef Documentation

template<Automaton Aut, bool has_one = labelset_t_of<Aut>::has_one()>
using vcsn::detail::epsilon_remover< Aut, has_one >::aut_proper_t = fresh_automaton_t_of<automaton_t, detail::proper_context<context_t_of<automaton_t>>>
private

Definition at line 45 of file epsilon-remover.hh.

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

Definition at line 36 of file epsilon-remover.hh.

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

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

Definition at line 369 of file epsilon-remover.hh.

template<Automaton Aut, bool has_one = labelset_t_of<Aut>::has_one()>
using vcsn::detail::epsilon_remover< Aut, has_one >::label_t = label_t_of<automaton_t>
private

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

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

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

template<Automaton Aut, bool has_one = labelset_t_of<Aut>::has_one()>
using vcsn::detail::epsilon_remover< Aut, has_one >::state_t = state_t_of<automaton_t>
private

Definition at line 37 of file epsilon-remover.hh.

template<Automaton Aut, bool has_one = labelset_t_of<Aut>::has_one()>
using vcsn::detail::epsilon_remover< Aut, has_one >::transition_t = transition_t_of<automaton_t>
private

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

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

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

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

Definition at line 38 of file epsilon-remover.hh.

Constructor & Destructor Documentation

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

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.

Parameters
autThe automaton in which epsilon-transitions will be removed
pruneWhether to remove states that become inaccessible.
Returns
true if the proper succeeds, or false otherwise.Get ready to eliminate spontaneous transitions.
Parameters
autthe automaton in which to remove them
prunewhether to delete states that become inaccessible

Definition at line 83 of file epsilon-remover.hh.

Member Function Documentation

template<Automaton Aut, bool has_one = labelset_t_of<Aut>::has_one()>
void vcsn::detail::epsilon_remover< Aut, has_one >::build_heap_ ( )
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::all_out(), 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_, vcsn::detail::in(), vcsn::detail::out(), and vcsn::detail::epsilon_remover< Aut, has_one >::todo_.

Referenced by vcsn::detail::epsilon_remover< Aut, has_one >::in_situ_remover_().

Here is the call graph for this function:

template<Automaton Aut, bool has_one = labelset_t_of<Aut>::has_one()>
void vcsn::detail::epsilon_remover< Aut, has_one >::in_situ_remover ( )
inline

Definition at line 100 of file epsilon-remover.hh.

References vcsn::detail::epsilon_remover< Aut, has_one >::aut_, vcsn::detail::epsilon_remover< Aut, has_one >::in_situ_remover_(), and vcsn::is_proper().

Referenced by vcsn::detail::epsilon_remover< Aut, has_one >::operator()(), and vcsn::detail::properer< Aut >::remover_here_().

Here is the call graph for this function:

template<Automaton Aut, bool has_one = labelset_t_of<Aut>::has_one()>
void vcsn::detail::epsilon_remover< Aut, has_one >::in_situ_remover_ ( state_t  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 193 of file epsilon-remover.hh.

References vcsn::detail::all_in(), vcsn::detail::all_out(), 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::in(), vcsn::detail::make_vector(), vcsn::pair(), vcsn::detail::epsilon_remover< Aut, has_one >::prune_, vcsn::detail::transitions(), and vcsn::detail::epsilon_remover< Aut, has_one >::ws_.

Here is the call graph for this function:

template<Automaton Aut, bool has_one = labelset_t_of<Aut>::has_one()>
void vcsn::detail::epsilon_remover< Aut, has_one >::in_situ_remover_ ( )
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::in(), vcsn::detail::epsilon_remover< Aut, has_one >::num_spontaneous_transitions_(), vcsn::detail::out(), 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 >::in_situ_remover().

Here is the call graph for this function:

template<Automaton Aut, bool has_one = labelset_t_of<Aut>::has_one()>
size_t vcsn::detail::epsilon_remover< Aut, has_one >::num_spontaneous_transitions_ ( ) const
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_, vcsn::res, and vcsn::detail::transitions().

Referenced by vcsn::detail::epsilon_remover< Aut, has_one >::in_situ_remover_().

Here is the call graph for this function:

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

Definition at line 89 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::detail::make_proper_context(), and vcsn::res.

Here is the call graph for this function:

template<Automaton Aut, bool has_one = labelset_t_of<Aut>::has_one()>
epsilon_profile<state_t>* vcsn::detail::epsilon_remover< Aut, has_one >::profile ( state_t  s)
inlineprivate
template<Automaton Aut, bool has_one = labelset_t_of<Aut>::has_one()>
void vcsn::detail::epsilon_remover< Aut, has_one >::show_heap_ ( ) const
inlineprivate
template<Automaton Aut, bool has_one = labelset_t_of<Aut>::has_one()>
void vcsn::detail::epsilon_remover< Aut, has_one >::update_heap_ ( state_t  s)
inlineprivate

Update the heap for s.

Precondition
its profile is updated.

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_().

Here is the call graph for this function:

template<Automaton Aut, bool has_one = labelset_t_of<Aut>::has_one()>
void vcsn::detail::epsilon_remover< Aut, has_one >::update_profile_ ( state_t  s)
inlineprivate

Update the profile of s.

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

References vcsn::detail::all_out(), vcsn::detail::epsilon_remover< Aut, has_one >::aut_, vcsn::detail::epsilon_remover< Aut, has_one >::empty_word_, vcsn::detail::in(), vcsn::detail::out(), vcsn::detail::epsilon_remover< Aut, has_one >::profile(), and vcsn::rat::size().

Referenced by vcsn::detail::epsilon_remover< Aut, has_one >::in_situ_remover_().

Here is the call graph for this function:

Member Data Documentation

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

Definition at line 168 of file epsilon-remover.hh.

template<Automaton Aut, bool has_one = labelset_t_of<Aut>::has_one()>
int vcsn::detail::epsilon_remover< Aut, has_one >::debug_
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_().

template<Automaton Aut, bool has_one = labelset_t_of<Aut>::has_one()>
label_t vcsn::detail::epsilon_remover< Aut, has_one >::empty_word_ = aut_->labelset()->one()
private
template<Automaton Aut, bool has_one = labelset_t_of<Aut>::has_one()>
std::unordered_map<state_t, typename heap_t::handle_type> vcsn::detail::epsilon_remover< Aut, has_one >::handles_
private
template<Automaton Aut, bool has_one = labelset_t_of<Aut>::has_one()>
bool vcsn::detail::epsilon_remover< Aut, has_one >::prune_
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_(), and vcsn::detail::properer< Aut >::remover_().

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

Definition at line 169 of file epsilon-remover.hh.

template<Automaton Aut, bool has_one = labelset_t_of<Aut>::has_one()>
const weightset_t& vcsn::detail::epsilon_remover< Aut, has_one >::ws_ = *aut_->weightset()
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_().


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