Vcsn  2.2a
Be Rational
synchronizing-word.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <algorithm>
4 #include <iostream>
5 #include <limits>
6 #include <unordered_map>
7 #include <unordered_set>
8 #include <utility>
9 #include <vector>
10 
11 #include <boost/algorithm/string.hpp>
12 
13 #include <vcsn/algos/distance.hh>
14 #include <vcsn/algos/pair.hh>
15 #include <vcsn/ctx/context.hh>
16 #include <vcsn/ctx/traits.hh>
17 #include <vcsn/dyn/automaton.hh>
18 #include <vcsn/dyn/context.hh>
19 #include <vcsn/dyn/label.hh>
20 #include <vcsn/labelset/labelset.hh> // make_wordset
21 #include <vcsn/misc/algorithm.hh> // erase_if
22 #include <vcsn/misc/map.hh>
23 #include <vcsn/misc/pair.hh>
24 #include <vcsn/misc/raise.hh>
25 
26 namespace vcsn
27 {
28 
29  /*--------------------------------------.
30  | is_synchronized_by(automaton, word). |
31  `--------------------------------------*/
32 
34  template <Automaton Aut>
35  bool
36  is_synchronized_by(const Aut& aut, const word_t_of<Aut>& w)
37  {
38  using automaton_t = Aut;
39  using state_t = state_t_of<automaton_t>;
40 
41  std::unordered_set<state_t> todo;
42 
43  for (auto s : aut->states())
44  todo.insert(s);
45 
46  for (auto l : aut->labelset()->letters_of(w))
47  {
48  std::unordered_set<state_t> new_todo;
49  for (auto s : todo)
50  {
51  auto ntf = out(aut, s, l);
52  auto size = ntf.size();
53  require(0 < size,
54  "is_synchronized_by: automaton must be complete");
55  require(size < 2,
56  "is_synchronized_by: automaton must be deterministic");
57  new_todo.insert(aut->dst_of(*ntf.begin()));
58  }
59  todo = std::move(new_todo);
60  }
61 
62  return todo.size() == 1;
63  }
64 
65  namespace dyn
66  {
67  namespace detail
68  {
70  template <Automaton Aut, typename LabelSet>
71  bool
72  is_synchronized_by(const automaton& aut, const label& word)
73  {
74  const auto& a = aut->as<Aut>();
75  const auto& w = word->as<LabelSet>();
76  return vcsn::is_synchronized_by(a, w.label());
77  }
78  }
79  }
80 
81 
82  /*---------------------.
83  | word_synchronizer. |
84  `---------------------*/
85 
86  namespace detail
87  {
88  template <Automaton Aut>
90  {
91  public:
92  using automaton_t = Aut;
96 
97  private:
99 
101  using state_name_t = std::pair<state_t, state_t>;
102 
103  using dist_transition_t
104  = std::pair<unsigned, transition_t_of<pair_automaton_t>>;
105  using paths_t
106  = std::unordered_map<state_t_of<pair_automaton_t>, dist_transition_t>;
107  using path_t = typename paths_t::value_type;
108 
114  std::unordered_set<state_t> todo_;
116 
117  public:
119  : aut_(aut)
120  {}
121 
122  private:
123  void init_pair(bool keep_initials = false)
124  {
125  pair_ = pair(aut_, keep_initials);
126  paths_ = paths_ibfs(pair_, pair_->singletons());
127 
128  if (keep_initials)
129  detail::erase_if(paths_,
130  [this](const path_t& p)
131  {
132  return pair_->is_singleton(p.first);
133  });
134  }
135 
136  void init_synchro(bool keep_initials = false)
137  {
138  init_pair(keep_initials);
139  require(pair_->states().size()
140  == paths_.size() + pair_->singletons().size(),
141  "automaton is not synchronizing");
142 
143  for (auto s : pair_->states())
144  if (!pair_->is_singleton(s))
145  todo_.insert(s);
146  }
147 
148  std::vector<transition_t> recompose_path(state_t from) const
149  {
150  std::vector<transition_t> res;
151  state_t bt_curr = from;
152  while (!pair_->is_singleton(bt_curr))
153  {
154  transition_t t = paths_.find(bt_curr)->second.second;
155  res.push_back(t);
156  bt_curr = pair_->dst_of(t);
157  }
158  return res;
159  }
160 
161  int dist(state_t s) const
162  {
163  return pair_->is_singleton(s) ? 0 : paths_.find(s)->second.first;
164  }
165 
166  state_t dest_state(state_t s, const label_t& l) const
167  {
168  auto ntf = out(pair_, s, l);
169  auto size = ntf.size();
170  require(0 < size, "automaton must be complete");
171  require(size < 2, "automaton must be deterministic");
172  return pair_->dst_of(*ntf.begin());
173  }
174 
175  void apply_label(const label_t& label)
176  {
177  res_ = aut_->labelset()->mul(res_, label);
178  std::unordered_set<state_t> new_todo;
179  for (auto s : todo_)
180  {
181  auto new_state = dest_state(s, label);
182  if (!pair_->is_singleton(new_state))
183  new_todo.insert(new_state);
184  }
185  todo_ = std::move(new_todo);
186  }
187 
190  void apply_path(const std::vector<transition_t>& path)
191  {
192  for (auto t : path)
193  apply_label(pair_->label_of(t));
194  }
195 
196  public:
197 
198  // We just perform an inverse BFS from q0 and put all the accessible
199  // states in 'paths'. If the size of paths is the same than the number
200  // of states of pa (minus q0), then for each pair of states (p, q),
201  // there is a word w such that d(p, w) = d(q, w), thus the automaton is
202  // synchronizing.
204  {
205  init_pair();
206  return paths_.size() == pair_->states().size() - 1;
207  }
208 
210  {
212  }
213 
215  {
216  return cycle_();
217  }
218 
220  {
222  }
223 
225  {
227  }
228 
230  {
231  return fastsynchro_();
232  }
233 
234  private:
235  using heuristic_t = auto (word_synchronizer::*)(state_t) const -> int;
236 
238  {
239  init_synchro();
240  while (!todo_.empty())
241  {
242  int min = std::numeric_limits<int>::max();
243  state_t s_min = 0;
244  for (auto s : todo_)
245  {
246  int d = (this->*(heuristic))(s);
247  if (d < min)
248  {
249  min = d;
250  s_min = s;
251  }
252  }
253 
254  apply_path(recompose_path(s_min));
255  }
256  return res_;
257  }
258 
260  {
261  init_synchro(true);
262  bool first = true;
263  state_t previous = 0;
264  while (!todo_.empty())
265  {
266  int min = std::numeric_limits<int>::max();
267  state_t s_min = 0;
268  for (auto s : todo_)
269  {
270  state_name_t o = pair_->get_origin(s);
271  if (!first && o.first != previous && o.second != previous)
272  continue;
273  int d = dist(s);
274  if (d < min)
275  {
276  min = d;
277  s_min = s;
278  }
279  }
280 
281  const auto& path = recompose_path(s_min);
282  state_name_t pair_end
283  = pair_->get_origin(pair_->dst_of(path[path.size() - 1]));
284  assert(pair_end.first == pair_end.second);
285  previous = pair_end.first;
286  first = false;
287  apply_path(path);
288  }
289  return res_;
290  }
291 
293  {
294  init_synchro();
295 
296  // The drawback of this algorithm is that it does not guarantee us to
297  // converge, so we this to counter prevent potential infinite loops.
298  unsigned count = 0;
299  while (!todo_.empty())
300  {
301  // compute lmin = arg min { phi_3(l) } forall l in labelset
302  label_t lmin;
303  int min = std::numeric_limits<int>::max();
304  for (const auto& l : pair_->labelset()->generators())
305  {
306  int cur_min = phi_3(l);
307  if (cur_min < min)
308  {
309  min = cur_min;
310  lmin = l;
311  }
312  }
313 
314  unsigned sq_bound = aut_->states().size();
315  if (min < 0 && count++ < (sq_bound * sq_bound))
316  apply_label(lmin);
317  else
318  {
319  // fallback on the phi_2 heuristic, with a size restriction.
320  int count = 0;
321  size_t t = todo_.size();
322  int bound = std::min(aut_->states().size(), (t * t - t / 2));
323  int min = std::numeric_limits<int>::max();
324  state_t s_min = 0;
325  for (auto s : todo_)
326  {
327  if (count++ >= bound)
328  break;
329  int d = phi_2(s);
330  if (d < min)
331  {
332  min = d;
333  s_min = s;
334  }
335  }
336  apply_path(recompose_path(s_min));
337  }
338  }
339  return res_;
340  }
341 
343  int delta(state_t p, const std::vector<transition_t>& w) const
344  {
345  state_t np = p;
346  for (auto t : w)
347  np = dest_state(np, pair_->label_of(t));
348  return dist(np) - dist(p);
349  }
350 
354  int phi_1(state_t p) const
355  {
356  int res = 0;
357  auto w = recompose_path(p);
358  for (auto s: todo_)
359  if (s != p)
360  res += delta(s, w);
361  return res;
362  }
363 
366  int phi_2(state_t p) const
367  {
368  return phi_1(p) + dist(p);
369  }
370 
373  int phi_3(const label_t& l) const
374  {
375  int res = 0;
376  for (auto s: todo_)
377  res += dist(dest_state(s, l)) - dist(s);
378  return res;
379  }
380  };
381  }
382 
383 
384  /*-----------------------------.
385  | is_synchronizing(automaton). |
386  `-----------------------------*/
387 
389  template <Automaton Aut>
390  bool is_synchronizing(const Aut& aut)
391  {
393  return sync.is_synchronizing();
394  }
395 
396  namespace dyn
397  {
398  namespace detail
399  {
401  template <Automaton Aut>
402  bool is_synchronizing(const automaton& aut)
403  {
404  const auto& a = aut->as<Aut>();
405  return vcsn::is_synchronizing(a);
406  }
407  }
408  }
409 
410 
411  /*-------------------------------.
412  | synchronizing_word(automaton). |
413  `-------------------------------*/
414 
416  template <Automaton Aut>
417  word_t_of<Aut>
418  synchronizing_word(const Aut& aut, const std::string& algo = "greedy")
419  {
421  if (boost::iequals(algo, "greedy") || boost::iequals(algo, "eppstein"))
422  return sync.greedy();
423  else if (boost::iequals(algo, "cycle"))
424  return sync.cycle();
425  else if (boost::iequals(algo, "synchrop"))
426  return sync.synchroP();
427  else if (boost::iequals(algo, "synchropl"))
428  return sync.synchroPL();
429  else if (boost::iequals(algo, "fastsynchro"))
430  return sync.fastsynchro();
431  else
432  raise("synchronizing_word: invalid algorithm: ", str_escape(algo));
433  }
434 
435  namespace dyn
436  {
437  namespace detail
438  {
440  template <Automaton Aut, typename String>
441  label
442  synchronizing_word(const automaton& aut, const std::string& algo)
443  {
444  const auto& a = aut->as<Aut>();
445  auto word = vcsn::synchronizing_word(a, algo);
446  return make_label(make_wordset(*a->labelset()), word);
447  }
448  }
449  }
450 }
void apply_path(const std::vector< transition_t > &path)
"Apply" a word to the set of active states (for each state, for each label, perform s = d(s)) ...
std::unordered_set< state_t > todo_
auto(word_synchronizer::*)(state_t) const -> int heuristic_t
typename detail::label_t_of_impl< base_t< ValueSet >>::type label_t_of
Definition: traits.hh:54
A dyn automaton.
Definition: automaton.hh:19
void erase_if(Container &c, const Predicate &p)
Definition: algorithm.hh:41
word_t_of< automaton_t > word_t
void init_pair(bool keep_initials=false)
typename detail::transition_t_of_impl< base_t< ValueSet >>::type transition_t_of
Definition: traits.hh:57
std::pair< unsigned, transition_t_of< pair_automaton_t >> dist_transition_t
label make_label(const LabelSet &ls, const typename LabelSet::value_t &l)
Definition: label.hh:80
pair_automaton_t pair_
Corresponding pair automaton.
law_t< LabelSet > make_wordset(const LabelSet &ls)
The wordset of a labelset.
Definition: labelset.hh:269
int phi_1(state_t p) const
Heuristic used for SynchroP.
automaton_t aut_
Input automaton.
word_synchronizer(const automaton_t &aut)
word_t_of< Aut > synchronizing_word(const Aut &aut, const std::string &algo="greedy")
Return a synchronizing word for aut using algo algo.
state_t_of< automaton_t > state_t
Paths in filesystems, i.e., file names.
Definition: path.hh:21
bool is_synchronizing(const automaton &aut)
Bridge.
bool is_synchronized_by(const Aut &aut, const word_t_of< Aut > &w)
Whether w synchronizes automaton aut.
int delta(state_t p, const std::vector< transition_t > &w) const
Compute dist(d(s, w)) - dist(s).
bool is_synchronized_by(const automaton &aut, const label &word)
Bridge.
typename labelset_t_of< base_t< ValueSet >>::word_t word_t_of
Definition: traits.hh:82
pair_automaton< Aut > pair(const Aut &aut, bool keep_initials=false)
Definition: pair.hh:251
int phi_3(const label_t &l) const
Heuristic used for FastSynchro.
state_t dest_state(state_t s, const label_t &l) const
std::vector< transition_t > recompose_path(state_t from) const
std::pair< state_t, state_t > state_name_t
pair_automaton< automaton_t > pair_automaton_t
typename paths_t::value_type path_t
transition_t_of< automaton_t > transition_t
void require(Bool b, Args &&...args)
If b is not verified, raise an error with args as message.
Definition: raise.hh:78
int phi_2(state_t p) const
Heuristic used for SynchroPL.
std::unordered_map< state_t_of< pair_automaton_t >, dist_transition_t > paths_t
void init_synchro(bool keep_initials=false)
std::ostream & str_escape(std::ostream &os, const std::string &str, const char *special=nullptr)
Output a string, escaping special characters.
Definition: escape.cc:54
label_t_of< automaton_t > label_t
void apply_label(const label_t &label)
label synchronizing_word(const automaton &aut, const std::string &algo)
Bridge.
std::shared_ptr< const detail::label_base > label
Definition: fwd.hh:44
bool is_synchronizing(const Aut &aut)
Whether this automaton is synchronizing, i.e., has synchronizing words.
std::shared_ptr< detail::pair_automaton_impl< Aut >> pair_automaton
Definition: pair.hh:244
std::unordered_map< state_t_of< Aut >, std::pair< unsigned, transition_t_of< Aut > > > paths_ibfs(const Aut &aut, const std::vector< state_t_of< Aut >> &start)
Find the shortest paths from some states to all the states.
Definition: distance.hh:73
auto out(const Aut &aut, state_t_of< Aut > s)
Indexes of visible transitions leaving state s.
Definition: automaton.hh:56
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
Definition: traits.hh:56
size_t size(const ExpSet &rs, const typename ExpSet::value_t &r)
auto & as()
Extract wrapped typed automaton.
Definition: automaton.hh:39
word_t synchro(heuristic_t heuristic)
Definition: a-star.hh:8