Vcsn  2.3a
Be Rational
epsilon-remover-distance.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <stdexcept>
4 #include <type_traits>
5 #include <utility>
6 #include <vector>
7 
8 #include <vcsn/algos/copy.hh>
9 #include <vcsn/algos/distance.hh>
10 
11 namespace vcsn
12 {
13  namespace detail
14  {
19  template <Automaton Aut,
20  bool has_one = labelset_t_of<Aut>::has_one()>
22  {
23  using automaton_t = std::remove_cv_t<Aut>;
26  using weight_t = typename weightset_t::value_t;
29 
36 
43 
44  public:
45  epsilon_remover_distance(const automaton_t& aut, bool prune = true)
46  : ws_(*aut->weightset())
47  , prune_(prune)
48  , d2p_(states_size(aut),
49  aut_proper_t::element_type::null_state())
50  , p2d_(states_size(aut),
51  aut_dirty_t::element_type::null_state())
52  {
53  auto dirty_ctx = dirty_ctx_t{{}, ws_};
54  auto proper_ctx = make_proper_context(aut->context());
55  aut_dirty_ = make_shared_ptr<aut_dirty_t>(dirty_ctx);
56  aut_proper_ = make_shared_ptr<aut_proper_t>(proper_ctx);
57 
58  auto pcopier = make_copier(aut, aut_proper_);
59  auto dcopier = make_copier(aut, aut_dirty_);
60 
61  pcopier([](state_t) { return true; },
62  [&aut](transition_t t) {
63  return !aut->labelset()->is_one(aut->label_of(t));
64  }
65  );
66  dcopier([&aut](state_t s) {
67  return (!in(aut, s, aut->labelset()->one()).empty()
68  || !out(aut, s, aut->labelset()->one()).empty());
69  },
70  [&aut](transition_t t) {
71  return aut->labelset()->is_one(aut->label_of(t));
72  }
73  );
74 
75  const auto& dorigins = dcopier.state_map();
76  const auto& porigins = pcopier.state_map();
77  for (const auto& dp : dorigins)
78  {
79  auto pp = porigins.find(dp.first);
80  assert(pp != porigins.end());
81  d2p_[dp.second] = pp->second;
82  p2d_[pp->second] = dp.second;
83  }
84 
85  de_ = all_distances(aut_dirty_);
86  }
87 
88  public:
89 
91  {
92  for (auto dirty_p : aut_dirty_->states())
93  for (auto dirty_q : aut_dirty_->states())
94  {
95  weight_t dist_pq = de_[dirty_p][dirty_q];
96  if (!ws_.is_zero(dist_pq))
97  {
98  auto proper_q = d2p_[dirty_q];
99  for (auto t : all_out(aut_proper_, proper_q))
100  {
101  auto proper_p = d2p_[dirty_p];
102  auto proper_r = aut_proper_->dst_of(t);
103  label_proper_t l = aut_proper_->label_of(t);
104  weight_t w = aut_proper_->weight_of(t);
105  aut_proper_->set_transition(proper_p, proper_r, l,
106  ws_.mul(dist_pq, w));
107  }
108  }
109  }
110  if (prune_)
111  for (auto s : aut_proper_->states())
112  if (all_in(aut_proper_, s).empty())
113  aut_proper_->del_state(s);
114  return aut_proper_;
115  }
116 
117  private:
121 
123  const weightset_t& ws_;
124 
126  bool prune_;
127 
129  std::vector<state_proper_t> d2p_;
131  std::vector<state_dirty_t> p2d_;
132 
133  std::vector<std::vector<weight_t>> de_;
134  };
135 
136  template <Automaton Aut>
137  class epsilon_remover_distance<Aut, false>
138  {
139  using automaton_t = std::remove_cv_t<Aut>;
141  public:
143  : aut_(aut)
144  {}
145 
147  {
148  return copy(aut_);
149  }
150 
151  private:
153  };
154  }
155 } // namespace vcsn
size_t states_size(const Aut &aut)
The largest state number, plus one.
Definition: automaton.hh:39
transition_t_of< automaton_t > transition_t
std::vector< state_dirty_t > p2d_
proper states -> dirty states.
auto out(const Aut &aut, state_t_of< Aut > s)
Indexes of visible transitions leaving state s.
Definition: automaton.hh:84
auto all_out(const Aut &aut, state_t_of< Aut > s)
Indexes of transitions leaving state s.
Definition: automaton.hh:65
Definition: a-star.hh:8
std::vector< std::vector< weight_t > > de_
fresh_automaton_t_of< Aut, proper_ctx_t > aut_proper_t
Proper automaton.
auto make_proper_context(const context< LabelSet, WeightSet > &ctx) -> proper_context< context< LabelSet, WeightSet >>
From a context, its non-nullable context.
Definition: labelset.hh:217
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
Definition: traits.hh:64
typename detail::transition_t_of_impl< base_t< ValueSet >>::type transition_t_of
Definition: traits.hh:65
This class contains the core of the proper algorithm.
std::vector< std::vector< weight_t_of< Aut > > > all_distances(const Aut &aut)
Definition: distance.hh:107
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
Definition: traits.hh:63
detail::copier< AutIn, AutOut > make_copier(const AutIn &in, AutOut &out, bool safe=true)
Build an automaton copier.
Definition: copy.hh:256
const weightset_t & ws_
Shorthand to the weightset.
auto all_in(const Aut &aut, state_t_of< Aut > s)
Indexes of transitions entering state s.
Definition: automaton.hh:114
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
Definition: traits.hh:67
std::vector< state_proper_t > d2p_
dirty states -> proper states.
aut_proper_t aut_proper_
The automata we work on.
typename Aut::element_type::template fresh_automaton_t< Context > fresh_automaton_t_of
Given an automaton type, the type of its copies.
Definition: traits.hh:82
std::shared_ptr< detail::mutable_automaton_impl< Context >> mutable_automaton
Definition: fwd.hh:25
auto in(const Aut &aut, state_t_of< Aut > s)
Indexes of visible transitions arriving to state s.
Definition: automaton.hh:133
#define Automaton
Definition: automaton.hh:23
mutable_automaton< dirty_ctx_t > aut_dirty_t
Spontaneous automaton.
bool prune_
Whether to prune states that become inaccessible.
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
epsilon_remover_distance(const automaton_t &aut, bool prune=true)
typename detail::label_t_of_impl< base_t< ValueSet >>::type label_t_of
Definition: traits.hh:62