Vcsn  2.4
Be Rational
mutable-automaton.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <algorithm>
4 #include <cassert>
5 #include <vector>
6 
7 #include <boost/range/algorithm/find.hpp>
8 #include <boost/range/algorithm/find_if.hpp>
9 #include <boost/range/irange.hpp>
10 
12 #include <vcsn/core/fwd.hh>
13 #include <vcsn/core/transition.hh>
14 #include <vcsn/ctx/context.hh>
15 #include <vcsn/ctx/traits.hh>
16 #include <vcsn/misc/crange.hh>
17 #include <vcsn/misc/format.hh>
18 #include <vcsn/misc/index.hh>
19 #include <vcsn/misc/memory.hh>
20 #include <vcsn/misc/symbol.hh>
21 
22 namespace vcsn
23 {
24  namespace detail
25  {
27  template <typename Context>
28  class mutable_automaton_impl
29  {
30  public:
31  using context_t = Context;
35  template <typename Ctx = Context>
39  using kind_t = typename context_t::kind_t;
40 
41  using labelset_ptr = typename context_t::labelset_ptr;
42  using weightset_ptr = typename context_t::weightset_ptr;
43 
45  struct state_tag {};
48  struct transition_tag {};
51  using label_t = typename labelset_t::value_t;
53  using weight_t = typename weightset_t::value_t;
54 
55  protected:
58 
61 
63  using tr_store_t = std::vector<stored_transition_t>;
65  using tr_cont_t = std::vector<transition_t>;
66 
69  {
74  };
75 
77  using st_store_t = std::vector<stored_state_t>;
78 
80  using free_store_t = std::vector<unsigned>;
81 
90 
91  public:
92  mutable_automaton_impl() = delete;
95  : ctx_{ctx}
96  , states_{2}
97  , prepost_label_(ctx.labelset()->special())
98  {}
99 
101  : ctx_(that.ctx_)
102  , prepost_label_(that.prepost_label_)
103  {
104  *this = std::move(that);
105  }
106 
108  {
109  if (this != &that)
110  {
111  ctx_ = std::move(that.ctx_);
112  prepost_label_ = std::move(that.prepost_label_);
113  std::swap(states_, that.states_);
114  std::swap(states_fs_, that.states_fs_);
115  std::swap(transitions_, that.transitions_);
116  std::swap(transitions_fs_, that.transitions_fs_);
117  }
118  return *this;
119  }
120 
121 
122  /*----------------.
123  | Related sets. |
124  `----------------*/
125 
126  static symbol sname()
127  {
128  static auto res
129  = symbol{"mutable_automaton<" + context_t::sname() + '>'};
130  return res;
131  }
132 
133  std::ostream& print_set(std::ostream& o = std::cout, format fmt = {}) const
134  {
135  o << "mutable_automaton<";
136  context().print_set(o, fmt);
137  return o << '>';
138  }
139 
140  const context_t& context() const { return ctx_; }
141  const weightset_ptr& weightset() const { return ctx_.weightset(); }
142  const labelset_ptr& labelset() const { return ctx_.labelset(); }
143 
144 
145  /*----------------------------------.
146  | Special states and transitions. |
147  `----------------------------------*/
148 
149  // pseudo-initial and final states.
150  // The code below assumes that pre() and post() are the first
151  // two states of the automaton. In other words, all other states
152  // have greater numbers. We also assume that pre()<post().
153  static constexpr state_t pre() { return 0U; }
154  static constexpr state_t post() { return 1U; }
156  static constexpr state_t null_state() { return -1U; }
158  static constexpr transition_t null_transition() { return -1U; }
161  static constexpr transition_t lazy_transition() { return -2U; }
162 
164  label_t prepost_label() const
165  {
166  return prepost_label_;
167  }
168 
169 
170  /*--------------.
171  | Statistics. |
172  `--------------*/
173 
174  size_t num_all_states() const { return states_.size() - states_fs_.size(); }
175  size_t num_states() const { return num_all_states() - 2; }
176  size_t num_initials() const { return states_[pre()].succ.size(); }
177  size_t num_finals() const { return states_[post()].pred.size(); }
178  size_t num_transitions() const
179  {
180  return (transitions_.size()
181  - transitions_fs_.size() - num_initials() - num_finals());
182  }
183 
184 
185  /*---------------------.
186  | Queries on states. |
187  `---------------------*/
188 
190  bool
191  has_state(state_t s) const
192  {
193  // Any number outside our container is not a state.
194  // (This includes "null_state()".)
195  if (states_.size() <= s)
196  return false;
197  else
198  {
199  const stored_state_t& ss = states_[s];
200  // Erased states have 'invalid' as their first successor.
201  return ss.succ.empty() || ss.succ.front() != null_transition();
202  }
203  }
204 
207  bool
208  is_lazy(state_t s) const
209  {
210  auto ts = all_out(s);
211  return !ts.empty() && ts.front() == lazy_transition();
212  }
213 
216  bool
217  is_lazy_in(state_t s) const
218  {
219  auto ts = all_in(s);
220  return !ts.empty() && ts.front() == lazy_transition();
221  }
222 
224  bool
225  is_initial(state_t s) const
226  {
227  return has_transition(pre(), s, prepost_label_);
228  }
229 
231  bool
232  is_final(state_t s) const
233  {
234  return has_transition(s, post(), prepost_label_);
235  }
236 
238  ATTRIBUTE_PURE
239  weight_t
240  get_initial_weight(state_t s) const
241  {
242  transition_t t = get_transition(pre(), s, prepost_label_);
243  if (t == null_transition())
244  return weightset()->zero();
245  else
246  return weight_of(t);
247  }
248 
250  ATTRIBUTE_PURE
251  weight_t
252  get_final_weight(state_t s) const
253  {
254  transition_t t = get_transition(s, post(), prepost_label_);
255  if (t == null_transition())
256  return weightset()->zero();
257  else
258  return weight_of(t);
259  }
260 
261 
262  /*--------------------------.
263  | Queries on transitions. |
264  `--------------------------*/
265 
266  transition_t
267  get_transition(state_t src, state_t dst, label_t l) const
268  {
269  assert(has_state(src));
270  assert(!is_lazy(src));
271  assert(has_state(dst));
272  assert(!is_lazy_in(dst));
273  const tr_cont_t& succ = states_[src].succ;
274  const tr_cont_t& pred = states_[dst].pred;
275  const auto& ls = *this->labelset();
276  if (succ.size() <= pred.size())
277  {
278  auto i =
279  boost::find_if(succ,
280  [this,l,ls,dst] (transition_t t)
281  {
282  return (dst_of(t) == dst
283  && ls.equal(label_of(t), l));
284  });
285  if (i != end(succ))
286  return *i;
287  }
288  else
289  {
290  auto i =
291  boost::find_if(pred,
292  [this,l,ls,src] (transition_t t)
293  {
294  return (src_of(t) == src
295  && ls.equal(label_of(t), l));
296  });
297  if (i != end(pred))
298  return *i;
299  }
300  return null_transition();
301  }
302 
303  bool
304  has_transition(state_t src, state_t dst, label_t l) const
305  {
306  return get_transition(src, dst, l) != null_transition();
307  }
308 
309  bool
310  has_transition(transition_t t) const
311  {
312  // Any number outside our container is not a transition.
313  // (This includes "null_transition()".)
314  if (t >= transitions_.size())
315  return false;
316 
317  // Erased transition have invalid source state.
318  return transitions_[t].src != null_state();
319  }
320 
321  state_t src_of(transition_t t) const { return transitions_[t].src; }
322  state_t dst_of(transition_t t) const { return transitions_[t].dst; }
323  label_t label_of(transition_t t) const
324  {
325  return transitions_[t].get_label();
326  }
327 
328  weight_t weight_of(transition_t t) const
329  {
330  return transitions_[t].get_weight();
331  }
332 
333 
334  /*---------------------.
335  | Edition of states. |
336  `---------------------*/
337 
338  protected:
340  void
341  del_transition_from_src(transition_t t)
342  {
343  stored_transition_t& st = transitions_[t];
344  auto& succ = states_[st.src].succ;
345  auto tsucc = boost::range::find(succ, t);
346  assert(tsucc != succ.end());
347  *tsucc = std::move(succ.back());
348  succ.pop_back();
349  }
350 
352  void
353  del_transition_from_dst(transition_t t)
354  {
355  stored_transition_t& st = transitions_[t];
356  auto& pred = states_[st.dst].pred;
357  auto tpred = boost::range::find(pred, t);
358  assert(tpred != pred.end());
359  *tpred = std::move(pred.back());
360  pred.pop_back();
361  }
362 
363  void
364  del_transition_container(tr_cont_t& tc, bool from_succ)
365  {
366  for (auto t: tc)
367  {
368  if (from_succ)
369  del_transition_from_dst(t);
370  else
371  del_transition_from_src(t);
372  transitions_[t].src = null_state();
373  }
374  transitions_fs_.insert(transitions_fs_.end(), tc.begin(), tc.end());
375  tc.clear();
376  }
377 
378  public:
380  state_t
381  new_state()
382  {
383  state_t res;
384  if (states_fs_.empty())
385  {
386  res = states_.size();
387  states_.emplace_back();
388  }
389  else
390  {
391  res = states_fs_.back();
392  states_fs_.pop_back();
393  stored_state_t& ss = states_[res];
394  // De-invalidate this state: remove the invalid transition.
395  ss.succ.clear();
396  }
397  return res;
398  }
399 
400  std::ostream&
401  print_state(state_t s, std::ostream& o = std::cout) const
402  {
403  if (s == pre())
404  o << "pre";
405  else if (s == post())
406  o << "post";
407  else
408  o << s - 2;
409  return o;
410  }
411 
412  std::ostream&
413  print_state_name(state_t s, std::ostream& o = std::cout,
414  format = {},
415  bool = false) const
416  {
417  return print_state(s, o);
418  }
419 
420  static constexpr bool
421  state_has_name(state_t)
422  {
423  return false;
424  }
425 
426  void
427  del_state(state_t s)
428  {
429  assert(has_state(s));
430  assert(s > post()); // Cannot erase pre() and post().
431  stored_state_t& ss = states_[s];
432  del_transition_container(ss.pred, false);
433  del_transition_container(ss.succ, true);
434  ss.succ.emplace_back(null_transition()); // So has_state() can work.
435  states_fs_.emplace_back(s);
436  }
437 
438  void
439  set_initial(state_t s, weight_t w)
440  {
441  set_transition(pre(), s, prepost_label_, w);
442  }
443 
444  void
445  set_initial(state_t s)
446  {
447  set_initial(s, weightset()->one());
448  }
449 
450  void
451  set_lazy(state_t s, bool lazy = true)
452  {
453  assert(has_state(s));
454  stored_state_t& ss = states_[s];
455  assert(ss.succ.empty()
456  || ss.succ.front() == lazy_transition());
457  ss.succ.clear();
458  if (lazy)
459  ss.succ.emplace_back(lazy_transition());
460  }
461 
462  void
463  set_lazy_in(state_t s, bool lazy = true)
464  {
465  assert(has_state(s));
466  stored_state_t& ss = states_[s];
467  assert(ss.pred.empty()
468  || ss.pred.front() == lazy_transition());
469  ss.pred.clear();
470  if (lazy)
471  ss.pred.emplace_back(lazy_transition());
472  }
473 
474  transition_t
475  add_initial(state_t s, weight_t w)
476  {
477  return add_transition(pre(), s, prepost_label_, w);
478  }
479 
480  void
481  unset_initial(state_t s)
482  {
483  set_initial(s, weightset()->zero());
484  }
485 
486  void
487  set_final(state_t s, weight_t w)
488  {
489  set_transition(s, post(), prepost_label_, w);
490  }
491 
492  void
493  set_final(state_t s)
494  {
495  set_final(s, weightset()->one());
496  }
497 
498  transition_t
499  add_final(state_t s, weight_t w)
500  {
501  return add_transition(s, post(), prepost_label_, w);
502  }
503 
504  void
505  unset_final(state_t s)
506  {
507  set_final(s, weightset()->zero());
508  }
509 
510 
511  /*--------------------------.
512  | Edition of transitions. |
513  `--------------------------*/
514 
515  void
516  del_transition(transition_t t)
517  {
518  assert(has_transition(t));
519  // Remove transition from source and destination.
520  del_transition_from_src(t);
521  del_transition_from_dst(t);
522  // Actually erase the transition.
523  transitions_[t].src = null_state();
524  transitions_fs_.emplace_back(t);
525  }
526 
528  void
529  del_transition(state_t src, state_t dst, label_t l)
530  {
531  transition_t t = get_transition(src, dst, l);
532  if (t != null_transition())
533  del_transition(t);
534  }
535 
546  transition_t
547  new_transition(state_t src, state_t dst, label_t l, weight_t w)
548  {
549  assert(!has_transition(src, dst, l));
550  if (weightset()->is_zero(w))
551  return null_transition();
552  else
553  {
554  // FIXME: When src == pre() || dst == post(), label must be empty.
555  transition_t t;
556  if (transitions_fs_.empty())
557  {
558  t = transitions_.size();
559  transitions_.emplace_back(src, dst, l, w);
560  }
561  else
562  {
563  t = transitions_fs_.back();
564  transitions_fs_.pop_back();
565  stored_transition_t& st = transitions_[t];
566  st.src = src;
567  st.dst = dst;
568  st.set_label(l);
569  st.set_weight(w);
570  }
571  states_[src].succ.emplace_back(t);
572  states_[dst].pred.emplace_back(t);
573  return t;
574  }
575  }
576 
589  template <Automaton A>
590  transition_t
591  new_transition_copy(state_t src, state_t dst,
592  const A& aut, transition_t_of<A> t,
593  bool transpose = false)
594  {
595  auto l = aut->label_of(t);
596  auto w = aut->weight_of(t);
597  if (transpose)
598  {
599  l = aut->labelset()->transpose(l);
600  w = aut->weightset()->transpose(w);
601  }
602  return new_transition(src, dst,
603  labelset()->conv(*aut->labelset(), l),
604  weightset()->conv(*aut->weightset(), w));
605  }
606 
608  transition_t
609  new_transition(state_t src, state_t dst, label_t l)
610  {
611  return new_transition(src, dst, l, weightset()->one());
612  }
613 
624  transition_t
625  set_transition(state_t src, state_t dst, label_t l, weight_t w)
626  {
627  // It's illegal to connect pre() to post().
628  // FIXME: reenable except for labels_are_one.
629  // assert(src != pre() || dst != post());
630  // It's illegal to leave post().
631  assert(src != post());
632  // It's illegal to go to pre().
633  assert(dst != pre());
634 
635  transition_t t = get_transition(src, dst, l);
636  if (t == null_transition())
637  t = new_transition(src, dst, l, w);
638  else if (weightset()->is_zero(w))
639  {
640  del_transition(t);
641  t = null_transition();
642  }
643  else
644  {
645  stored_transition_t& st = transitions_[t];
646  st.set_label(l);
647  st.set_weight(w);
648  }
649  return t;
650  }
651 
655  {
656  return set_transition(src, dst, l, weightset()->one());
657  }
658 
671  {
672  transition_t t = get_transition(src, dst, l);
673  if (t == null_transition())
674  t = new_transition(src, dst, l, w);
675  else
676  {
677  w = weightset()->add(weight_of(t), w);
678  t = set_weight(t, w);
679  }
680  return t;
681  }
682 
686  {
687  return add_transition(src, dst, l, weightset()->one());
688  }
689 
698  template <Automaton A>
701  const A& aut, transition_t_of<A> t,
702  bool transpose = false)
703  {
704  auto l = aut->label_of(t);
705  auto w = aut->weight_of(t);
706  if (transpose)
707  {
708  l = aut->labelset()->transpose(l);
709  w = aut->weightset()->transpose(w);
710  }
711  return add_transition(src, dst,
712  labelset()->conv(*aut->labelset(), l),
713  weightset()->conv(*aut->weightset(), w));
714  }
715 
717  std::ostream& print(transition_t t, std::ostream& o = std::cout,
718  format fmt = {}) const
719  {
720  if (t == null_transition())
721  o << "null_transition";
722  else if (t == lazy_transition())
723  o << "lazy_transition";
724  else
725  {
726  o << t << ": ";
727  print_state_name(src_of(t), o) << " -- <";
728  weightset()->print(weight_of(t), o, fmt.for_weights()) << '>';
729  labelset()->print(label_of(t), o, fmt.for_labels()) << " --> ";
730  print_state_name(dst_of(t), o);
731  }
732  return o;
733  }
734 
736  std::ostream& print(std::ostream& o = std::cout) const
737  {
738  for (auto s: all_states())
739  {
740  o << "State: ";
741  print_state_name(s, o) << '\n';
742  o << " Incoming:\n";
743  for (auto t: all_in(s))
744  {
745  o << " ";
746  print(t, o) << '\n';
747  }
748  o << " Outgoing:\n";
749  for (auto t: all_out(s))
750  {
751  o << " ";
752  print(t, o) << '\n';
753  }
754  }
755  return o;
756  }
757 
760  {
761  if (weightset()->is_zero(w))
762  {
763  del_transition(t);
764  return null_transition();
765  }
766  else
767  transitions_[t].set_weight(w);
768  return t;
769  }
770 
771  weight_t
773  {
774  return weight_of(set_weight(t, weightset()->add(weight_of(t), w)));
775  }
776 
777  weight_t
779  {
780  return weight_of(set_weight(t, weightset()->mul(w, weight_of(t))));
781  }
782 
783  weight_t
785  {
786  return weight_of(set_weight(t, weightset()->mul(weight_of(t), w)));
787  }
788 
789 
790  /*---------------------------------------.
791  | Iteration on states and transitions. |
792  `---------------------------------------*/
793 
794  protected:
797  template <typename Pred>
798  auto state_range(state_t b, state_t e, Pred pred) const
799  {
801  (boost::irange<state_t>(b, e),
802  [this, pred]
803  (state_t s)
804  {
805  const stored_state_t& ss = states_[s];
806  return ((ss.succ.empty()
807  || ss.succ.front() != null_transition())
808  && pred(s));
809  });
810  }
811 
813  auto state_range(state_t b, state_t e) const
814  {
815  return state_range(b, e, [](state_t) { return true; });
816  }
817 
818  public:
821  auto all_states() const
822  {
823  return state_range(0U, states_.size());
824  }
825 
828  template <typename Pred>
829  auto all_states(Pred pred) const
830  {
831  return state_range(0U, states_.size(), pred);
832  }
833 
836  auto states() const
837  {
838  return state_range(post() + 1, states_.size());
839  }
840 
842  auto all_transitions() const
843  {
845  (boost::irange<transition_t>(0U, transitions_.size()),
846  [this](transition_t t)
847  {
848  return src_of(t) != null_state();
849  });
850  }
851 
855  all_out(state_t s) const
856  {
857  assert(has_state(s));
858  return states_[s].succ;
859  }
860 
864  all_in(state_t s) const
865  {
866  assert(has_state(s));
867  return states_[s].pred;
868  }
869  };
870  }
871 
872  template <typename Context>
873  mutable_automaton<Context>
874  make_mutable_automaton(const Context& ctx)
875  {
876  return make_shared_ptr<mutable_automaton<Context>>(ctx);
877  }
878 
879  template <typename Context>
880  auto
881  make_nullable_automaton(const Context& ctx)
882  {
884  }
885 }
const context_t & context() const
auto make_nullable_automaton(const Context &ctx)
index_t_impl< transition_tag > transition_t
transition_t set_weight(transition_t t, weight_t w)
transition_t add_transition_copy(state_t src, state_t dst, const A &aut, transition_t_of< A > t, bool transpose=false)
Add a transition between two states, copying the label from the given transition. ...
mutable_automaton_impl(const context_t &ctx)
container_filter_range< Cont, Pred > make_container_filter_range(const Cont &cont, Pred pred)
Definition: crange.hh:114
bool has_state(state_t s) const
Whether state s belongs to the automaton.
Bidirectional automata.
Definition: fwd.hh:21
std::ostream & print(transition_t t, std::ostream &o=std::cout, format fmt={}) const
Print a transition, for debugging.
state_t src_of(transition_t t) const
label_t label_of(transition_t t) const
return res
Definition: multiply.hh:398
typename weightset_t::value_t weight_t
Transition weight.
labelset_t_of< context_t > labelset_t
typename context_t::kind_t kind_t
static constexpr state_t null_state()
Invalid state.
container_range< const tr_cont_t & > all_in(state_t s) const
Indexes of all transitions arriving to state s.
typename context_t::labelset_ptr labelset_ptr
std::shared_ptr< detail::mutable_automaton_impl< Context >> mutable_automaton
Definition: fwd.hh:25
weight_t rweight(transition_t t, weight_t w)
weight_t lweight(transition_t t, weight_t w)
Lightweight state/transition handle (or index).
Definition: index.hh:12
auto all_states() const
All states including pre()/post().
mutable_automaton< Context > make_mutable_automaton(const Context &ctx)
An input/output format for valuesets.
Definition: format.hh:13
if(exp.max==-1)
Definition: multiply.hh:381
Provide a variadic mul on top of a binary mul(), and one().
Definition: fwd.hh:46
Restrict the interface of a container to begin/end.
Definition: fwd.hh:11
transition_t new_transition(state_t src, state_t dst, label_t l, weight_t w)
Create a transition between two states.
const labelset_ptr & labelset() const
container_range< const tr_cont_t & > all_out(state_t s) const
Indexes of all transitions leaving state s.
boost::flyweight< std::string, boost::flyweights::no_tracking, boost::flyweights::intermodule_holder > symbol
An internalized string.
Definition: symbol.hh:23
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
Definition: traits.hh:63
Transition with label and non Boolean weight.
Definition: transition.hh:57
static constexpr transition_t lazy_transition()
Invalid transition that shows that the state's outgoing transitions are unknown.
auto all_states(Pred pred) const
All states including pre()/post() that validate pred.
mutable_automaton< Ctx > fresh_automaton_t
The (shared pointer) type to use if we have to create an automaton of the same (underlying) type...
free_store_t states_fs_
Free indexes in states_.
typename labelset_t::value_t label_t
Transition label.
Definition: a-star.hh:8
std::vector< stored_transition_t > tr_store_t
All the automaton's transitions.
std::vector< unsigned > free_store_t
A list of unused indexes in the states/transitions tables.
typename context_t::weightset_ptr weightset_ptr
weight_t weight_of(transition_t t) const
const weightset_ptr & weightset() const
free_store_t transitions_fs_
Free indexes in transitions_.
context_t ctx_
The algebraic type of this automaton.
auto states() const
All states excluding pre()/post().
transition_t set_transition(state_t src, state_t dst, label_t l)
Same as above, with unit weight.
std::ostream & print(std::ostream &o=std::cout) const
Print an automaton, for debugging.
std::vector< transition_t > tr_cont_t
All the incoming/outgoing transition handles of a state.
transition_t add_transition(state_t src, state_t dst, label_t l, weight_t w)
Add a transition between two states.
transition_t set_transition(state_t src, state_t dst, label_t l, weight_t w)
Set a transition between two states.
auto all_transitions() const
All the transition indexes between all states (including pre and post).
transition_t add_transition(state_t src, state_t dst, label_t l)
Same as above, with weight one.
weight_t add_weight(transition_t t, weight_t w)
typename detail::transition_t_of_impl< base_t< ValueSet >>::type transition_t_of
Definition: traits.hh:65
symbol sname()
Definition: name.hh:65
Lightweight transition handle (or index).
Lightweight state handle (or index).
std::ostream & print_state_name(state_t s, std::ostream &o=std::cout, format={}, bool=false) const
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
Definition: traits.hh:67
An exponent, or range of exponents.
Definition: to.hh:25
auto conv(const ValueSet &vs, const std::string &str, Args &&...args) -> decltype(vs.conv(std::declval< std::istream & >(), std::forward< Args >(args)...))
Parse str via vs.conv.
Definition: stream.hh:29
state_t dst_of(transition_t t) const
mutable_automaton_impl & operator=(mutable_automaton_impl &&that)
weightset_t_of< context_t > weightset_t
auto state_range(state_t b, state_t e, Pred pred) const
The range of index numbers in [b .
nullableset_context_t< context< LabelSet, WeightSet > > make_nullableset_context(const context< LabelSet, WeightSet > &ctx)
The nullableset context of a context.
Definition: labelset.hh:165
std::vector< stored_state_t > st_store_t
All the automaton's states.
label_t prepost_label_
Label for initial and final transitions.
transition_tuple< state_t, label_t, weight_t > stored_transition_t
Data stored per transition.
mutable_automaton_impl(mutable_automaton_impl &&that)
transition_t get_transition(state_t src, state_t dst, label_t l) const
std::ostream & print_set(std::ostream &o=std::cout, format fmt={}) const
static constexpr transition_t null_transition()
Invalid transition.
auto state_range(state_t b, state_t e) const
The range of state numbers in [b .. e].
Aut transpose(const transpose_automaton< Aut > &aut)
The transpose of a transpose automaton is the original automaton.
Definition: transpose.hh:253