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

#include <proper.hh>

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

Classes
struct	state_profile
	Data needed to compare the elimination order between states. More...

Public Member Functions
	properer (automaton_t &aut, bool prune=true)
	Get ready to eliminate spontaneous transitions. More...

Static Public Member Functions
static void	proper_here (automaton_t &aut, bool prune=true)
	Remove the epsilon-transitions of the input. More...

static bool	in_situ_remover (automaton_t &aut, bool prune=true)
	The core of the (backward) epsilon-removal. 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	label_t = label_t_of< automaton_t >

using	transition_t = transition_t_of< automaton_t >

using	transitions_t = std::vector< transition_t >

using	heap_t = boost::heap::fibonacci_heap< state_profile >
	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...

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

Static Private Member Functions
template<star_status_t Status>
static std::enable_if< Status==star_status_t::TOPS > ::type	proper_here_ (automaton_t &aut, bool=true)
	TOPS: valid iff proper succeeds. More...

template<star_status_t Status>
static std::enable_if< Status==star_status_t::ABSVAL > ::type	proper_here_ (automaton_t &aut, bool prune=true)
	ABSVAL: valid iff proper succeeds on the "absolute value" of the automaton. More...

template<star_status_t Status>
static std::enable_if< Status==star_status_t::STARRABLE > ::type	proper_here_ (automaton_t &aut, bool prune=true)
	STARRABLE: always valid. More...

template<star_status_t Status>
static std::enable_if< Status==star_status_t::NON_STARRABLE > ::type	proper_here_ (automaton_t &aut, bool prune=true)
	NON_STARRABLE: valid iff there is no epsilon-circuit with weight zero. 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_
	Shorthand to the weightset. More...

label_t	empty_word_
	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<typename Aut, bool has_one = labelset_t_of<Aut>::has_one()>
class vcsn::detail::properer< 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 49 of file proper.hh.

Member Typedef Documentation

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

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

private

Definition at line 51 of file proper.hh.

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

using vcsn::detail::properer< Aut, has_one >::heap_t = boost::heap::fibonacci_heap<state_profile>

private

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

Definition at line 504 of file proper.hh.

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

using vcsn::detail::properer< Aut, has_one >::label_t = label_t_of<automaton_t>

private

Definition at line 55 of file proper.hh.

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

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

private

Definition at line 52 of file proper.hh.

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

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

private

Definition at line 56 of file proper.hh.

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

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

private

Definition at line 57 of file proper.hh.

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

using vcsn::detail::properer< Aut, has_one >::weight_t = typename weightset_t::value_t

private

Definition at line 54 of file proper.hh.

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

using vcsn::detail::properer< Aut, has_one >::weightset_t = weightset_t_of<automaton_t>

private

Definition at line 53 of file proper.hh.

Constructor & Destructor Documentation

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

vcsn::detail::properer< Aut, has_one >::properer	(	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 63 of file proper.hh.

Member Function Documentation

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

void vcsn::detail::properer< Aut, has_one >::build_heap_ ( )

inlineprivate

Build the profiles and the heap for states with incoming spontaneous transitions.

Definition at line 219 of file proper.hh.

References vcsn::detail::properer< Aut, has_one >::aut_, vcsn::detail::properer< Aut, has_one >::empty_word_, vcsn::detail::properer< Aut, has_one >::handles_, and vcsn::detail::properer< Aut, has_one >::todo_.

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

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

static bool vcsn::detail::properer< Aut, has_one >::in_situ_remover	(	automaton_t &	aut,
		bool	prune = `true`
	)

inlinestatic

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.

Definition at line 122 of file proper.hh.

References vcsn::detail::properer< Aut, has_one >::in_situ_remover_().

Referenced by vcsn::in_situ_remover(), and vcsn::detail::properer< Aut, has_one >::proper_here_().

Here is the call graph for this function:

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

void vcsn::detail::properer< 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 state_profile definition.

Definition at line 296 of file proper.hh.

References vcsn::detail::properer< Aut, has_one >::added_, vcsn::detail::properer< Aut, has_one >::aut_, vcsn::detail::properer< Aut, has_one >::debug_, vcsn::detail::properer< Aut, has_one >::empty_word_, vcsn::pair(), vcsn::detail::properer< Aut, has_one >::prune_, vcsn::detail::properer< Aut, has_one >::removed_, and vcsn::detail::properer< Aut, has_one >::ws_.

Referenced by vcsn::detail::properer< Aut, has_one >::in_situ_remover().

Here is the call graph for this function:

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

void vcsn::detail::properer< 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 381 of file proper.hh.

Here is the call graph for this function:

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

state_profile* vcsn::detail::properer< Aut, has_one >::profile ( state_t s )

inlineprivate

Definition at line 273 of file proper.hh.

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

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

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

static void vcsn::detail::properer< Aut, has_one >::proper_here	(	automaton_t &	aut,
		bool	prune = `true`
	)

inlinestatic

Remove the epsilon-transitions of the input.

The behaviour of this method depends on the star_status of the weight_set:

– starrable : always valid, does not throw any exception – tops : the proper algo is directly launched on the input; if it returns false, an exception is launched – non_starrable / absval: is_valid is called before launching the algorithm.

Parameters

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

Exceptions

runtime_error if the input is not valid

Definition at line 85 of file proper.hh.

References vcsn::is_proper().

Referenced by vcsn::proper_here().

Here is the call graph for this function:

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

template<star_status_t Status>

static std::enable_if<Status == star_status_t::TOPS>::type vcsn::detail::properer< Aut, has_one >::proper_here_	(	automaton_t &	aut,
		bool	= `true`
	)

inlinestaticprivate

TOPS: valid iff proper succeeds.

Definition at line 454 of file proper.hh.

References vcsn::detail::properer< Aut, has_one >::in_situ_remover().

Here is the call graph for this function:

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

template<star_status_t Status>

static std::enable_if<Status == star_status_t::ABSVAL>::type vcsn::detail::properer< Aut, has_one >::proper_here_	(	automaton_t &	aut,
		bool	prune = `true`
	)

inlinestaticprivate

ABSVAL: valid iff proper succeeds on the "absolute value" of the automaton.

Definition at line 465 of file proper.hh.

References vcsn::detail::properer< Aut, has_one >::in_situ_remover(), vcsn::is_valid(), and vcsn::require().

Here is the call graph for this function:

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

template<star_status_t Status>

static std::enable_if<Status == star_status_t::STARRABLE>::type vcsn::detail::properer< Aut, has_one >::proper_here_	(	automaton_t &	aut,
		bool	prune = `true`
	)

inlinestaticprivate

STARRABLE: always valid.

Definition at line 475 of file proper.hh.

References vcsn::detail::properer< Aut, has_one >::in_situ_remover().

Here is the call graph for this function:

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

template<star_status_t Status>

static std::enable_if<Status == star_status_t::NON_STARRABLE>::type vcsn::detail::properer< Aut, has_one >::proper_here_	(	automaton_t &	aut,
		bool	prune = `true`
	)