#include <minimize-moore.hh>

Collaboration diagram for vcsn::detail_moore::minimizer< Aut >:

Public Member Functions
	minimizer (const Aut &a)

void	build_classes_ ()
	Build the initial classes, and split until fix point. More...

partition_automaton< automaton_t >	operator() ()
	Return the quotient. More...

Private Types
using	automaton_t = Aut

using	label_t = label_t_of< automaton_t >

using	state_t = state_t_of< automaton_t >

using	class_t = unsigned

using	classes_t = std::vector< class_t >

using	set_t = std::vector< state_t >

using	state_to_class_t = std::unordered_map< state_t, class_t >

using	target_class_to_states_t = std::unordered_map< class_t, set_t >

using	class_to_set_t = std::vector< set_t >

using	class_to_state_t = std::vector< state_t >

Private Member Functions
std::ostream &	print_ (const set_t &ss, std::ostream &o) const

std::ostream &	print_ (const class_to_set_t &c2ss, std::ostream &o) const

void	clear ()

class_t	make_class (set_t &&set, class_t number=class_invalid)
	Make a new class with the given set of states. More...

class_t	out_class (state_t s, label_t l)
	The destination class of s with l in a. More...

Static Private Member Functions
static constexpr const char *	me ()

Private Attributes
const automaton_t &	a_
	Input automaton, supplied at construction time. More...

const labelset_t_of< Aut > ::genset_t	gs_
	The generators. More...

unsigned	num_classes_ = 0

class_to_set_t	class_to_set_

state_to_class_t	state_to_class_

class_to_state_t	class_to_res_state_

std::unordered_map< state_t, std::unordered_map< label_t, state_t > >	out_
	An auxiliary data structure enabling fast access to transitions from a given state and label, in random order. More...

Static Private Attributes
static constexpr class_t	class_invalid = -1
	An invalid class. More...

Detailed Description

template<typename Aut>
class vcsn::detail_moore::minimizer< Aut >

Definition at line 22 of file minimize-moore.hh.

Member Typedef Documentation

template<typename Aut>

using vcsn::detail_moore::minimizer< Aut >::automaton_t = Aut

private

Definition at line 29 of file minimize-moore.hh.

template<typename Aut>

using vcsn::detail_moore::minimizer< Aut >::class_t = unsigned

private

Definition at line 39 of file minimize-moore.hh.

template<typename Aut>

using vcsn::detail_moore::minimizer< Aut >::class_to_set_t = std::vector<set_t>

private

Definition at line 44 of file minimize-moore.hh.

template<typename Aut>

using vcsn::detail_moore::minimizer< Aut >::class_to_state_t = std::vector<state_t>

private

Definition at line 45 of file minimize-moore.hh.

template<typename Aut>

using vcsn::detail_moore::minimizer< Aut >::classes_t = std::vector<class_t>

private

Definition at line 40 of file minimize-moore.hh.

template<typename Aut>

using vcsn::detail_moore::minimizer< Aut >::label_t = label_t_of<automaton_t>

private

Definition at line 37 of file minimize-moore.hh.

template<typename Aut>

using vcsn::detail_moore::minimizer< Aut >::set_t = std::vector<state_t>

private

Definition at line 41 of file minimize-moore.hh.

template<typename Aut>

using vcsn::detail_moore::minimizer< Aut >::state_t = state_t_of<automaton_t>

private

Definition at line 38 of file minimize-moore.hh.

template<typename Aut>

using vcsn::detail_moore::minimizer< Aut >::state_to_class_t = std::unordered_map<state_t, class_t>

private

Definition at line 42 of file minimize-moore.hh.

template<typename Aut>

using vcsn::detail_moore::minimizer< Aut >::target_class_to_states_t = std::unordered_map<class_t, set_t>

private

Definition at line 43 of file minimize-moore.hh.

Constructor & Destructor Documentation

template<typename Aut>

vcsn::detail_moore::minimizer< Aut >::minimizer ( const Aut & a )

inline

Definition at line 136 of file minimize-moore.hh.

References vcsn::detail_moore::minimizer< Aut >::a_, vcsn::is_deterministic(), vcsn::is_trim(), vcsn::detail_moore::minimizer< Aut >::me(), vcsn::detail_moore::minimizer< Aut >::out_, and vcsn::require().

Here is the call graph for this function:

Member Function Documentation

template<typename Aut>

void vcsn::detail_moore::minimizer< Aut >::build_classes_ ( )

inline

Build the initial classes, and split until fix point.

Definition at line 149 of file minimize-moore.hh.

References vcsn::detail_moore::minimizer< Aut >::a_, vcsn::detail_moore::minimizer< Aut >::class_invalid, vcsn::detail_moore::minimizer< Aut >::class_to_set_, vcsn::detail_moore::minimizer< Aut >::gs_, vcsn::detail_moore::minimizer< Aut >::make_class(), vcsn::detail_moore::minimizer< Aut >::num_classes_, and vcsn::detail_moore::minimizer< Aut >::out_class().

Referenced by vcsn::detail_moore::minimizer< Aut >::operator()().

Here is the call graph for this function:

template<typename Aut>

void vcsn::detail_moore::minimizer< Aut >::clear ( )

inlineprivate

Definition at line 91 of file minimize-moore.hh.

References vcsn::detail_moore::minimizer< Aut >::class_to_res_state_, vcsn::detail_moore::minimizer< Aut >::class_to_set_, vcsn::detail_moore::minimizer< Aut >::num_classes_, vcsn::detail_moore::minimizer< Aut >::out_, and vcsn::detail_moore::minimizer< Aut >::state_to_class_.

template<typename Aut>

class_t vcsn::detail_moore::minimizer< Aut >::make_class	(	set_t &&	set,
		class_t	number = `class_invalid`
	)

inlineprivate

Make a new class with the given set of states.

Definition at line 101 of file minimize-moore.hh.

References vcsn::detail_moore::minimizer< Aut >::class_invalid, vcsn::detail_moore::minimizer< Aut >::class_to_set_, vcsn::detail_moore::minimizer< Aut >::num_classes_, and vcsn::detail_moore::minimizer< Aut >::state_to_class_.

Referenced by vcsn::detail_moore::minimizer< Aut >::build_classes_().

template<typename Aut>

static constexpr const char* vcsn::detail_moore::minimizer< Aut >::me ( )

inlinestaticprivate

Definition at line 47 of file minimize-moore.hh.

Referenced by vcsn::detail_moore::minimizer< Aut >::minimizer().

template<typename Aut>

partition_automaton<automaton_t> vcsn::detail_moore::minimizer< Aut >::operator() ( )

inline

Return the quotient.

Definition at line 207 of file minimize-moore.hh.

References vcsn::detail_moore::minimizer< Aut >::a_, vcsn::detail_moore::minimizer< Aut >::build_classes_(), vcsn::detail_moore::minimizer< Aut >::class_to_set_, and vcsn::quotient().

Here is the call graph for this function:

template<typename Aut>

class_t vcsn::detail_moore::minimizer< Aut >::out_class	(	state_t	s,
		label_t	l
	)

inlineprivate

The destination class of s with l in a.

Return class_invalid if s has no successor with l.

Definition at line 124 of file minimize-moore.hh.

References vcsn::detail_moore::minimizer< Aut >::class_invalid, vcsn::detail_moore::minimizer< Aut >::out_, and vcsn::detail_moore::minimizer< Aut >::state_to_class_.

Referenced by vcsn::detail_moore::minimizer< Aut >::build_classes_().

template<typename Aut>

std::ostream& vcsn::detail_moore::minimizer< Aut >::print_	(	const set_t &	ss,
		std::ostream &	o
	)		const

inlineprivate

Definition at line 58 of file minimize-moore.hh.

Referenced by vcsn::detail_moore::minimizer< Aut >::print_().

template<typename Aut>

std::ostream& vcsn::detail_moore::minimizer< Aut >::print_	(	const class_to_set_t &	c2ss,
		std::ostream &	o
	)		const

inlineprivate

Definition at line 69 of file minimize-moore.hh.

References vcsn::detail_moore::minimizer< Aut >::print_().

Here is the call graph for this function:

Member Data Documentation

template<typename Aut>

const automaton_t& vcsn::detail_moore::minimizer< Aut >::a_

private

Input automaton, supplied at construction time.

Definition at line 32 of file minimize-moore.hh.

Referenced by vcsn::detail_moore::minimizer< Aut >::build_classes_(), vcsn::detail_moore::minimizer< Aut >::minimizer(), and vcsn::detail_moore::minimizer< Aut >::operator()().

template<typename Aut>

constexpr class_t vcsn::detail_moore::minimizer< Aut >::class_invalid = -1

staticprivate

An invalid class.

Definition at line 50 of file minimize-moore.hh.

Referenced by vcsn::detail_moore::minimizer< Aut >::build_classes_(), vcsn::detail_moore::minimizer< Aut >::make_class(), and vcsn::detail_moore::minimizer< Aut >::out_class().

template<typename Aut>

class_to_state_t vcsn::detail_moore::minimizer< Aut >::class_to_res_state_

private

Definition at line 56 of file minimize-moore.hh.

Referenced by vcsn::detail_moore::minimizer< Aut >::clear().

template<typename Aut>

class_to_set_t vcsn::detail_moore::minimizer< Aut >::class_to_set_

private

Definition at line 54 of file minimize-moore.hh.

Referenced by vcsn::detail_moore::minimizer< Aut >::build_classes_(), vcsn::detail_moore::minimizer< Aut >::clear(), vcsn::detail_moore::minimizer< Aut >::make_class(), and vcsn::detail_moore::minimizer< Aut >::operator()().

template<typename Aut>

const labelset_t_of<Aut>::genset_t vcsn::detail_moore::minimizer< Aut >::gs_

private

The generators.

Definition at line 35 of file minimize-moore.hh.

Referenced by vcsn::detail_moore::minimizer< Aut >::build_classes_().

template<typename Aut>

unsigned vcsn::detail_moore::minimizer< Aut >::num_classes_ = 0

private

Definition at line 51 of file minimize-moore.hh.

Referenced by vcsn::detail_moore::minimizer< Aut >::build_classes_(), vcsn::detail_moore::minimizer< Aut >::clear(), and vcsn::detail_moore::minimizer< Aut >::make_class().

template<typename Aut>

std::unordered_map<state_t, std::unordered_map<label_t, state_t> > vcsn::detail_moore::minimizer< Aut >::out_

private

An auxiliary data structure enabling fast access to transitions from a given state and label, in random order.

This is a clear win for automata with many transitions between a couple of states. FIXME: this uglyish hash-of-hashes is slightly faster than an unordered_map of pairs, as of GCC 4.8.2 on Luca's amd64 laptop, compiled with -O3.

Definition at line 89 of file minimize-moore.hh.

Referenced by vcsn::detail_moore::minimizer< Aut >::clear(), vcsn::detail_moore::minimizer< Aut >::minimizer(), and vcsn::detail_moore::minimizer< Aut >::out_class().

template<typename Aut>

state_to_class_t vcsn::detail_moore::minimizer< Aut >::state_to_class_

private

Definition at line 55 of file minimize-moore.hh.

Referenced by vcsn::detail_moore::minimizer< Aut >::clear(), vcsn::detail_moore::minimizer< Aut >::make_class(), and vcsn::detail_moore::minimizer< Aut >::out_class().

The documentation for this class was generated from the following file: