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

#include <epsilon-remover-separate.hh>

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

aut_proper_t	operator() ()
	Remove all the states with incoming spontaneous transitions. More...

Private Types
using	automaton_t = typename std::remove_cv< Aut >::type

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	transition_t = transition_t_of< automaton_t >

using	transitions_t = std::vector< transition_t >

using	proper_ctx_t = detail::proper_context< context_t_of< Aut >>

using	dirty_ctx_t = context< vcsn::oneset, weightset_t >

using	aut_dirty_t = mutable_automaton< dirty_ctx_t >

using	aut_proper_t = fresh_automaton_t_of< Aut, proper_ctx_t >

using	label_proper_t = label_t_of< aut_proper_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 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_t s)
	Update the heap for s. More...

epsilon_profile< state_t > *	profile (state_t s)

void	remover_on (state_t dirty_s, state_t proper_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 automata we work on. More...

aut_dirty_t	aut_dirty_

const weightset_t &	ws_
	Shorthand to the weightset. 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...

std::vector< state_t >	d2p_

std::vector< state_t >	p2d_

Detailed Description

template<typename 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 36 of file epsilon-remover-separate.hh.

Member Typedef Documentation

template<typename 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

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

template<typename 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

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

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

using vcsn::detail::epsilon_remover_separate< Aut, has_one >::automaton_t = typename std::remove_cv<Aut>::type

private

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

template<typename 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

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

template<typename 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<epsilon_profile<state_t>>

private

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

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

template<typename 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 52 of file epsilon-remover-separate.hh.

template<typename 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<typename 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

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

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

using vcsn::detail::epsilon_remover_separate< Aut, has_one >::state_t = state_t_of<automaton_t>

private

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

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

using vcsn::detail::epsilon_remover_separate< Aut, has_one >::transition_t = transition_t_of<automaton_t>

private

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

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

using vcsn::detail::epsilon_remover_separate< Aut, has_one >::transitions_t = std::vector<transition_t>

private

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

template<typename 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<typename 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<typename 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

aut	the automaton in which to remove them
prune	whether to delete states that become inaccessible

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

References vcsn::detail::epsilon_remover_separate< Aut, has_one >::aut_dirty_, vcsn::detail::epsilon_remover_separate< Aut, has_one >::aut_proper_, vcsn::detail::epsilon_remover_separate< Aut, has_one >::d2p_, vcsn::make_copier(), vcsn::detail::make_proper_context(), vcsn::detail::epsilon_remover_separate< Aut, has_one >::p2d_, and vcsn::detail::epsilon_remover_separate< Aut, has_one >::ws_.

Here is the call graph for this function:

Member Function Documentation

template<typename 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 118 of file epsilon-remover-separate.hh.

References vcsn::detail::epsilon_remover_separate< Aut, has_one >::aut_dirty_, vcsn::detail::epsilon_remover_separate< Aut, has_one >::d2p_, vcsn::detail::epsilon_remover_separate< Aut, has_one >::handles_, vcsn::detail::epsilon_remover_separate< Aut, has_one >::todo_, and vcsn::detail::epsilon_remover_separate< Aut, has_one >::update_profile_().

Referenced by vcsn::detail::epsilon_remover_separate< Aut, has_one >::operator()().

Here is the call graph for this function:

template<typename 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 299 of file epsilon-remover-separate.hh.

Here is the call graph for this function:

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

epsilon_profile<state_t>* vcsn::detail::epsilon_remover_separate< Aut, has_one >::profile ( state_t s )

inlineprivate

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

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

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

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

void vcsn::detail::epsilon_remover_separate< Aut, has_one >::remover_on	(	state_t	dirty_s,
		state_t	proper_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.

The state s corresponds to a dirty state id.

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

References vcsn::detail::epsilon_remover_separate< Aut, has_one >::aut_dirty_, vcsn::detail::epsilon_remover_separate< Aut, has_one >::aut_proper_, vcsn::detail::epsilon_remover_separate< Aut, has_one >::d2p_, vcsn::detail::epsilon_remover_separate< Aut, has_one >::debug_, vcsn::pair(), vcsn::detail::epsilon_remover_separate< Aut, has_one >::prune_, and vcsn::detail::epsilon_remover_separate< Aut, has_one >::ws_.

Referenced by vcsn::detail::epsilon_remover_separate< Aut, has_one >::operator()().

Here is the call graph for this function:

template<typename 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 134 of file epsilon-remover-separate.hh.

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