Vcsn  2.4
Be Rational
are-isomorphic.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <algorithm>
4 #include <map>
5 #include <stack>
6 #include <unordered_map>
7 #include <unordered_set>
8 
9 #include <boost/range/algorithm/permutation.hpp>
10 #include <boost/range/algorithm/sort.hpp>
11 
12 #include <vcsn/algos/accessible.hh>
13 #include <vcsn/dyn/automaton.hh>
14 #include <vcsn/dyn/fwd.hh>
15 #include <vcsn/misc/functional.hh>
16 #include <vcsn/misc/map.hh>
17 #include <vcsn/misc/vector.hh>
18 
19 // What we refer to as "sequentiality" in this algorithm is an obvious
20 // generalization to any context of the notion of sequentiality
21 // defined only for lal, in its turn an obvious generalization of
22 // determinism to weighted automata.
23 
24 namespace vcsn
25 {
26 
27  /*-----------------.
28  | are_isomorphic. |
29  `-----------------*/
30 
31  template <Automaton Aut1, Automaton Aut2>
33  {
34  private:
35  using automaton1_t = Aut1;
43 
44  using automaton2_t = Aut2;
52 
53  // FIXME: do we want to generalize this to heterogeneous contexts?
54  // It is not completely clear whether such behavior is desirable.
55  //
56  // We don't check labelsets, because currently, by sheer luck,
57  // comparing lan vs. lal works.
58  static_assert(std::is_same<weightset1_t, weightset2_t>{},
59  "are_isomorphic: contexts must be equal");
60 
61  using weightset_t = weightset1_t; // FIXME: join!
62  using labelset_t = labelset1_t; // FIXME: join!
63 
64  using states_t = std::pair<state1_t, state2_t>;
65 
68 
70  template <Automaton Aut>
71  using dout_t =
74  std::unordered_map<label_t_of<Aut>,
75  std::pair<weight_t_of<Aut>, state_t_of<Aut>>,
78 
82 
84  template <Automaton Aut>
85  using nout_t =
87  <state_t_of<Aut>,
90  std::unordered_map<weight_t_of<Aut>,
91  std::vector<state_t_of<Aut>>,
94  vcsn::hash<labelset_t_of<Aut>>,
98 
102  using pair_t = std::pair<state1_t, state2_t>;
103  using worklist_t = std::stack<pair_t>;
105 
107  using s1tos2_t = std::unordered_map<state1_t, state2_t>;
108  using s2tos1_t = std::unordered_map<state2_t, state1_t>;
109 
117  {
118  enum class tag
119  {
120  never_computed = -1, // We didn't run the algorithm yet.
121  isomorphic = 0, // a1_ and a2_ are in fact isomorphic.
122  counterexample = 1, // We found a counterexample of two states
123  // [only possible for sequential automata].
124  nocounterexample = 2, // Exhaustive tests failed [we do this only
125  // for non-sequential automata].
126  trivially_different = 3, // Different number of states or transitions,
127  // of different sequentiality.
128  } response;
129 
132 
136 
138  : response(tag::never_computed)
139  {}
140  } fr_;
141 
142  // Return true and fill \a dout if \a a is sequential; otherwise
143  // return false and clear dout. We can't use the is_deterministic
144  // algorithm, as it's only defined for lal.
145  template <Automaton Aut>
146  bool is_sequential_filling(const Aut& a,
147  dout_t<Aut>& dout)
148  {
149  for (auto t : all_transitions(a))
150  {
151  const state_t_of<Aut>& src = a->src_of(t);
152  const label_t_of<Aut>& l = a->label_of(t);
153  auto& doutsrc = dout[src];
154  if (doutsrc.find(l) == doutsrc.end())
155  dout[src][l] = {a->weight_of(t), a->dst_of(t)};
156  else
157  {
158  dout.clear();
159  return false;
160  }
161  }
162  return true;
163  }
164 
165  void fill_nouts_()
166  {
167  for (auto t1 : all_transitions(a1_))
168  nout1_[a1_->src_of(t1)][a1_->label_of(t1)][a1_->weight_of(t1)]
169  .emplace_back(a1_->dst_of(t1));
170  for (auto t2 : all_transitions(a2_))
171  nout2_[a2_->src_of(t2)][a2_->label_of(t2)][a2_->weight_of(t2)]
172  .emplace_back(a2_->dst_of(t2));
173  }
174 
175  void clear()
176  {
177  dout1_.clear();
178  dout2_.clear();
179  nout1_.clear();
180  nout2_.clear();
181  }
182 
184  {
185  // Automata of different sizes are different.
186  if (a1_->num_states() != a2_->num_states())
187  return true;
188  if (a1_->num_transitions() != a2_->num_transitions())
189  return true;
190 
191  // The idea of comparing alphabet sizes here is tempting, but
192  // it's more useful to only deal with the actually used labels;
193  // we consider isomorphic even two automata from labelsets with
194  // different alphabets, when the actually used labels match.
195  // Building a set of actually used labels has linear complexity,
196  // and it's not obvious that performing an additional check now
197  // would pay in real usage. FIXME: benchmark in real cases.
198 
199  return false;
200  }
201 
202  public:
203  are_isomorphicer(const Aut1 &a1, const Aut2 &a2)
204  : a1_(a1)
205  , a2_(a2)
206  {}
207 
208  const full_response
210  {
211  clear();
212 
213  // If we prove non-isomorphism at this point, it will be because
214  // of sizes.
216 
217  require(is_accessible(a1_),
218  "are-isomorphic: lhs automaton must be accessible");
219  require(is_accessible(a2_),
220  "are-isomorphic: rhs automaton must be accessible");
221 
222  // Before even initializing our data structures, which is
223  // potentially expensive, try to simply compare the number of
224  // elements such as states and transitions.
225  if (trivially_different())
226  return fr_;
227 
228  if (is_sequential_filling(a1_, dout1_))
229  if (is_sequential_filling(a2_, dout2_))
231  else
232  return fr_; // Different sequentiality.
233  else
234  if (is_sequential_filling(a2_, dout2_))
235  return fr_; // Different sequentiality.
236  else
237  {
238  fill_nouts_();
240  }
241  }
242 
243  using states1_t = std::vector<state1_t>;
244  using states2_t = std::vector<state2_t>;
245 
250  using class_id = std::size_t;
251  using class_pair_t = std::pair<states1_t, states2_t>;
252  using state_classes_t = std::vector<class_pair_t>;
254 
255  template <Automaton Aut>
256  class_id state_to_class(state_t_of<Aut> s, Aut& a)
257  {
258  class_id res = 0;
259 
260  hash_combine(res, s == a->pre());
261  hash_combine(res, s == a->post());
262 
263  const auto& ws = *a->weightset();
264  const auto& ls = *a->labelset();
265 
266  using transition_t = std::pair<weight_t_of<Aut>,
267  label_t_of<Aut>>;
268  using transitions_t = std::vector<transition_t>;
269  const auto less =
270  [&](const transition_t& t1, const transition_t& t2)
271  {
272  if (ws.less(t1.first, t2.first))
273  return true;
274  else if (ws.less(t2.first, t1.first))
275  return false;
276  else
277  return ls.less(t1.second, t2.second);
278  };
279 
280 #define HASH_TRANSITIONS(expression, endpoint_getter) \
281  { \
282  std::unordered_set<state_t_of<Aut>> endpoint_states; \
283  transitions_t tt; \
284  for (auto& t: expression) \
285  { \
286  tt.emplace_back(transition_t{a->weight_of(t), a->label_of(t)}); \
287  endpoint_states.emplace(a->endpoint_getter(t)); \
288  } \
289  boost::sort(tt, less); \
290  for (const auto& t: tt) \
291  { \
292  hash_combine(res, ws.hash(t.first)); \
293  hash_combine(res, ls.hash(t.second)); \
294  } \
295  hash_combine(res, endpoint_states.size()); \
296  }
297 
298  // Hash input transitions data, in a way which doesn't depend on
299  // state numbers or transition order.
300  HASH_TRANSITIONS(all_in(a, s), src_of);
301 
302  // Do the same for output transitions.
303  HASH_TRANSITIONS(all_out(a, s), dst_of);
304 
305 #undef HASH_TRANSITIONS
306 
307  return res;
308  }
309 
311  {
312  // Class left and right states:
313  std::unordered_map<class_id, std::pair<states1_t, states2_t>> table;
314  for (auto s1: a1_->all_states())
315  table[state_to_class(s1, a1_)].first.emplace_back(s1);
316  for (auto s2: a2_->all_states())
317  table[state_to_class(s2, a2_)].second.emplace_back(s2);
318 
319  // Return a table without class hashes sorted by decreasing
320  // (left) size, in order to perform the most constrained choices
321  // first.
323  for (const auto& c: table)
324  res.emplace_back(std::move(c.second.first), std::move(c.second.second));
325  boost::sort(res,
326  [](const class_pair_t& c1, const class_pair_t& c2)
327  {
328  return c1.first.size() > c2.first.size();
329  });
330 
331  for (auto& c: res)
332  {
333  // This is mostly to make debugging easier.
334  boost::sort(c.first);
335 
336  // This call is needed for correctness: we have to start
337  // with all classes in their "smallest" configuration in
338  // lexicographic order.
339  boost::sort(c.second);
340  }
341 
342  //print_class_stats(res);
343  return res;
344  }
345 
348  std::ostream& o = std::cerr) const
349  {
350  size_t max = 0, min = a1_->num_all_states();
351  long double sum = 0.0;
352  for (const auto& c: cs)
353  {
354  max = std::max(max, c.first.size());
355  min = std::min(min, c.first.size());
356  sum += c.first.size();
357  }
358  long state_no = a1_->num_all_states();
359  o << "State no: " << state_no << '\n'
360  << "Class no: " << cs.size() << '\n'
361  << "* min class size: " << min << '\n'
362  << "* avg class size: " << sum / cs.size() << '\n'
363  << "* max class size: " << max << '\n';
364  }
365 
368  std::ostream& o = std::cerr)
369  {
370  for (const auto& c: cs)
371  {
372  o << "* ";
373  for (const auto& s1: c.first)
374  o << s1 << ' ';
375  o << "-- ";
376  for (const auto& s2: c.second)
377  o << s2 << ' ';
378  o << '\n';
379  }
380  }
381 
383  {
384  try
385  {
387  }
388  catch (const std::out_of_range&)
389  {
390  return false;
391  }
392  }
394  {
395  std::unordered_set<state1_t> mss1;
396  std::unordered_set<state2_t> mss2;
397  std::stack<pair_t> worklist;
398  worklist.push({a1_->pre(), a2_->pre()});
399  worklist.push({a1_->post(), a2_->post()});
400  while (! worklist.empty())
401  {
402  const auto p = std::move(worklist.top()); worklist.pop();
403  const state1_t s1 = p.first;
404  const state2_t s2 = p.second;
405 
406  // Even before checking for marks, check if these two states
407  // are supposed to be isomorphic with one another. We can't
408  // avoid this just because we've visited them before.
409  if (fr_.s1tos2_.at(s1) != s2 || fr_.s2tos1_.at(s2) != s1)
410  return false;
411  const bool m1 = (mss1.find(s1) != mss1.end());
412  const bool m2 = (mss2.find(s2) != mss2.end());
413  if (m1 != m2)
414  return false;
415  else if (m1 && m2)
416  continue;
417  // Otherwise we have that ! m1 && ! m2.
418  mss1.emplace(s1);
419  mss2.emplace(s2);
420 
421  // If only one of s1 and s2 is pre or post then this is not
422  // an isomorphism.
423  if ((s1 == a1_->pre()) != (s2 == a2_->pre())
424  || (s1 == a1_->post()) != (s2 == a2_->post()))
425  return false;
426 
427  int t1n = 0, t2n = 0;
428  for (auto t1: all_out(a1_, s1))
429  {
430  auto d1 = a1_->dst_of(t1);
431  const auto& w1 = a1_->weight_of(t1);
432  const auto& l1 = a1_->label_of(t1);
433  const auto& d2s = nout2_.at(s2).at(l1).at(w1);
434  auto d2 = fr_.s1tos2_.at(d1); // according to the isomorphism
435  if (!has(d2s, d2))
436  return false;
437  worklist.push({d1, d2});
438  ++ t1n;
439  }
440  for (auto t2: all_out(a2_, s2))
441  {
442  auto d2 = a2_->dst_of(t2);
443  const auto& w2 = a2_->weight_of(t2);
444  const auto& l2 = a2_->label_of(t2);
445  const auto& d1s = nout1_.at(s1).at(l2).at(w2);
446  auto d1 = fr_.s2tos1_.at(d2); // according to the isomorphism
447  if (!has(d1s, d1))
448  return false;
449  worklist.push({d1, d2});
450  ++ t2n;
451  }
452  if (t1n != t2n)
453  return false;
454  } // while
455  return true;
456  }
457 
459  {
460  for (const auto& c: state_classes_)
461  for (size_t i = 0; i < c.first.size(); ++ i)
462  {
463  state1_t s1 = c.first[i];
464  state2_t s2 = c.second[i];
465  fr_.s1tos2_[s1] = s2;
466  fr_.s2tos1_[s2] = s1;
467  }
468  }
469 
470  long factorial(long n)
471  {
472  long res = 1;
473  for (long i = 1; i <= n; ++ i)
474  res *= i;
475  return res;
476  }
477 
480  std::vector<long> class_permutation_max_;
481  std::vector<long> class_permutation_generated_;
482 
484  {
485  class_permutation_max_.clear();
486  class_permutation_generated_.clear();
487  for (const auto& c: state_classes_)
488  {
489  class_permutation_max_.emplace_back(factorial(c.second.size()) - 1);
490  class_permutation_generated_.emplace_back(0);
491  }
492  }
493 
494  // Build the next class combination obtained by permuting one
495  // class Like std::next_permutation, return true iff it was
496  // possible to rearrange into a "greater" configuration; if not,
497  // reset all classes to their first configuration.
499  {
500  // This algorithm is strongly reminiscent of natural number
501  // increment in a positional system, with carry propagation; in
502  // order to generate a configuration we permute the rightmost
503  // class; if this permutation resets it to its original value,
504  // we propagate the "carry" by continuing to permute the class
505  // on the left possibly propagating further left, and so on.
506 
507  const int rightmost = int(state_classes_.size()) - 1;
508 
509  // Permute the rightmost class.
510  if (boost::next_permutation(state_classes_[rightmost].second))
511  {
512  // Easy case: no carry.
513  ++ class_permutation_generated_[rightmost];
514  return true;
515  }
516 
517  // Permuting the rightmost class made it go back to its minimal
518  // configuration: propagate carry to the left.
519  //
520  // Carry propagation works by resetting all consecutive
521  // rightmost maximum-configuration class to their initial
522  // configuration, and permuting the leftmost one which was not
523  // maximum. If no such leftmost class exist then "the carry
524  // overflows", and we're done.
525  assert(class_permutation_generated_[rightmost]
526  == class_permutation_max_[rightmost]);
527  class_permutation_generated_[rightmost] = 0;
528  int i;
529  for (i = rightmost - 1;
530  i >= 0
531  && class_permutation_generated_[i] == class_permutation_max_[i];
532  -- i)
533  {
534  boost::next_permutation(state_classes_[i].second);
535  class_permutation_generated_[i] = 0;
536  }
537  if (i == -1)
538  return false; // Carry overflow.
539 
540  // Permute in order to propagate the carry to its final place.
541  boost::next_permutation(state_classes_[i].second);
542  ++ class_permutation_generated_[i];
543  return true;
544  }
545 
546  const full_response
548  {
549  // Initialize state classes, so that later we can only do
550  // brute-force search *within* each class.
551  state_classes_ = make_state_classes();
552 
553  // Don't even bother to search if the classes of left and right
554  // states have different sizes:
555  for (const auto& c: state_classes_)
556  if (c.first.size() != c.second.size())
557  {
559  return fr_;
560  }
561 
562  // Reorder the right-hand side in all possible ways allowed by
563  // classes, until we stumble on a solution.
565  do
566  {
568  if (is_isomorphism_valid())
569  {
571  return fr_;
572  }
573  }
574  while (next_class_combination());
575 
576  // We proved by exhaustion that no solution exists.
578  return fr_;
579  }
580 
581  const full_response
583  {
584  // If we prove non-isomorphism from now on, it will be by
585  // presenting some specific pair of states.
587 
588  worklist_.push({a1_->pre(), a2_->pre()});
589 
590  while (! worklist_.empty())
591  {
592  const states_t states = worklist_.top(); worklist_.pop();
593  const state1_t s1 = states.first;
594  const state2_t s2 = states.second;
595 
596  // If we prove non-isomorphism in this iteration, it will be
597  // by using the <s1, s2> pair as a counterexample.
598  fr_.counterexample = {s1, s2};
599 
600  // If the number of transitions going out from the two
601  // states is different, don't even bother looking at them.
602  // On the other hand if the number is equal we can afford to
603  // reason in just one direction: look at transitions from s1
604  // and ensure that all of them have a matching one from s2.
605  if (dout1_[s1].size() != dout2_[s2].size())
606  return fr_;
607 
608  for (const auto& l1_w1dst1 : dout1_[s1]) // dout1_.at(s1) may fail.
609  {
610  const label1_t& l1 = l1_w1dst1.first;
611  const weight1_t& w1 = l1_w1dst1.second.first;
612  const state1_t& dst1 = l1_w1dst1.second.second;
613 
614  const auto& s2out = dout2_.find(s2);
615  if (s2out == dout2_.cend())
616  return fr_;
617  const auto& s2outl = s2out->second.find(l1);
618  if (s2outl == s2out->second.cend())
619  return fr_;
620  weight2_t w2 = s2outl->second.first;
621  state2_t dst2 = s2outl->second.second;
622 
623  if (! weightset_t::equal(w1, w2))
624  return fr_;
625 
626  const auto& isomorphics_to_dst1 = fr_.s1tos2_.find(dst1);
627  const auto& isomorphics_to_dst2 = fr_.s2tos1_.find(dst2);
628 
629  if (isomorphics_to_dst1 == fr_.s1tos2_.cend())
630  {
631  if (isomorphics_to_dst2 == fr_.s2tos1_.cend()) // Both empty.
632  {
633  fr_.s1tos2_[dst1] = dst2;
634  fr_.s2tos1_[dst2] = dst1;
635  worklist_.push({dst1, dst2});
636  }
637  else
638  return fr_;
639  }
640  else if (isomorphics_to_dst1 == fr_.s1tos2_.cend()
641  || isomorphics_to_dst1->second != dst2
642  || isomorphics_to_dst2->second != dst1)
643  return fr_;
644  } // outer for
645  } // while
647  return fr_;
648  }
649 
650  bool operator()()
651  {
652  const full_response& r = get_full_response();
654  }
655 
659  using origins_t = std::map<state2_t, state1_t>;
660 
662  origins_t
664  {
666  __func__, ": isomorphism-check not successfully performed");
667  origins_t res;
668  for (const auto& s2s1: fr_.s2tos1_)
669  res[s2s1.first] = s2s1.second;
670  return res;
671  }
672 
674  static
675  std::ostream&
676  print(const origins_t& orig, std::ostream& o)
677  {
678  o << "/* Origins.\n"
679  << " node [shape = box, style = rounded]\n";
680  for (const auto& p : orig)
681  if (2 <= p.first)
682  {
683  o << " " << p.first - 2
684  << " [label = \"" << p.second << "\"]\n";
685  }
686  o << "*/\n";
687  return o;
688  }
689 
690  };
691 
692  template <Automaton Aut1, Automaton Aut2>
693  bool
694  are_isomorphic(const Aut1& a1, const Aut2& a2)
695  {
697 
698  return are_isomorphic();
699  }
700 
701  namespace dyn
702  {
703  namespace detail
704  {
705 
707  template <Automaton Aut1, Automaton Aut2>
708  bool
709  are_isomorphic(const automaton& aut1, const automaton& aut2)
710  {
711  const auto& a1 = aut1->as<Aut1>();
712  const auto& a2 = aut2->as<Aut2>();
713  return are_isomorphic(a1, a2);
714  }
715  }
716  }
717 }
std::vector< state1_t > states1_t
bool is_sequential_filling(const Aut &a, dout_t< Aut > &dout)
dout_t< automaton2_t > dout2_
std::vector< state2_t > states2_t
label_t_of< automaton1_t > label1_t
return res
Definition: multiply.hh:398
std::unordered_map< state_t_of< Aut >, std::unordered_map< label_t_of< Aut >, std::pair< weight_t_of< Aut >, state_t_of< Aut >>, vcsn::hash< labelset_t_of< Aut >>, vcsn::equal_to< labelset_t_of< Aut >>>> dout_t
See the comment for out_ in minimize.hh.
#define HASH_TRANSITIONS(expression, endpoint_getter)
std::size_t class_id
Automaton states partitioned into classes.
This is useful to make hashes with labels or weights as keys without using non-default constructors; ...
Definition: functional.hh:12
state_t_of< automaton1_t > state1_t
state_classes_t state_classes_
Functor to compare Values of ValueSets.
Definition: functional.hh:76
bool are_isomorphic(const automaton &aut1, const automaton &aut2)
Bridge.
bool is_accessible(const Aut &a)
Whether all its states are accessible.
Definition: accessible.hh:175
nout_t< automaton2_t > nout2_
This is useful to make hashes with labels or weights as keys without using non-default constructors; ...
Definition: functional.hh:57
std::vector< class_pair_t > state_classes_t
enum vcsn::are_isomorphicer::full_response::tag response
std::pair< state1_t, state2_t > states_t
void require(Bool b, Args &&...args)
If b is not verified, raise an error with args as message.
Definition: raise.hh:91
s1tos2_t s1tos2_
Only meaningful if the tag is tag::isomorphic.
weightset_t_of< automaton2_t > weightset2_t
Provide a variadic mul on top of a binary mul(), and one().
Definition: fwd.hh:46
std::unordered_map< state_t_of< Aut >, std::unordered_map< label_t_of< Aut >, std::unordered_map< weight_t_of< Aut >, std::vector< state_t_of< Aut >>, vcsn::hash< weightset_t_of< Aut >>, vcsn::equal_to< weightset_t_of< Aut >>>, vcsn::hash< labelset_t_of< Aut >>, vcsn::equal_to< labelset_t_of< Aut >>>> nout_t
For the nonsequential case.
typename detail::label_t_of_impl< base_t< ValueSet >>::type label_t_of
Definition: traits.hh:62
std::unordered_map< state1_t, state2_t > s1tos2_t
The maps associating the states of a1_ and the states of a2_->
const full_response get_full_response()
bool are_isomorphic(const Aut1 &a1, const Aut2 &a2)
std::unordered_map< state2_t, state1_t > s2tos1_t
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
Definition: traits.hh:63
are_isomorphicer(const Aut1 &a1, const Aut2 &a2)
label_t_of< automaton2_t > label2_t
void print_class_stats(const state_classes_t &cs, std::ostream &o=std::cerr) const
Handy debugging method.
origins_t origins()
Only meaningful if operator() returned true.
context_t_of< automaton1_t > context1_t
return exp min
Definition: multiply.hh:361
struct vcsn::are_isomorphicer::full_response fr_
Definition: a-star.hh:8
A datum specifying if two given automata are isomorphic, and why if they are not. ...
dout_t< automaton1_t > dout1_
For the simpler, faster sequential case.
labelset_t_of< context1_t > labelset1_t
size_t size(const ExpSet &rs, const typename ExpSet::value_t &r)
std::pair< state1_t, state2_t > pair_t
A worklist of pairs of states which are candidate to be isomorphic.
std::stack< pair_t > worklist_t
auto all_out(const Aut &aut, state_t_of< Aut > s)
Indexes of transitions leaving state s.
Definition: automaton.hh:66
void print_classes(const state_classes_t &cs, std::ostream &o=std::cerr)
Handy debugging method.
transition_t_of< automaton2_t > transition2_t
const state_classes_t make_state_classes()
context_t_of< automaton2_t > context2_t
labelset_t_of< context2_t > labelset2_t
pair_t counterexample
Only meaningful if the tag is tag::counterexample.
nout_t< automaton1_t > nout1_
typename detail::weight_t_of_impl< base_t< ValueSet >>::type weight_t_of
Definition: traits.hh:66
std::map< state2_t, state1_t > origins_t
A map from each a2_ state to the corresponding a1_ state.
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
Definition: traits.hh:64
A dyn automaton.
Definition: automaton.hh:17
weight_t_of< automaton1_t > weight1_t
void initialize_next_class_combination_state()
transition_t_of< automaton1_t > transition1_t
std::vector< std::pair< string_t, string_t >> transitions_t
Definition: parse.hh:72
std::vector< long > class_permutation_generated_
static std::ostream & print(const origins_t &orig, std::ostream &o)
Print origins.
class_id state_to_class(state_t_of< Aut > s, Aut &a)
weightset_t_of< automaton1_t > weightset1_t
const full_response get_full_response_sequential()
typename detail::transition_t_of_impl< base_t< ValueSet >>::type transition_t_of
Definition: traits.hh:65
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
Definition: traits.hh:67
weight_t_of< automaton2_t > weight2_t
std::pair< states1_t, states2_t > class_pair_t
ATTRIBUTE_PURE bool has(const boost::container::flat_set< Key, Compare, Allocator > &s, const Key &e)
Whether e is member of s.
Definition: setalpha.hh:25
const full_response get_full_response_nonsequential()
auto sort(const Aut &a) -> permutation_automaton< Aut >
Definition: sort.hh:161
auto all_in(const Aut &aut, state_t_of< Aut > s)
Indexes of transitions entering state s.
Definition: automaton.hh:115
void hash_combine(std::size_t &seed, const T &v)
Definition: functional.hh:48
auto & as()
Extract wrapped typed automaton.
Definition: automaton.hh:37
typename detail::context_t_of_impl< base_t< ValueSet >>::type context_t_of
Definition: traits.hh:61
Request the unordered_map implementation.
state_t_of< automaton2_t > state2_t
auto all_transitions(const Aut &aut)
All the transition indexes between all states (including pre and post).
Definition: automaton.hh:213
std::vector< long > class_permutation_max_
We need to keep some (small) state between a next_class_combination call and the next.