Awali
Another Weighted Automata library
weighted_thompson.hh
Go to the documentation of this file.
1 // This file is part of Awali.
2 // Copyright 2016-2022 Sylvain Lombardy, Victor Marsault, Jacques Sakarovitch
3 //
4 // Awali is a free software: you can redistribute it and/or modify
5 // it under the terms of the GNU General Public License as published by
6 // the Free Software Foundation, either version 3 of the License, or
7 // (at your option) any later version.
8 //
9 // This program is distributed in the hope that it will be useful,
10 // but WITHOUT ANY WARRANTY; without even the implied warranty of
11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 // GNU General Public License for more details.
13 //
14 // You should have received a copy of the GNU General Public License
15 // along with this program. If not, see <http://www.gnu.org/licenses/>.
16 
17 #ifndef AWALI_ALGOS_WEIGHTED_THOMPSON_HH
18 # define AWALI_ALGOS_WEIGHTED_THOMPSON_HH
19 
20 #include <awali/sttc/ctx/fwd.hh>
21 #include <awali/sttc/ctx/traits.hh>
24 #include <awali/sttc/misc/raise.hh>
25 #include <awali/sttc/labelset/traits.hh> //nullable_of
26 
27 namespace awali { namespace sttc {
28 
29  namespace rat
30  {
33  template <typename Aut,
34  typename Context = context_t_of<Aut>
35  >
37  : public Context::const_visitor
38  {
39  public:
40  using automaton_t = Aut;
41  using context_t = Context;
44  using history_t = std::shared_ptr<string_history>;
45 
46  using super_type = typename Context::const_visitor;
47 
48  static_assert(context_t::has_one(), "requires nullable labels");
49 
50  constexpr static const char* me() { return "weighted thompson"; }
51 
52  weighted_thompson_visitor(const context_t& ctx, bool keep_history)
53  : res_(make_shared_ptr<automaton_t>(ctx)),
54  history_(std::make_shared<string_history>()),
55  keep_history_(keep_history)
56  {}
57 
59  operator()(const typename Context::ratexp_t& v)
60  {
61  if(keep_history_)
62  res_->set_history(history_);
63  v->accept(*this);
64  res_->set_initial(initial_);
65  res_->set_final(final_);
66  res_->set_final(initial_,cst_);
67  return std::move(res_);
68  }
69 
71  {
72  initial_ = res_->add_state();
73  final_ = res_->add_state();
74  cst_ = ws_.zero();
75  res_->set_state_name(initial_,"s"+std::to_string(counter));
76  res_->set_state_name(final_,"t"+std::to_string(counter++));
77  history_->add_state(initial_,"zero");
78  }
79 
81  {
82  initial_ = res_->add_state();
83  final_ = res_->add_state();
84  cst_ = ws_.one();
85  res_->set_state_name(initial_,"s"+std::to_string(counter));
86  res_->set_state_name(final_,"t"+std::to_string(counter++));
87  history_->add_state(initial_,"one");
88  }
89 
91  {
92  initial_ = res_->add_state();
93  final_ = res_->add_state();
94  res_->new_transition(initial_, final_, e.value());
95  cst_ = ws_.zero();
96  res_->set_state_name(initial_,"s"+std::to_string(counter));
97  res_->set_state_name(final_,"t"+std::to_string(counter++));
98  history_->add_state(initial_,"letter");
99  }
100 
102  {
103  state_t initial = res_->add_state();
104  state_t final = res_->add_state();
105  weight_t w=ws_.zero();
106  for (auto c: e)
107  {
108  c->accept(*this);
109  res_->new_transition(initial, initial_, epsilon_);
110  res_->new_transition(final_, final, epsilon_);
111  w=ws_.add(w,cst_);
112  }
113  initial_ = initial;
114  final_ = final;
115  cst_ = w;
116  res_->set_state_name(initial_,"s"+std::to_string(counter));
117  res_->set_state_name(final_,"t"+std::to_string(counter++));
118  history_->add_state(initial_,"sum");
119  }
120 
126 
128  {
129  state_t initial = res_->add_state();
130  e.head()->accept(*this);
131  weight_t w = cst_;
132  res_->new_transition(initial, initial_, epsilon_);
133  state_t final = 0, current = final_;
134  unsigned cnt=0;
135  for(auto c: e.tail()) {
136  c->accept(*this);
137  final = res_->add_state();
138  res_->set_state_name(final,"p"+std::to_string(counter)+"-"+std::to_string(++cnt));
139  res_->new_transition(current, initial_, epsilon_);
140  res_->new_transition(final_, final, epsilon_);
141  res_->new_transition(initial, initial_, epsilon_, w);
142  res_->new_transition(current, final, epsilon_, cst_);
143  w = ws_.mul(w, cst_);
144  current = final;
145  }
146  initial_ = initial;
147  final_ = final;
148  cst_ = w;
149  res_->set_state_name(initial_,"s"+std::to_string(counter));
150  res_->set_state_name(final_,"t"+std::to_string(counter));
151  history_->add_state(initial_,"product");
152  }
153 
155  {
156  e.sub()->accept(*this);
157  state_t initial = res_->add_state();
158  state_t final = res_->add_state();
159  weight_t w = ws_.star(cst_);
160  res_->new_transition(initial, initial_, epsilon_,w);
161  res_->new_transition(final_, final, epsilon_,w);
162  res_->new_transition(final_, initial_, epsilon_,w);
163  initial_ = initial;
164  final_ = final;
165  cst_ = w;
166  res_->set_state_name(initial_,"s"+std::to_string(counter));
167  res_->set_state_name(final_,"t"+std::to_string(counter++));
168  history_->add_state(initial_,"star");
169  }
170 
172  {
173  e.sub()->accept(*this);
174  state_t initial = res_->add_state();
175  state_t final = res_->add_state();
176  const weight_t& w = e.weight();
177  res_->new_transition(initial, initial_, epsilon_, w);
178  res_->new_transition(final_, final, epsilon_);
179  initial_ = initial;
180  final_ = final;
181  cst_ = ws_.mul(w, cst_);
182  history_->add_state(initial_,"left wgt");
183  }
184 
186  {
187  e.sub()->accept(*this);
188  state_t initial = res_->add_state();
189  state_t final = res_->add_state();
190  const weight_t& w = e.weight();
191  res_->new_transition(initial, initial_, epsilon_);
192  res_->new_transition(final_, final, epsilon_, w);
193  initial_ = initial;
194  final_ = final;
195  cst_ = ws_.mul(cst_, w);
196  history_->add_state(initial_,"right wgt");
197  }
198 
199  private:
200  automaton_t res_;
201  const weightset_t& ws_ = *res_->weightset();
202  using label_t = label_t_of<automaton_t>;
203  const label_t epsilon_ = res_->labelset()->one();
204  state_t initial_ = automaton_t::element_type::null_state();
205  state_t final_ = automaton_t::element_type::null_state();
206  weight_t cst_;
207  history_t history_;
208  bool keep_history_;
209  unsigned counter=0;
210  };
211 
212  } // rat::
213 
243  template <typename Aut,
244  typename Context = context_t_of<Aut>>
245  Aut
246  weighted_thompson(const Context& ctx, const typename Context::ratexp_t& exp, bool keep_history=true)
247  {
249  return weighted_thompson(exp);
250  }
251 
260  template <typename RatExpSet>
261  mutable_automaton<sttc::nullable_of<typename RatExpSet::context_t>>
262  weighted_thompson(const RatExpSet& rs, const typename RatExpSet::ratexp_t& exp, bool keep_history=true)
263  {
266  return weighted_thompson(exp);
267  }
268 }}//end of ns awali::stc
269 
270 #endif // !AWALI_ALGOS_WEIGHTED_THOMPSON_HH
The semiring of complex numbers.
Definition: c.hh:44
Definition: ratexp.hh:280
Definition: ratexp.hh:262
Definition: ratexp.hh:176
An inner node with multiple children.
Definition: ratexp.hh:115
An inner node implementing a weight.
Definition: ratexp.hh:208
Definition: weighted_thompson.hh:38
weight_t_of< context_t > weight_t
Definition: weighted_thompson.hh:43
AWALI_RAT_VISIT(rweight, e)
Definition: weighted_thompson.hh:185
AWALI_RAT_VISIT(atom, e)
Definition: weighted_thompson.hh:90
constexpr static const char * me()
Definition: weighted_thompson.hh:50
AWALI_RAT_VISIT(zero,)
Definition: weighted_thompson.hh:70
typename Context::const_visitor super_type
Definition: weighted_thompson.hh:46
AWALI_RAT_VISIT(one,)
Definition: weighted_thompson.hh:80
Aut automaton_t
Definition: weighted_thompson.hh:40
weightset_t_of< context_t > weightset_t
Definition: weighted_thompson.hh:42
AWALI_RAT_VISIT(sum, e)
Definition: weighted_thompson.hh:101
weighted_thompson_visitor(const context_t &ctx, bool keep_history)
Definition: weighted_thompson.hh:52
Context context_t
Definition: weighted_thompson.hh:41
AWALI_RAT_VISIT(star, e)
Definition: weighted_thompson.hh:154
std::shared_ptr< string_history > history_t
Definition: weighted_thompson.hh:44
automaton_t operator()(const typename Context::ratexp_t &v)
Definition: weighted_thompson.hh:59
AWALI_RAT_VISIT(lweight, e)
Definition: weighted_thompson.hh:171
Definition: string_history.hh:29
std::string to_string(identities i)
typename internal::label_t_of_impl< internal::base_t< ValueSet > >::type label_t_of
Helper to retrieve the type of the labels of a value set.
Definition: traits.hh:71
SharedPtr make_shared_ptr(Args &&... args)
Same as std::make_shared, but parameterized by the shared_ptr type, not the (pointed to) element_type...
Definition: memory.hh:29
typename internal::weight_t_of_impl< internal::base_t< ValueSet > >::type weight_t_of
Helper to retrieve the type of the weights of a value set.
Definition: traits.hh:81
Aut weighted_thompson(const Context &ctx, const typename Context::ratexp_t &exp, bool keep_history=true)
builds a variant of the Thompson automaton without epsilon cycles
Definition: weighted_thompson.hh:246
auto get_nullable_context(const Context &ctx) -> nullable_of< Context >
Definition: traits.hh:302
std::shared_ptr< internal::mutable_automaton_impl< Context > > mutable_automaton
Definition: mutable_automaton.hh:45
typename internal::weightset_t_of_impl< internal::base_t< ValueSet > >::type weightset_t_of
Helper to retrieve the type of the weightset of a value set.
Definition: traits.hh:86
Main namespace of Awali.
Definition: ato.hh:22
unsigned state_t
Definition: types.hh:21
#define AWALI_RAT_UNSUPPORTED(Type)
Definition: visitor.hh:73