Vcsn  2.2a Be Rational
vcsn::detail::left_reductioner< Aut > Class Template Reference

`#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_tws_ = *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
private

Definition at line 195 of file reduce.hh.

template<Automaton Aut>
 using vcsn::detail::left_reductioner< Aut >::label_t = label_t_of
private

Definition at line 198 of file reduce.hh.

template<Automaton Aut>
 using vcsn::detail::left_reductioner< Aut >::matrix_set_t = std::map
private

Definition at line 204 of file reduce.hh.

template<Automaton Aut>
 using vcsn::detail::left_reductioner< Aut >::matrix_t = std::vector >
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
private

Definition at line 197 of file reduce.hh.

template<Automaton Aut>
 using vcsn::detail::left_reductioner< Aut >::output_state_t = state_t_of
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
private

Definition at line 199 of file reduce.hh.

template<Automaton Aut>
 using vcsn::detail::left_reductioner< Aut >::vector_t = std::vector
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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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

Definition at line 385 of file reduce.hh.

## Member Data Documentation

template<Automaton Aut>
 unsigned vcsn::detail::left_reductioner< Aut >::dimension
private
template<Automaton Aut>
 vector_t vcsn::detail::left_reductioner< Aut >::final
private

Definition at line 590 of file reduce.hh.

template<Automaton Aut>
 vector_t vcsn::detail::left_reductioner< Aut >::init
private

Definition at line 589 of file reduce.hh.

template<Automaton Aut>
 automaton_t vcsn::detail::left_reductioner< Aut >::input_
private

Definition at line 582 of file reduce.hh.

template<Automaton Aut>
 matrix_set_t vcsn::detail::left_reductioner< Aut >::letter_matrix_set
private

Definition at line 591 of file reduce.hh.

template<Automaton Aut>
 output_automaton_t vcsn::detail::left_reductioner< Aut >::res_
private

Definition at line 585 of file reduce.hh.

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

template<Automaton Aut>
 const weightset_t_of vcsn::detail::left_reductioner< Aut >::ws_ = *input_->weightset()
private

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