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