Awali
Another Weighted Automata library
fsm.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_EFSM_HH
18 # define AWALI_ALGOS_EFSM_HH
19 
20 # include <algorithm>
21 # include <iostream>
22 # include <map>
23 
24 #include <awali/sttc/algos/grail.hh> // outputter
27 #include <awali/common/qfraction.cc>
28 
29 namespace awali { namespace sttc {
30 
31 
32  /*--------------------------.
33  | fsm(automaton, stream). |
34  `--------------------------*/
35  namespace internal
36  {
37 
38  template<typename T>
39  T evalf(const T& x) {
40  return x;
41  }
42 
43  double evalf(const q_fraction_t& x) {
44  return 0.1*x.num/x.den;
45  }
46 
48  template <typename LabelSet>
49  struct rank
50  {
51  static constexpr size_t value = 1;
52  };
53 
54  template <typename... LabelSet>
55  struct rank<tupleset<LabelSet...>>
56  {
57  static constexpr size_t value = sizeof...(LabelSet);
58  };
59 
65  template <typename Aut>
66  class efsmer: public outputter<Aut>
67  {
68  protected:
69  using automaton_t = Aut;
71 
72  using label_t = typename super_type::label_t;
73 
74  using super_type::os_;
75  using super_type::aut_;
76  using super_type::ls_;
77  using super_type::ws_;
78 
79  public:
80  using super_type::super_type;
81 
83  void operator()()
84  {
85  os_ <<
86  "#! /bin/sh\n"
87  "\n"
88  "me=$(basename \"$0\")\n"
89  "medir=$(mktemp -d \"/tmp/$me.XXXXXX\") || exit 1\n"
90  "\n";
91 
92  // Provide the symbols first, as when reading EFSM, knowing
93  // how \e is represented will help reading the transitions.
94  output_symbols_();
95 
96  os_ <<
97  "cat >$medir/transitions.fsm <<\\EOFSM";
98  output_transitions_();
99  os_ <<
100  "\n"
101  "EOFSM\n"
102  "\n"
103 
104  // Some OpenFST tools seem to really require an
105  // output-symbol list, even for acceptors. While
106  // fstrmepsilon perfectly works with just the isymbols,
107  // fstintersect (equivalent to our awali-product: the
108  // Hadamard product) for instance, seems to require the
109  // osymbols; this seems to be due to the fact that Open FST
110  // bases its implementation of intersect on its (transducer)
111  // composition.
112  "fstcompile" << (is_transducer ? "" : " --acceptor") << " \\\n"
113  " --keep_isymbols --isymbols=" << isymbols_ << " \\\n"
114  " --keep_osymbols --osymbols=" << osymbols_ << " \\\n"
115  " $medir/transitions.fsm \"$@\"\n"
116  "sta=$?\n"
117  "\n"
118  "rm -rf $medir\n"
119  "exit $sta" // No final \n.
120  ;
121  }
122 
123  private:
125  template <typename Label>
126  void output_label_(const Label& l, std::false_type)
127  {
128  ls_.print(l, os_);
129  }
130 
132  template <typename Label>
133  void output_label_(const Label& l, std::true_type)
134  {
135  ls_.template set<0>().print(std::get<0>(l), os_);
136  os_ << '\t';
137  ls_.template set<1>().print(std::get<1>(l), os_);
138  }
139 
140  void output_transition_(const transition_t t) override
141  {
142  aut_->print_state(aut_->src_of(t), os_);
143  if (aut_->dst_of(t) != aut_->post())
144  {
145  os_ << '\t';
146  aut_->print_state(aut_->dst_of(t), os_);
147  os_ << '\t';
148  if (ls_.is_special(aut_->label_of(t)))
149  os_ << "\\e";
150  else
151  output_label_(aut_->label_of(t), is_transducer);
152  }
153 
154  if (ws_.show_one() || !ws_.is_one(aut_->weight_of(t)))
155  {
156  os_ << '\t';
157  ws_.print(aut_->weight_of(t), os_);
158  }
159  }
160 
162  void output_transitions_()
163  {
164  // FSM format supports a single initial state, which requires,
165  // when we have several initial states, to "exhibit" pre() and
166  // spontaneous transitions. Avoid this when possible.
167  if (aut_->initial_transitions().size() != 1)
168  for (auto t : aut_->initial_transitions())
169  {
170  os_ << '\n';
171  output_transition_(t);
172  }
173 
174  // We _must_ start by the initial state.
175  {
176  std::vector<state_t> states(std::begin(aut_->states()),
177  std::end(aut_->states()));
178  std::sort(begin(states), end(states),
179  [this](state_t l, state_t r)
180  {
181  return (std::forward_as_tuple(!aut_->is_initial(l), l)
182  < std::forward_as_tuple(!aut_->is_initial(r), r));
183  });
184  for (auto s: states)
185  this->output_state_(s);
186  }
187  for (auto t : aut_->final_transitions())
188  {
189  os_ << '\n';
190  output_transition_(t);
191  }
192  }
193 
194  template <typename LabelSet, typename Labels, typename GetLabel>
195  auto add_alphabet(const LabelSet& ls, Labels& labels,
196  GetLabel get_label, int)
197  -> decltype(ls.genset(), void())
198  {
199  for (auto l : ls.genset())
200  labels.insert(get_label(ls.value(l)));
201  }
202 
203  template <typename LabelSet, typename Labels, typename GetLabel>
204  void add_alphabet(const LabelSet&, Labels&,
205  GetLabel, long)
206  {}
207 
230  template <typename LabelSet, typename GetLabel>
231  void output_symbols_(const std::string& name,
232  const LabelSet& ls,
233  GetLabel get_label)
234  {
235  // The labels we declare.
236  using labelset_t = LabelSet;
237  using label_t = typename labelset_t::value_t;
238 
239  std::set<label_t, less<labelset_t>> labels;
240  add_alphabet(*aut_->labelset(), labels, get_label, 0);
241  for (auto t : aut_->transitions())
242  labels.insert(get_label(aut_->label_of(t)));
243 
244  // Sorted per label name, which is fine, and deterministic.
245  // Start with special/epsilon. Show it as \e.
246  os_ <<
247  "cat >" << name << " <<\\EOFSM\n"
248  "\\e\t0\n";
249  size_t num = 0;
250  for (const auto& l: labels)
251  if (!ls.is_one(l))
252  {
253  ls.print(l, os_);
254  os_ << '\t' << ++num << '\n';
255  }
256  os_ <<
257  "EOFSM\n"
258  "\n";
259  }
260 
262  template <typename>
263  void
264  output_symbols_impl_(std::false_type)
265  {
266  output_symbols_(isymbols_,
267  ls_,
268  [](label_t l) { return l; });
269  }
270 
272  template <typename>
273  void
274  output_symbols_impl_(std::true_type)
275  {
276  output_symbols_(isymbols_,
277  ls_.template set<0>(),
278  [](const label_t& l) { return std::get<0>(l); });
279  output_symbols_(osymbols_,
280  ls_.template set<1>(),
281  [](const label_t& l) { return std::get<1>(l); });
282  }
283 
284  void
285  output_symbols_()
286  {
287  output_symbols_impl_<automaton_t>(is_transducer);
288  }
289 
292  using is_transducer_t =
293  std::integral_constant<bool,
294  2 <= rank<labelset_t_of<automaton_t>>::value>;
295  const is_transducer_t is_transducer = {};
296 
298  const char* isymbols_ =
299  is_transducer ? "$medir/isymbols.txt" : "$medir/symbols.txt";
301  const char* osymbols_ =
302  is_transducer ? "$medir/osymbols.txt" : "$medir/symbols.txt";
303  };
304  }
305 
306 
310  template <typename Aut>
311  std::ostream&
312  efsm(const Aut& aut, std::ostream& out)
313  {
314  internal::efsmer<Aut> efsm{aut, out};
315  efsm();
316  return out;
317  }
318 
319 }}//end of ns awali::stc
320 
321 #endif // !AWALI_ALGOS_EFSM_HH
Definition: qfraction.hh:26
den_t den
Definition: qfraction.hh:32
num_t num
Definition: qfraction.hh:31
Format automaton to EFSM format, based on FSM format.
Definition: fsm.hh:67
void operator()()
Actually output aut_ on os_.
Definition: fsm.hh:83
const automaton_t & aut_
The automaton we have to output.
Definition: grail.hh:154
typename super_type::label_t label_t
Definition: fsm.hh:72
const labelset_t_of< automaton_t > & ls_
Short-hand to the labelset.
Definition: grail.hh:158
const weightset_t & ws_
Short-hand to the weightset.
Definition: grail.hh:160
std::ostream & os_
Output stream.
Definition: grail.hh:156
Aut automaton_t
Definition: fsm.hh:69
Factor common bits in automaton formatting.
Definition: grail.hh:43
void output_state_(const state_t s)
Output transitions, sorted lexicographically on (Label, Dest).
Definition: grail.hh:96
const automaton_t & aut_
The automaton we have to output.
Definition: grail.hh:154
const labelset_t_of< automaton_t > & ls_
Short-hand to the labelset.
Definition: grail.hh:158
const weightset_t & ws_
Short-hand to the weightset.
Definition: grail.hh:160
std::ostream & os_
Output stream.
Definition: grail.hh:156
label_t_of< automaton_t > label_t
Definition: grail.hh:60
A ValueSet which is a Cartesian product of ValueSets.
Definition: tupleset.hh:80
std::vector< state_t > states(abstract_automaton_t const *aut, bool all)
static constexpr TOP< void > value
Definition: priority.hh:93
T evalf(const T &x)
Definition: fsm.hh:39
void sort(Aut a, Compare p)
Definition: sort.hh:28
std::ostream & efsm(const Aut &aut, std::ostream &out)
Format automaton to EFSM format, based on FSM format.
Definition: fsm.hh:312
Main namespace of Awali.
Definition: ato.hh:22
unsigned state_t
Definition: types.hh:21
unsigned transition_t
Definition: types.hh:22
Number of tapes.
Definition: fsm.hh:50
static constexpr size_t value
Definition: fsm.hh:51