Vcsn  2.2
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)
 Get ready to eliminate spontaneous transitions. 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)
 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_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 38 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 49 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 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 >::heap_t = boost::heap::fibonacci_heap<epsilon_profile<state_t>>
private

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

Definition at line 372 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 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 >::labelset_t = labelset_t_of<automaton_t>
private

Definition at line 44 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 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 >::transition_t = transition_t_of<automaton_t>
private

Definition at line 46 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 43 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 42 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

Get ready to eliminate spontaneous transitions.

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

Definition at line 55 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 122 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 72 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 196 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 280 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 353 of file epsilon-remover.hh.

References vcsn::detail::epsilon_remover< Aut, has_one >::aut_, 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 61 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(), and vcsn::detail::make_proper_context().

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 152 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

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.Update the profile of s.

Definition at line 111 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 171 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 363 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 378 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 172 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 367 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: