Vcsn  2.4
Be Rational
push-weights.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <vcsn/algos/distance.hh>
4 #include <vcsn/dyn/automaton.hh>
5 #include <vcsn/dyn/fwd.hh>
7 
8 namespace vcsn
9 {
10  /*--------------.
11  | push weights. |
12  `--------------*/
13 
16  template <Automaton Aut>
17  weight_t_of<Aut>
19  {
20  auto d = ss_shortest_distance(aut, s0);
21  return d[aut->post()];
22  }
23 
26  template <Automaton Aut>
27  std::unordered_map<state_t_of<Aut>, weight_t_of<Aut>>
29  {
30  std::unordered_map<state_t_of<Aut>, weight_t_of<Aut>> res;
31  for (auto s : aut->states())
32  {
33  auto w = shortest_distance_to_finals(aut, s);
34  res.emplace(s, w);
35  }
36  return res;
37  }
38 
42  template <Automaton Aut>
43  auto
44  push_weights(const Aut& aut)
45  -> decltype(::vcsn::copy(aut))
46  {
47  auto res = ::vcsn::copy(aut);
48  auto distances = shortest_distance_to_finals(res);
49  auto ws = *res->weightset();
50  distances[res->post()] = ws.one();
51  for (auto t : all_transitions(res))
52  {
53  auto ds = distances[res->src_of(t)];
54  auto de = distances[res->dst_of(t)];
55  auto w = ws.mul(res->weight_of(t), de);
56  if (res->src_of(t) == res->pre())
57  res->set_weight(t, de);
58  else if (!ws.is_zero(ds))
59  res->set_weight(t, ws.rdivide(w, ds));
60  }
61  return res;
62  }
63 
64  namespace dyn
65  {
66  namespace detail
67  {
69  template <Automaton Aut>
70  automaton
71  push_weights(const automaton& aut)
72  {
73  const auto& a = aut->as<Aut>();
75  }
76  }
77  }
78 
79 } // namespace vcsn
return res
Definition: multiply.hh:398
weight_t_of< Aut > shortest_distance_to_finals(Aut aut, state_t_of< Aut > s0)
Find shorhest of s0 to the final states of aut by using single source shortest distance.
Definition: push-weights.hh:18
automaton push_weights(const automaton &aut)
Bridge.
Definition: push-weights.hh:71
Definition: a-star.hh:8
typename detail::weight_t_of_impl< base_t< ValueSet >>::type weight_t_of
Definition: traits.hh:66
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
Definition: traits.hh:64
A dyn automaton.
Definition: automaton.hh:17
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 ...
Definition: copy.hh:322
auto & as()
Extract wrapped typed automaton.
Definition: automaton.hh:37
auto push_weights(const Aut &aut) -> decltype(::vcsn::copy(aut))
The algorithm weight pushing.
Definition: push-weights.hh:44
auto all_transitions(const Aut &aut)
All the transition indexes between all states (including pre and post).
Definition: automaton.hh:213
std::vector< weight_t_of< Aut > > ss_shortest_distance(const Aut &aut, state_t_of< Aut > s0)
Single source shortest distance.
Definition: distance.hh:28