Vcsn  2.3
Be Rational
is-synchronized.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <stack>
4 #include <vector>
5 #include <unordered_map>
6 
7 #include <boost/bimap.hpp>
8 #include <boost/bimap/unordered_set_of.hpp>
9 
10 #include <vcsn/algos/fwd.hh>
12 #include <vcsn/core/automaton.hh> // all_out
13 #include <vcsn/ctx/context.hh>
14 #include <vcsn/dyn/automaton.hh> // dyn::make_automaton
15 #include <vcsn/misc/bimap.hh>
16 #include <vcsn/misc/pair.hh> // hash
17 #include <vcsn/misc/tuple.hh> // index_sequence
18 #include <vcsn/misc/unordered_map.hh> // has
19 
20 namespace vcsn
21 {
22  namespace detail
23  {
24 
30  template <Automaton Aut>
31  class delay_automaton_impl
32  : public automaton_decorator<fresh_automaton_t_of<Aut>>
33  {
34  public:
35  using automaton_t = Aut;
42 
44  template <std::size_t... I>
46 
47  static constexpr size_t number_of_tapes = labelset_t_of<Aut>::size();
48 
50 
51  static constexpr index_t indices = {};
52 
54  using delay_t = std::array<size_t, number_of_tapes>;
55 
57  using state_name_t = std::pair<state_t, delay_t>;
58 
60  using bimap_t = boost::bimap<boost::bimaps::unordered_set_of<state_name_t>, boost::bimaps::unordered_set_of<state_t>>;
61  using map_t = typename bimap_t::left_map;
62  using origins_t = typename bimap_t::right_map;
63 
64  template <size_t I>
65  using tape_labelset_t = typename labelset_t::template valueset_t<I>;
66 
68  : super_t(aut->context())
69  , aut_(aut)
70  {
71  map_().insert({{this->pre(), delay_t{}}, aut->pre()});
72  map_().insert({{this->post(), delay_t{}}, aut->post()});
73  }
74 
76  static symbol sname()
77  {
78  static auto res = symbol{"delay_automaton<"
80  return res;
81  }
82 
83  std::ostream& print_set(std::ostream& o, format fmt = {}) const
84  {
85  o << "delay_automaton<";
86  super_t::print_set(o, fmt);
87  return o << '>';
88  }
89 
92  state_t state(const state_name_t& r)
93  {
94  if (r.first == aut_->post())
95  return this->post();
96  state_t res;
97  auto i = map_().find(r);
98  if (i == std::end(map_()))
99  {
100  res = super_t::new_state();
101  // Emplace is not available because of the internals of bimap
102  map_().insert({r, res});
103  todo_.push(r);
104  }
105  else
106  res = i->second;
107  return res;
108  }
109 
110  using super_t::new_transition;
111 
112  void
113  new_transition(const state_name_t& src, const state_name_t& dst,
114  const label_t& l, const weight_t& w)
115  {
116  super_t::new_transition(state(src), state(dst), l, w);
117  }
118 
119  bool state_has_name(state_t s) const
120  {
121  return has(origins(), s);
122  }
123 
124  std::ostream&
125  print_state_name(state_t s, std::ostream& o,
126  format fmt = {},
127  bool = false) const
128  {
129  auto ns = origins().at(s);
130  aut_->print_state_name(ns.first, o, fmt, true);
131  o << ":(";
132  auto a = ns.second;
133  for (int i = 0; i < a.size() - 1; i++)
134  o << a[i] << ',';
135  if (a.size())
136  o << a[a.size() - 1];
137  o << ')';
138  return o;
139  }
140 
141  delay_t delay_of(state_t s)
142  {
143  auto i = origins().find(s);
144  if (i == std::end(origins()))
145  return {};
146  else
147  return i->second.second;
148  }
149 
150  const origins_t&
151  origins() const
152  {
153  return bimap_.right;
154  }
155 
156  map_t&
157  map_()
158  {
159  return bimap_.left;
160  }
161 
163  std::stack<state_name_t, std::vector<state_name_t>> todo_;
165  bimap_t bimap_;
167  automaton_t aut_;
168  };
169 
170  template <Automaton Aut>
171  class synchronize_checker
172  {
173  static_assert(context_t_of<Aut>::is_lat,
174  "synchronize: automaton labelset must be a tupleset");
175 
176  public:
177  using automaton_t = Aut;
178  using out_automaton_t = delay_automaton<automaton_t>;
179  using state_t = state_t_of<automaton_t>;
180  using labelset_t = labelset_t_of<out_automaton_t>;
181  using label_t = typename labelset_t::value_t;
182  using delay_t = typename out_automaton_t::element_type::delay_t;
183  using state_name_t = typename out_automaton_t::element_type::state_name_t;
184 
185  template <size_t I>
186  using tape_labelset_t = typename labelset_t::template valueset_t<I>;
187 
189  template <std::size_t... I>
190  using seq = vcsn::detail::index_sequence<I...>;
191 
192 
193  synchronize_checker(const automaton_t& aut)
194  : in_aut_(aut), out_aut_(make_shared_ptr<out_automaton_t>(aut))
195  {}
196 
204  bool is_synchronized()
205  {
206  // tag the states with the delays
207  value_automaton();
208  for (auto s : out_aut_->states())
209  {
210  delay_t d = out_aut_->delay_of(s);
211  if (d != delay_t{})
212  for (auto tr : out(out_aut_, s))
213  {
214  if (out_aut_->labelset()->is_one(out_aut_->label_of(tr)))
215  continue;
216  auto dst = out_aut_->dst_of(tr);
217  if (out_aut_->post() == dst)
218  continue;
219  delay_t dst_d = out_aut_->delay_of(dst);
220  for (size_t i = 0; i < out_aut_->number_of_tapes; i++) {
221  if (d[i] && dst_d[i] <= d[i])
222  return false;
223  }
224  }
225  }
226  return true;
227  }
228 
229  out_automaton_t
230  make_delay_automaton()
231  {
232  value_automaton();
233  return out_aut_;
234  }
235 
236  private:
237 
238  /*
239  * Compute the automaton with states tagged with their delays.
240  *
241  * If split, create the artificial states required for synchronizing.
242  */
243  void value_automaton()
244  {
245  out_aut_->todo_.emplace(in_aut_->pre(), delay_t{});
246 
247  while (!out_aut_->todo_.empty())
248  {
249  auto val_state = std::move(out_aut_->todo_.top());
250  auto st = val_state.first;
251  delay_t delay = val_state.second;
252  out_aut_->todo_.pop();
253  for (auto t : all_out(in_aut_, st))
254  {
255  auto l = in_aut_->label_of(t);
256  auto dst = in_aut_->dst_of(t);
257  delay_t d = add_delay_(delay, l, out_aut_->indices);
258  state_name_t new_state(dst, d);
259  out_aut_->new_transition(val_state,
260  new_state,
261  l,
262  in_aut_->weight_of(t));
263  }
264  }
265  }
266 
268  template <size_t... I>
269  delay_t
270  add_delay_(delay_t d, const label_t& l, seq<I...>) const
271  {
272  delay_t del
273  = {(std::get<I>(d) + tape_labelset_t<I>::size(std::get<I>(l)))...};
274  size_t min = *std::min_element(begin(del), end(del));
275  return {(std::get<I>(del) - min)...};
276  }
277 
278  automaton_t in_aut_;
279  out_automaton_t out_aut_;
280  };
281 
282  template <Automaton Aut>
283  bool is_synchronized(const Aut& aut)
284  {
285  synchronize_checker<Aut> s(aut);
286  return s.is_synchronized();
287  }
288 
289  template <Automaton Aut>
290  delay_automaton<Aut>
291  make_delay_automaton(const Aut& aut)
292  {
293  synchronize_checker<Aut> s(aut);
294  return s.make_delay_automaton();
295  }
296 
297  }
298 
299  /*------------------.
300  | is_synchronized. |
301  `------------------*/
302 
307  template <Automaton Aut>
308  bool
309  is_synchronized(const Aut& aut)
310  {
311  return detail::is_synchronized(aut);
312  }
313 
314  namespace dyn
315  {
316  namespace detail
317  {
319  template <Automaton Aut>
320  bool is_synchronized(const automaton& aut)
321  {
322  return vcsn::is_synchronized(aut->as<Aut>());
323  }
324  }
325  }
326 
327  /*------------------.
328  | delay_automaton. |
329  `------------------*/
330 
335  template <Automaton Aut>
336  auto
337  make_delay_automaton(const Aut& aut)
338  -> decltype(detail::make_delay_automaton(aut))
339  {
340  return detail::make_delay_automaton(aut);
341  }
342 
343  namespace dyn
344  {
345  namespace detail
346  {
348  template <Automaton Aut>
349  automaton delay_automaton(const automaton& aut)
350  {
351  return vcsn::make_delay_automaton(aut->as<Aut>());
352  }
353  }
354  }
355 }
typename bimap_t::left_map map_t
static symbol sname()
Static name.
typename detail::weight_t_of_impl< base_t< ValueSet >>::type weight_t_of
Definition: traits.hh:66
boost::flyweight< std::string, boost::flyweights::no_tracking, boost::flyweights::intermodule_holder > symbol
An internalized string.
Definition: symbol.hh:23
static constexpr auto pre(Args &&...args) -> decltype(element_type::pre(std::forward< Args >(args)...))
symbol sname()
Definition: name.hh:65
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
Definition: traits.hh:63
labelset_t_of< super_t > labelset_t
size_t size(const ExpSet &rs, const typename ExpSet::value_t &r)
Aggregate an automaton, and forward calls to it.
static constexpr index_t indices
auto print_set(Args &&...args) const -> decltype(aut_-> print_set(std::forward< Args >(args)...))
typename detail::context_t_of_impl< base_t< ValueSet >>::type context_t_of
Definition: traits.hh:61
return res
Definition: multiply.hh:398
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
Definition: traits.hh:64
static constexpr auto post(Args &&...args) -> decltype(element_type::post(std::forward< Args >(args)...))
Definition: a-star.hh:8
typename detail::label_t_of_impl< base_t< ValueSet >>::type label_t_of
Definition: traits.hh:62
An input/output format for valuesets.
Definition: format.hh:13
boost::bimap< boost::bimaps::unordered_set_of< state_name_t >, boost::bimaps::unordered_set_of< state_t >> bimap_t
Symbolic states to state handlers.
typename bimap_t::right_map origins_t
delay_automaton_impl(const automaton_t &aut)
std::pair< state_t, delay_t > state_name_t
State + delay.
context_t_of< super_t > context_t
typename labelset_t::template valueset_t< I > tape_labelset_t
std::ostream & print_set(std::ostream &o, format fmt={}) const
std::array< size_t, number_of_tapes > delay_t
The delay associated with each state.
static constexpr size_t number_of_tapes
automaton_t aut_
The original automaton.