#include <reduce.hh>

Collaboration diagram for vcsn::detail::left_reductioner< Aut >:

Public Types
using	z_weight_t = vcsn::detail::z_impl::value_t
	Specializations for Q and R. More...

using	q_weight_t = vcsn::detail::q_impl::value_t

using	r_weight_t = vcsn::detail::r_impl::value_t

Public Member Functions
	left_reductioner (const automaton_t &input)

void	linear_representation ()
	Create the linear representation of the input. More...

void	product_vector_matrix (const vector_t &v, const matrix_t &m, vector_t &res)
	Computes the product of a row vector with a matrix. More...

weight_t	scalar_product (const vector_t &v, const vector_t &w)
	Computes the scalar product of two vectors. More...

unsigned	find_pivot_by_norm (const vector_t &v, unsigned begin, unsigned *permutation)

void	z_reduce_vector (vector_t &vbasis, vector_t &current, unsigned nb, unsigned *permutation)

void	z_vector_in_new_basis (std::vector< vector_t > &basis, vector_t &current, vector_t &new_vector, unsigned *permutation)

unsigned	find_pivot (const vector_t &v, unsigned begin, unsigned *permutation)
	Return the first (w.r.t the column permutation) non zero element as pivot. More...

weight_t	reduce_vector (vector_t &vbasis, vector_t &current, unsigned b, unsigned *permutation)
	Reduce a vector w.r.t. More...

void	normalisation_vector (vector_t &v, unsigned pivot, unsigned *permutation)
	Normalize the basis vector such that its pivot is equal to 1. More...

void	bottom_up_reduction (std::vector< vector_t > &basis, unsigned *permutation)
	Apply reduction to vectors of the basis to maximize the number of zeros. More...

void	vector_in_new_basis (std::vector< vector_t > &basis, vector_t &current, vector_t &new_vector, unsigned *permutation)
	Compute the coordinate of a vector in the new basis. More...

output_automaton_t	operator() ()
	Core algorithm This algorithm computes a basis of I.mu(w). More...

Static Public Member Functions
static weight_t	norm (const q_weight_t &w)

static weight_t	norm (const r_weight_t &w)
	Norm for real numbers; a "stable" pivot should minimize this norm. More...

static weight_t	norm (const z_weight_t &w)
	Norm for integers. More...

static z_weight_t	gcd (z_weight_t x, z_weight_t y, z_weight_t &a, z_weight_t &b)

Private Types
using	automaton_t = Aut

using	context_t = context_t_of< automaton_t >

using	weightset_t = typename context_t::weightset_t

using	output_automaton_t = fresh_automaton_t_of< automaton_t >

using	label_t = label_t_of< automaton_t >

using	state_t = state_t_of< automaton_t >

using	output_state_t = state_t_of< output_automaton_t >

using	weight_t = typename context_t::weight_t

using	vector_t = std::vector< weight_t >

using	matrix_t = std::vector< std::map< std::size_t, weight_t > >

using	matrix_set_t = std::map< label_t, matrix_t >

Private Attributes
automaton_t	input_

const weightset_t_of< automaton_t >	ws_ = *input_->weightset()

output_automaton_t	res_

unsigned	dimension

vector_t	init

vector_t	final

matrix_set_t	letter_matrix_set

Detailed Description

template<Automaton Aut>
class vcsn::detail::left_reductioner< Aut >

Definition at line 189 of file reduce.hh.

Member Typedef Documentation

template<Automaton Aut>

using vcsn::detail::left_reductioner< Aut >::automaton_t = Aut

private

Definition at line 194 of file reduce.hh.

template<Automaton Aut>

using vcsn::detail::left_reductioner< Aut >::context_t = context_t_of<automaton_t>

private

Definition at line 195 of file reduce.hh.

template<Automaton Aut>

using vcsn::detail::left_reductioner< Aut >::label_t = label_t_of<automaton_t>

private

Definition at line 198 of file reduce.hh.

template<Automaton Aut>

using vcsn::detail::left_reductioner< Aut >::matrix_set_t = std::map<label_t, matrix_t>

private

Definition at line 204 of file reduce.hh.

template<Automaton Aut>

using vcsn::detail::left_reductioner< Aut >::matrix_t = std::vector<std::map<std::size_t, weight_t> >

private

Definition at line 203 of file reduce.hh.

template<Automaton Aut>

using vcsn::detail::left_reductioner< Aut >::output_automaton_t = fresh_automaton_t_of<automaton_t>

private

Definition at line 197 of file reduce.hh.

template<Automaton Aut>

using vcsn::detail::left_reductioner< Aut >::output_state_t = state_t_of<output_automaton_t>

private

Definition at line 200 of file reduce.hh.

template<Automaton Aut>

using vcsn::detail::left_reductioner< Aut >::q_weight_t = vcsn::detail::q_impl::value_t

Definition at line 269 of file reduce.hh.

template<Automaton Aut>

using vcsn::detail::left_reductioner< Aut >::r_weight_t = vcsn::detail::r_impl::value_t

Definition at line 270 of file reduce.hh.

template<Automaton Aut>

using vcsn::detail::left_reductioner< Aut >::state_t = state_t_of<automaton_t>

private

Definition at line 199 of file reduce.hh.

template<Automaton Aut>

using vcsn::detail::left_reductioner< Aut >::vector_t = std::vector<weight_t>

private

Definition at line 202 of file reduce.hh.

template<Automaton Aut>

using vcsn::detail::left_reductioner< Aut >::weight_t = typename context_t::weight_t

private

Definition at line 201 of file reduce.hh.

template<Automaton Aut>

using vcsn::detail::left_reductioner< Aut >::weightset_t = typename context_t::weightset_t

private

Definition at line 196 of file reduce.hh.

template<Automaton Aut>

using vcsn::detail::left_reductioner< Aut >::z_weight_t = vcsn::detail::z_impl::value_t

Specializations for Q and R.

Definition at line 268 of file reduce.hh.

Constructor & Destructor Documentation

template<Automaton Aut>

vcsn::detail::left_reductioner< Aut >::left_reductioner ( const automaton_t & input )

inline

Definition at line 207 of file reduce.hh.

Member Function Documentation

template<Automaton Aut>

void vcsn::detail::left_reductioner< Aut >::bottom_up_reduction	(	std::vector< vector_t > &	basis,
		unsigned *	permutation
	)

inline

Apply reduction to vectors of the basis to maximize the number of zeros.

Definition at line 462 of file reduce.hh.

References vcsn::detail::left_reductioner< Aut >::reduce_vector().

Here is the call graph for this function:

template<Automaton Aut>

unsigned vcsn::detail::left_reductioner< Aut >::find_pivot	(	const vector_t &	v,
		unsigned	begin,
		unsigned *	permutation
	)

inline

Return the first (w.r.t the column permutation) non zero element as pivot.

Definition at line 413 of file reduce.hh.

References vcsn::detail::left_reductioner< Aut >::dimension, and vcsn::detail::left_reductioner< Aut >::ws_.

template<Automaton Aut>

unsigned vcsn::detail::left_reductioner< Aut >::find_pivot_by_norm	(	const vector_t &	v,
		unsigned	begin,
		unsigned *	permutation
	)

inline

Definition at line 301 of file reduce.hh.

References vcsn::detail::left_reductioner< Aut >::dimension, vcsn::detail::left_reductioner< Aut >::norm(), and vcsn::detail::left_reductioner< Aut >::ws_.

Here is the call graph for this function:

template<Automaton Aut>

static z_weight_t vcsn::detail::left_reductioner< Aut >::gcd	(	z_weight_t	x,
		z_weight_t	y,
		z_weight_t &	a,
		z_weight_t &	b
	)

inlinestatic

Definition at line 325 of file reduce.hh.

Referenced by vcsn::detail::left_reductioner< Aut >::z_reduce_vector().

template<Automaton Aut>

void vcsn::detail::left_reductioner< Aut >::linear_representation ( )

inline

Create the linear representation of the input.

Definition at line 213 of file reduce.hh.

References vcsn::detail::left_reductioner< Aut >::dimension, vcsn::detail::final_transitions(), vcsn::detail::left_reductioner< Aut >::init, vcsn::detail::initial_transitions(), vcsn::detail::left_reductioner< Aut >::input_, vcsn::detail::left_reductioner< Aut >::letter_matrix_set, and vcsn::detail::transitions().

Referenced by vcsn::detail::left_reductioner< Aut >::operator()().

Here is the call graph for this function:

template<Automaton Aut>

static weight_t vcsn::detail::left_reductioner< Aut >::norm ( const q_weight_t & w )

inlinestatic

Definition at line 282 of file reduce.hh.

References vcsn::detail::q_impl::value_t::den, and vcsn::detail::q_impl::value_t::num.

Referenced by vcsn::detail::left_reductioner< Aut >::find_pivot_by_norm().

template<Automaton Aut>

static weight_t vcsn::detail::left_reductioner< Aut >::norm ( const r_weight_t & w )

inlinestatic

Norm for real numbers; a "stable" pivot should minimize this norm.

Definition at line 288 of file reduce.hh.

template<Automaton Aut>

static weight_t vcsn::detail::left_reductioner< Aut >::norm ( const z_weight_t & w )

inlinestatic

Norm for integers.

Definition at line 294 of file reduce.hh.

template<Automaton Aut>

void vcsn::detail::left_reductioner< Aut >::normalisation_vector	(	vector_t &	v,
		unsigned	pivot,
		unsigned *	permutation
	)

inline

Normalize the basis vector such that its pivot is equal to 1.

Definition at line 448 of file reduce.hh.

References vcsn::detail::left_reductioner< Aut >::dimension, and vcsn::detail::left_reductioner< Aut >::ws_.

template<Automaton Aut>

output_automaton_t vcsn::detail::left_reductioner< Aut >::operator() ( )

inline

Core algorithm This algorithm computes a basis of I.mu(w).

The basis is scaled.

An automaton where states correspond to the vectors of this basis is built

Definition at line 487 of file reduce.hh.

References vcsn::detail::left_reductioner< Aut >::dimension, vcsn::detail::left_reductioner< Aut >::init, vcsn::detail::left_reductioner< Aut >::letter_matrix_set, vcsn::detail::left_reductioner< Aut >::linear_representation(), vcsn::detail::left_reductioner< Aut >::product_vector_matrix(), vcsn::detail::left_reductioner< Aut >::res_, vcsn::detail::left_reductioner< Aut >::scalar_product(), vcsn::detail::v, and vcsn::detail::left_reductioner< Aut >::ws_.

Here is the call graph for this function:

template<Automaton Aut>

void vcsn::detail::left_reductioner< Aut >::product_vector_matrix	(	const vector_t &	v,
		const matrix_t &	m,
		vector_t &	res
	)

inline

Computes the product of a row vector with a matrix.

Definition at line 245 of file reduce.hh.

References vcsn::detail::left_reductioner< Aut >::dimension, and vcsn::detail::left_reductioner< Aut >::ws_.

Referenced by vcsn::detail::left_reductioner< Aut >::operator()().

template<Automaton Aut>

weight_t vcsn::detail::left_reductioner< Aut >::reduce_vector	(	vector_t &	vbasis,
		vector_t &	current,
		unsigned	b,
		unsigned *	permutation
	)

inline

Reduce a vector w.r.t.

a vector of the basis.

When this method is called, in vbasis and current, all the entries that come before (w.r.t the permutation) the pivot are zero. Moreover, vbasis[pivot]=1 This method computes current := current - current[pivot].vbasis

Definition at line 430 of file reduce.hh.

References vcsn::detail::left_reductioner< Aut >::dimension, and vcsn::detail::left_reductioner< Aut >::ws_.

Referenced by vcsn::detail::left_reductioner< Aut >::bottom_up_reduction(), and vcsn::detail::left_reductioner< Aut >::vector_in_new_basis().

template<Automaton Aut>

weight_t vcsn::detail::left_reductioner< Aut >::scalar_product	(	const vector_t &	v,
		const vector_t &	w
	)

inline

Computes the scalar product of two vectors.

Definition at line 258 of file reduce.hh.

References vcsn::detail::left_reductioner< Aut >::dimension, and vcsn::detail::left_reductioner< Aut >::ws_.

Referenced by vcsn::detail::left_reductioner< Aut >::operator()().

template<Automaton Aut>

void vcsn::detail::left_reductioner< Aut >::vector_in_new_basis	(	std::vector< vector_t > &	basis,
		vector_t &	current,
		vector_t &	new_vector,
		unsigned *	permutation
	)

inline

Compute the coordinate of a vector in the new basis.

Definition at line 471 of file reduce.hh.

References vcsn::detail::left_reductioner< Aut >::reduce_vector().

Here is the call graph for this function:

template<Automaton Aut>

void vcsn::detail::left_reductioner< Aut >::z_reduce_vector	(	vector_t &	vbasis,
		vector_t &	current,
		unsigned	nb,
		unsigned *	permutation
	)

inline

Definition at line 365 of file reduce.hh.

References vcsn::detail::left_reductioner< Aut >::dimension, vcsn::detail::left_reductioner< Aut >::gcd(), and vcsn::detail::left_reductioner< Aut >::ws_.

Here is the call graph for this function:

template<Automaton Aut>

void vcsn::detail::left_reductioner< Aut >::z_vector_in_new_basis	(	std::vector< vector_t > &	basis,
		vector_t &	current,
		vector_t &	new_vector,
		unsigned *	permutation
	)