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_t &	ws_ = *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

aut	the automaton in which to remove them
prune	whether 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.

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

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

References vcsn::detail::epsilon_remover< Aut, has_one >::handles_.

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

template<Automaton Aut, bool has_one = labelset_t_of<Aut>::has_one()>

void vcsn::detail::epsilon_remover< Aut, has_one >::show_heap_ ( ) const

inlineprivate

Show the heap, for debugging.

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

References vcsn::detail::epsilon_remover< Aut, has_one >::todo_.

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

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