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

aut	The automaton in which epsilon-transitions will be removed
prune	Whether to remove states that become inaccessible.

Returns: true if the proper succeeds, or false otherwise.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 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.

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

Definition at line 173 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 136 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 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()>

automaton_t vcsn::detail::epsilon_remover< Aut, has_one >::aut_

private

The automaton we work on.

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

Referenced by vcsn::detail::epsilon_remover< Aut, has_one >::build_heap_(), vcsn::detail::epsilon_remover< Aut, has_one >::in_situ_remover(), vcsn::detail::epsilon_remover< Aut, has_one >::in_situ_remover_(), vcsn::detail::epsilon_remover< Aut, has_one >::num_spontaneous_transitions_(), vcsn::detail::epsilon_remover< Aut, has_one >::operator()(), and vcsn::detail::epsilon_remover< Aut, has_one >::update_profile_().

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

Shorthand to the empty word.

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

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

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

Map: state -> heap-handle.

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

Referenced by vcsn::detail::epsilon_remover< Aut, has_one >::build_heap_(), vcsn::detail::epsilon_remover< Aut, has_one >::in_situ_remover_(), vcsn::detail::epsilon_remover< Aut, has_one >::profile(), and vcsn::detail::epsilon_remover< Aut, has_one >::update_heap_().

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

heap_t vcsn::detail::epsilon_remover< Aut, has_one >::todo_

private

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

Referenced by vcsn::detail::epsilon_remover< Aut, has_one >::build_heap_(), vcsn::detail::epsilon_remover< Aut, has_one >::in_situ_remover_(), vcsn::detail::epsilon_remover< Aut, has_one >::show_heap_(), and vcsn::detail::epsilon_remover< Aut, has_one >::update_heap_().

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:

vcsn/algos/epsilon-remover.hh

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Detailed Description

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

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

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