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

Definition at line 269 of file reduce.hh.

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.

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

Member Data Documentation

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

Definition at line 590 of file reduce.hh.

template<Automaton Aut>
automaton_t vcsn::detail::left_reductioner< Aut >::input_
private
template<Automaton Aut>
matrix_set_t vcsn::detail::left_reductioner< Aut >::letter_matrix_set
private
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()().


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