4 #include <unordered_map>
83 template <
typename Weightset>
86 template <
typename Reduc,
typename Vector>
89 unsigned begin,
unsigned* permutation)
91 return that->find_pivot(v, begin, permutation);
94 template <
typename Reduc,
typename Vector>
97 Vector& current,
unsigned b,
unsigned* permutation)
99 that->reduce_vector(vbasis, current, b, permutation);
102 template <
typename Reduc,
typename Vector>
105 unsigned pivot,
unsigned* permutation)
107 that->normalisation_vector(v, pivot, permutation);
110 template <
typename Reduc,
typename Basis>
114 that->bottom_up_reduction(basis, permutation);
117 template <
typename Reduc,
typename Basis,
typename Vector>
120 Vector& current, Vector& new_vector,
121 unsigned* permutation)
123 that->vector_in_new_basis(basis, current, new_vector, permutation);
130 template <
typename Reduc,
typename Vector>
133 unsigned begin,
unsigned* permutation)
135 return that->find_pivot_by_norm(v, begin, permutation);
142 template <
typename Reduc,
typename Vector>
145 unsigned begin,
unsigned* permutation)
147 return that->find_pivot_by_norm(v, begin, permutation);
154 template <
typename Reduc,
typename Vector>
157 unsigned begin,
unsigned* permutation)
159 return that->find_pivot_by_norm(v, begin, permutation);
162 template <
typename Reduc,
typename Vector>
165 Vector& current,
unsigned b,
unsigned* permutation)
167 that->z_reduce_vector(vbasis, current, b, permutation);
170 template <
typename Reduc,
typename Vector>
174 template <
typename Reduc,
typename Basis>
178 template <
typename Reduc,
typename Basis,
typename Vector>
181 Vector& current, Vector& new_vector,
182 unsigned* permutation)
184 that->z_vector_in_new_basis(basis, current, new_vector, permutation);
188 template <Automaton Aut>
192 "reduce: requires free labelset");
194 using automaton_t = Aut;
196 using weightset_t =
typename context_t::weightset_t;
201 using weight_t =
typename context_t::weight_t;
202 using vector_t = std::vector<weight_t>;
203 using matrix_t = std::vector<std::map<std::size_t, weight_t> > ;
204 using matrix_set_t = std::map<label_t, matrix_t>;
213 void linear_representation()
215 std::unordered_map<state_t, unsigned> state_to_index;
217 for (
auto s: input_->states())
218 state_to_index[s] = i++;
226 init[state_to_index[input_->dst_of(t)]] = input_->weight_of(t);
229 final[state_to_index[input_->src_of(t)]] = input_->weight_of(t);
233 auto it = letter_matrix_set.find(input_->label_of(t));
234 if (it == letter_matrix_set.end())
235 it = letter_matrix_set.emplace(input_->label_of(t),
236 matrix_t(dimension)).first;
237 it->second[state_to_index[input_->src_of(t)]]
238 [state_to_index[input_->dst_of(t)]] = input_->weight_of(t);
245 void product_vector_matrix(
const vector_t&
v,
249 for (
unsigned i = 0; i < dimension; i++)
252 unsigned j = it.first;
253 res[j] = ws_.add(res[j], ws_.mul(v[i], it.second));
258 weight_t scalar_product(
const vector_t& v,
261 weight_t res = ws_.zero();
262 for (
unsigned i = 0; i < dimension; ++i)
263 res = ws_.add(res, ws_.mul(v[i], w[i]));
282 static weight_t norm(
const q_weight_t& w)
284 return w.den+abs(w.num);
288 static weight_t norm(
const r_weight_t& w)
290 return fabs(w)+fabs(1/w);
294 static weight_t norm(
const z_weight_t& w)
301 find_pivot_by_norm(
const vector_t& v,
unsigned begin,
302 unsigned* permutation)
305 unsigned pivot = dimension;
306 for (
unsigned i = begin; i < dimension; ++i)
307 if (!ws_.is_zero(v[permutation[i]])
308 && (pivot == dimension
309 || ws_.less(norm(v[permutation[i]]), min)))
312 min = norm(v[permutation[i]]);
325 gcd(z_weight_t x, z_weight_t y, z_weight_t& a, z_weight_t&
b)
337 res =
gcd(-x, y, a, b);
342 res =
gcd(x, -y, a, b);
346 res =
gcd(y, x, b, a);
349 z_weight_t
z = x % y;
350 res =
gcd(y, z, b, a);
354 assert(res == a * x + b * y);
365 void z_reduce_vector(vector_t& vbasis, vector_t& current,
366 unsigned nb,
unsigned* permutation)
368 unsigned pivot = permutation[nb];
369 if (ws_.is_zero(current[pivot]))
371 weight_t bp = vbasis[pivot];
372 weight_t cp = current[pivot];
374 weight_t g =
gcd(bp, cp, a, b);
377 for (
unsigned i = nb; i < dimension; ++i)
379 weight_t tmp = current[permutation[i]];
380 current[permutation[i]] = bp*tmp - cp*vbasis[permutation[i]];
381 vbasis[permutation[i]] = a*vbasis[permutation[i]] + b*tmp;
385 void z_vector_in_new_basis(std::vector<vector_t>& basis,
386 vector_t& current, vector_t& new_vector,
387 unsigned* permutation)
389 for (
unsigned b = 0; b < basis.size(); ++
b)
391 vector_t& vbasis = basis[
b];
392 unsigned pivot = permutation[
b];
393 new_vector[
b] = current[pivot] / vbasis[pivot];
394 if (!ws_.is_zero(new_vector[b]))
396 current[pivot] = ws_.zero();
397 for (
unsigned i = b+1; i < dimension; ++i)
398 current[permutation[i]]
399 -= new_vector[b] * vbasis[permutation[i]];
413 unsigned find_pivot(
const vector_t& v,
unsigned begin,
414 unsigned* permutation)
416 for (
unsigned i = begin; i < dimension; ++i)
417 if (!ws_.is_zero(v[permutation[i]]))
430 weight_t reduce_vector(vector_t& vbasis,
431 vector_t& current,
unsigned b,
432 unsigned* permutation)
434 unsigned pivot = permutation[
b];
435 weight_t ratio = current[pivot];
436 if (ws_.is_zero(ratio))
439 current[pivot] = ws_.zero();
440 for (
unsigned i = b+1; i < dimension; ++i)
441 current[permutation[i]]
442 = ws_.sub(current[permutation[i]],
443 ws_.mul(ratio, vbasis[permutation[i]]));
448 void normalisation_vector(vector_t& v,
unsigned pivot,
449 unsigned* permutation)
451 weight_t k = v[permutation[pivot]];
454 v[permutation[pivot]] = ws_.one();
455 for (
unsigned r = pivot + 1;
r < dimension; ++
r)
456 v[permutation[
r]] = ws_.rdivide(v[permutation[
r]], k);
462 void bottom_up_reduction(std::vector<vector_t>& basis,
463 unsigned* permutation)
465 for (
unsigned b = basis.size()-1; 0 <
b; --
b)
466 for (
unsigned c = 0; c <
b; ++c)
467 reduce_vector(basis[b], basis[c], b, permutation);
471 void vector_in_new_basis(std::vector<vector_t>& basis,
472 vector_t& current, vector_t& new_vector,
473 unsigned* permutation)
475 for (
unsigned b = 0; b < basis.size(); ++
b)
476 new_vector[b] = reduce_vector(basis[b], current, b, permutation);
487 output_automaton_t operator()()
492 linear_representation();
495 std::vector<vector_t> basis;
499 unsigned permutation[dimension];
500 for (
unsigned i = 0; i < dimension; ++i)
505 unsigned pivot = type_t::find_pivot(
this, init, 0, permutation);
506 if (pivot == dimension)
509 permutation[0] = pivot;
510 permutation[pivot] = 0;
513 vector_t first(init);
514 type_t::normalisation_vector(
this, first, 0, permutation);
515 basis.push_back(first);
520 for (
unsigned nb = 0; nb < basis.size(); ++nb)
522 for (
auto mu : letter_matrix_set)
524 vector_t current(dimension);
525 product_vector_matrix(basis[nb], mu.second, current);
527 for (
unsigned b = 0; b < basis.size(); ++
b)
528 type_t::reduce_vector(
this, basis[b],
529 current, b, permutation);
532 pivot = type_t::find_pivot(
this, current, basis.size(),
534 if (pivot != dimension)
536 if (pivot != basis.size())
537 std::swap(permutation[pivot], permutation[basis.size()]);
538 type_t::normalisation_vector(
this, current,
539 basis.size(), permutation);
540 basis.push_back(current);
546 type_t::bottom_up_reduction(
this, basis, permutation);
550 std::vector<output_state_t> states(basis.size());
551 for (
unsigned b = 0; b < basis.size(); ++
b)
552 states[b] = res_->new_state();
554 vector_t vect_new_basis(basis.size());
555 type_t::vector_in_new_basis(
this, basis, init,
556 vect_new_basis, permutation);
557 for (
unsigned b = 0; b < basis.size(); ++
b)
558 res_->set_initial(states[b], vect_new_basis[b]);
561 for (
unsigned v = 0; v < basis.size(); ++
v)
563 weight_t k = scalar_product(basis[v],
final);
565 res_->set_final(states[v],k);
566 for (
auto mu : letter_matrix_set)
569 vector_t current(dimension);
570 product_vector_matrix(basis[v], mu.second, current);
571 type_t::vector_in_new_basis(
this, basis, current,
572 vect_new_basis, permutation);
573 for (
unsigned b = 0; b < basis.size(); ++
b)
574 res_->new_transition(states[v], states[b],
575 mu.first, vect_new_basis[b]);
585 output_automaton_t res_;
591 matrix_set_t letter_matrix_set;
596 template <Automaton Aut>
599 -> decltype(
copy(input))
606 template <Automaton Aut>
609 -> decltype(
copy(input))
619 template <Automaton Aut>
623 const auto& a = aut->
as<Aut>();
auto final_transitions(const Aut &aut) -> decltype(aut->all_in(aut->post()))
Indexes of transitions from (visible) final states.
weightset_mixin< detail::b_impl > b
static void bottom_up_reduction(Reduc *that, Basis &basis, unsigned *permutation)
static unsigned find_pivot(Reduc *that, const Vector &v, unsigned begin, unsigned *permutation)
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
static void vector_in_new_basis(Reduc *that, Basis &basis, Vector ¤t, Vector &new_vector, unsigned *permutation)
static unsigned find_pivot(Reduc *that, const Vector &v, unsigned begin, unsigned *permutation)
AutOut make_fresh_automaton(const AutIn &model)
Create an empty, mutable, automaton, based on another one.
auto left_reduce(const Aut &input) -> decltype(copy(input))
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
auto transitions(const Aut &aut) -> decltype(all_transitions(aut, is_special_t< Aut >
All the transition indexes between visible states.
static void reduce_vector(Reduc *that, Vector &vbasis, Vector ¤t, unsigned b, unsigned *permutation)
weightset_mixin< detail::r_impl > r
Provide a variadic mul on top of a binary mul(), and one().
auto initial_transitions(const Aut &aut) -> decltype(aut->all_out(aut->pre()))
Indexes of transitions to (visible) initial states.
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
static unsigned find_pivot(Reduc *that, const Vector &v, unsigned begin, unsigned *permutation)
static void normalisation_vector(Reduc *that, Vector &v, unsigned pivot, unsigned *permutation)
Aut transpose(const transpose_automaton< Aut > &aut)
The transpose of a transpose automaton is the original automaton.
typename detail::context_t_of_impl< base_t< ValueSet >>::type context_t_of
auto copy(const AutIn &input, KeepState keep_state, KeepTrans keep_trans) -> decltype(keep_state(input->null_state()), keep_trans(input->null_transition()), make_fresh_automaton< AutIn, AutOut >(input))
A copy of input keeping only its states that are accepted by keep_state, and transitions accepted by ...
static void vector_in_new_basis(Reduc *that, Basis &basis, Vector ¤t, Vector &new_vector, unsigned *permutation)
typename Aut::element_type::template fresh_automaton_t< Context > fresh_automaton_t_of
Given an automaton type, the type of its copies.
static unsigned find_pivot(Reduc *that, const Vector &v, unsigned begin, unsigned *permutation)
static void bottom_up_reduction(Reduc *, Basis &, unsigned *)
static void reduce_vector(Reduc *that, Vector &vbasis, Vector ¤t, unsigned b, unsigned *permutation)
auto & as()
Extract wrapped typed automaton.
ATTRIBUTE_PURE unsigned int gcd(unsigned int a, unsigned int b)
Greatest common divisor.
automaton reduce(const automaton &aut)
Bridge.
type_t
The possible types of expressions.
auto reduce(const Aut &input) -> decltype(copy(input))
typename detail::label_t_of_impl< base_t< ValueSet >>::type label_t_of
static void normalisation_vector(Reduc *, Vector &, unsigned, unsigned *)