6 #include <unordered_map>
7 #include <unordered_set>
9 #include <boost/range/algorithm/permutation.hpp>
10 #include <boost/range/algorithm/sort.hpp>
31 template <
typename Aut1,
typename Aut2>
58 using states_t = std::pair<state1_t, state2_t>;
64 template<
typename Automaton>
68 std::unordered_map<label_t_of<Automaton>,
69 std::pair<weight_t_of<Automaton>,
70 state_t_of<Automaton>>,
79 template<
typename Automaton>
82 <state_t_of<Automaton>,
85 std::unordered_map<weight_t_of<Automaton>,
86 std::vector<state_t_of<Automaton>>,
89 vcsn::hash<labelset_t_of<Automaton>>,
97 using pair_t = std::pair<state1_t, state2_t>;
102 using s1tos2_t = std::unordered_map<state1_t, state2_t>;
103 using s2tos1_t = std::unordered_map<state2_t, state1_t>;
140 template <
typename Automaton>
144 for (
auto t : a->all_transitions())
146 const state_t_of<Automaton>& src = a->src_of(t);
147 const label_t_of<Automaton>& l = a->label_of(t);
148 auto& doutsrc = dout[src];
149 if (doutsrc.find(l) == doutsrc.end())
150 dout[src][l] = {a->weight_of(t), a->dst_of(t)};
162 for (
auto t1 : a1_->all_transitions())
163 nout1_[a1_->src_of(t1)][a1_->label_of(t1)][a1_->weight_of(t1)]
164 .emplace_back(a1_->dst_of(t1));
165 for (
auto t2 : a2_->all_transitions())
166 nout2_[a2_->src_of(t2)][a2_->label_of(t2)][a2_->weight_of(t2)]
167 .emplace_back(a2_->dst_of(t2));
181 if (a1_->num_states() != a2_->num_states())
183 if (a1_->num_transitions() != a2_->num_transitions())
213 "are-isomorphic: lhs automaton must be accessible");
215 "are-isomorphic: rhs automaton must be accessible");
250 template<
typename Automaton>
258 const auto ws = * a->weightset();
259 const auto ls = * a->labelset();
261 using transition_t = std::pair<weight_t_of<Automaton>,
262 label_t_of<Automaton>>;
265 [&](
const transition_t& t1,
const transition_t& t2)
267 if (ws.less(t1.first, t2.first))
269 else if (ws.less(t2.first, t1.first))
272 return ls.less(t1.second, t2.second);
275 #define HASH_TRANSITIONS(expression, endpoint_getter) \
277 std::unordered_set<state_t_of<Automaton>> endpoint_states; \
279 for (auto& t: expression) \
281 tt.emplace_back(transition_t{a->weight_of(t), a->label_of(t)}); \
282 endpoint_states.emplace(a->endpoint_getter(t)); \
284 boost::sort(tt, less); \
285 for (const auto& t: tt) \
287 hash_combine(res, ws.hash(t.first)); \
288 hash_combine(res, ls.hash(t.second)); \
290 hash_combine(res, endpoint_states.size()); \
300 #undef HASH_TRANSITIONS
308 std::unordered_map<class_id, std::pair<states1_t, states2_t>> table;
309 for (
auto s1: a1_->all_states())
311 for (
auto s2: a2_->all_states())
318 for (
const auto& c: table)
319 res.emplace_back(std::move(c.second.first), std::move(c.second.second));
323 return c1.first.size() > c2.first.size();
344 size_t max = 0, min = a1_->num_all_states();
345 long double sum = 0.0;
346 for (
const auto& c: cs)
348 max = std::max(max, c.first.size());
349 min = std::min(min, c.first.size());
350 sum += c.first.size();
352 long state_no = a1_->num_all_states();
353 std::cerr <<
"State no: " << state_no <<
"\n";
354 std::cerr <<
"Class no: " << cs.size() <<
"\n";
355 std::cerr <<
"* min class size: " << min <<
"\n";
356 std::cerr <<
"* avg class size: " << sum / cs.size() <<
"\n";
357 std::cerr <<
"* max class size: " << max <<
"\n";
363 for (
const auto& c: cs)
366 for (
const auto& s1: c.first)
367 std::cerr << s1 <<
" ";
369 for (
const auto& s2: c.second)
370 std::cerr << s2 <<
" ";
381 catch (
const std::out_of_range&)
388 std::unordered_set<state1_t> mss1;
389 std::unordered_set<state2_t> mss2;
390 std::stack<pair_t> worklist;
391 worklist.push({a1_->pre(), a2_->pre()});
392 worklist.push({a1_->post(), a2_->post()});
393 while (! worklist.empty())
395 const auto p = std::move(worklist.top()); worklist.pop();
404 const bool m1 = (mss1.find(s1) != mss1.end());
405 const bool m2 = (mss2.find(s2) != mss2.end());
416 if ((s1 == a1_->pre()) != (s2 == a2_->pre())
417 || (s1 == a1_->post()) != (s2 == a2_->post()))
420 int t1n = 0, t2n = 0;
421 for (
auto t1: a1_->all_out(s1))
423 auto d1 = a1_->dst_of(t1);
424 const auto& w1 = a1_->weight_of(t1);
425 const auto& l1 = a1_->label_of(t1);
426 const auto& d2s = nout2_.at(s2).at(l1).at(w1);
430 worklist.push({d1, d2});
433 for (
auto t2: a2_->all_out(s2))
435 auto d2 = a2_->dst_of(t2);
436 const auto& w2 = a2_->weight_of(t2);
437 const auto& l2 = a2_->label_of(t2);
438 const auto& d1s = nout1_.at(s1).at(l2).at(w2);
442 worklist.push({d1, d2});
453 for (
const auto& c: state_classes_)
454 for (
int i = 0; i < int(c.first.size()); ++ i)
466 for (
long i = 1; i <= n; ++ i)
478 class_permutation_max_.clear();
479 class_permutation_generated_.clear();
480 for (
const auto& c: state_classes_) {
481 class_permutation_max_.emplace_back(
factorial(c.second.size()) - 1);
482 class_permutation_generated_.emplace_back(0);
499 const int rightmost = int(state_classes_.size()) - 1;
502 if (boost::next_permutation(state_classes_[rightmost].second))
505 ++ class_permutation_generated_[rightmost];
517 assert(class_permutation_generated_[rightmost]
518 == class_permutation_max_[rightmost]);
519 class_permutation_generated_[rightmost] = 0;
521 for (i = rightmost - 1;
523 && class_permutation_generated_[i] == class_permutation_max_[i];
526 boost::next_permutation(state_classes_[i].second);
527 class_permutation_generated_[i] = 0;
533 boost::next_permutation(state_classes_[i].second);
534 ++ class_permutation_generated_[i];
547 for (
const auto& c: state_classes_)
548 if (c.first.size() != c.second.size())
580 worklist_.push({a1_->pre(), a2_->pre()});
582 while (! worklist_.empty())
584 const states_t states = worklist_.top(); worklist_.pop();
597 if (dout1_[s1].
size() != dout2_[s2].
size())
600 for (
const auto& l1_w1dst1 : dout1_[s1])
602 const label1_t& l1 = l1_w1dst1.first;
603 const weight1_t& w1 = l1_w1dst1.second.first;
604 const state1_t& dst1 = l1_w1dst1.second.second;
606 const auto& s2out = dout2_.find(s2);
607 if (s2out == dout2_.cend())
609 const auto& s2outl = s2out->second.find(l1);
610 if (s2outl == s2out->second.cend())
613 state2_t dst2 = s2outl->second.second;
615 if (! weightset_t::equal(w1, w2))
618 const auto& isomorphics_to_dst1 =
fr_.
s1tos2_.find(dst1);
619 const auto& isomorphics_to_dst2 =
fr_.
s2tos1_.find(dst2);
621 if (isomorphics_to_dst1 ==
fr_.
s1tos2_.cend())
623 if (isomorphics_to_dst2 ==
fr_.
s2tos1_.cend())
627 worklist_.push({dst1, dst2});
632 else if (isomorphics_to_dst1 ==
fr_.
s1tos2_.cend()
633 || isomorphics_to_dst1->second != dst2
634 || isomorphics_to_dst2->second != dst1)
658 __func__,
": isomorphism-check not successfully performed");
661 res[s2s1.first] = s2s1.second;
670 o <<
"/* Origins." << std::endl
671 <<
" node [shape = box, style = rounded]" << std::endl;
675 o <<
" " << p.first - 2
676 <<
" [label = \"" << p.second <<
"\"]" << std::endl;
678 o <<
"*/" << std::endl;
684 template <
typename Aut1,
typename Aut2>
699 template <
typename Aut1,
typename Aut2>
703 const auto& a1 = aut1->as<Aut1>();
704 const auto& a2 = aut2->as<Aut2>();
std::vector< state1_t > states1_t
dout_t< automaton2_t > dout2_
s1tos2_t s1tos2_
Only meaningful if the tag is tag::isomorphic.
std::vector< state2_t > states2_t
bool trivially_different()
bool is_accessible(const Aut &a)
Whether all its states are accessible.
label_t_of< automaton1_t > label1_t
This is useful to make hashes with labels or weights as keys without using non-default constructors; ...
typename detail::label_t_of_impl< base_t< ValueSet >>::type label_t_of
std::size_t class_id
Automaton states partitioned into classes.
Functor to compare Values of ValueSets.
state_t_of< automaton1_t > state1_t
state_classes_t state_classes_
nout_t< automaton2_t > nout2_
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
typename detail::context_t_of_impl< base_t< ValueSet >>::type context_t_of
std::unordered_map< state_t_of< Automaton >, std::unordered_map< label_t_of< Automaton >, std::unordered_map< weight_t_of< Automaton >, std::vector< state_t_of< Automaton >>, vcsn::hash< weightset_t_of< Automaton >>, vcsn::equal_to< weightset_t_of< Automaton >>>, vcsn::hash< labelset_t_of< Automaton >>, vcsn::equal_to< labelset_t_of< Automaton >>>> nout_t
For the nonsequential case.
std::vector< class_pair_t > state_classes_t
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
std::pair< state1_t, state2_t > states_t
std::unordered_map< state1_t, state2_t > s1tos2_t
The maps associating the states of a1_ and the states of a2_->
bool are_isomorphic(const automaton &aut1, const automaton &aut2)
Bridge.
const full_response get_full_response()
bool is_isomorphism_valid()
std::unordered_map< state2_t, state1_t > s2tos1_t
are_isomorphicer(const Aut1 &a1, const Aut2 &a2)
label_t_of< automaton2_t > label2_t
origins_t origins()
Only meaningful if operator() returned true.
enum vcsn::are_isomorphicer::full_response::tag response
context_t_of< automaton1_t > context1_t
void hash_combine(std::size_t &seed, const T &v)
struct vcsn::are_isomorphicer::full_response fr_
#define HASH_TRANSITIONS(expression, endpoint_getter)
This is useful to make hashes with labels or weights as keys without using non-default constructors; ...
std::vector< std::pair< string_t, string_t >> transitions_t
dout_t< automaton1_t > dout1_
For the simpler, faster sequential case.
labelset_t_of< context1_t > labelset1_t
bool next_class_combination()
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
std::unordered_map< state_t_of< Automaton >, std::unordered_map< label_t_of< Automaton >, std::pair< weight_t_of< Automaton >, state_t_of< Automaton >>, vcsn::hash< labelset_t_of< Automaton >>, vcsn::equal_to< labelset_t_of< Automaton >>>> dout_t
See the comment for out_ in minimize.hh.
transition_t_of< automaton2_t > transition2_t
Provide a variadic mul on top of a binary mul(), and one().
const state_classes_t make_state_classes()
pair_t counterexample
Only meaningful if the tag is tag::counterexample.
context_t_of< automaton2_t > context2_t
labelset_t_of< context2_t > labelset2_t
bool are_isomorphic(const Aut1 &a1, const Aut2 &a2)
std::shared_ptr< detail::automaton_base > automaton
size_t size(const ExpSet &rs, const typename ExpSet::value_t &r)
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
nout_t< automaton1_t > nout1_
std::map< state2_t, state1_t > origins_t
A map from each a2_ state to the corresponding a1_ state.
weight_t_of< automaton1_t > weight1_t
void require(bool b, Args &&...args)
If b is not verified, raise an error with args as message.
void initialize_next_class_combination_state()
transition_t_of< automaton1_t > transition1_t
void print_classes(const state_classes_t &cs)
Handy debugging method.
typename detail::transition_t_of_impl< base_t< ValueSet >>::type transition_t_of
std::vector< long > class_permutation_generated_
static std::ostream & print(const origins_t &orig, std::ostream &o)
Print origins.
weightset_t_of< automaton1_t > weightset1_t
A datum specifying if two given automata are isomorphic, and why if they are not. ...
const full_response get_full_response_sequential()
void print_class_stats(const state_classes_t &cs)
Handy debugging method.
auto sum(const A &lhs, const B &rhs) -> decltype(join_automata(lhs, rhs))
weight_t_of< automaton2_t > weight2_t
std::pair< states1_t, states2_t > class_pair_t
ATTRIBUTE_PURE bool has(const std::deque< T, Allocator > &s, const T &e)
Whether e is member of s.
const full_response get_full_response_nonsequential()
bool is_isomorphism_valid_throwing()
class_id state_to_class(state_t_of< Automaton > s, Automaton &a)
void update_result_isomorphism()
state_t_of< automaton2_t > state2_t
bool is_sequential_filling(const Automaton &a, dout_t< Automaton > &dout)
weightset_t_of< automaton1_t > weightset2_t
auto sort(const Aut &a) -> permutation_automaton< Aut >
std::vector< long > class_permutation_max_
We need to keep some (small) state between a next_class_combination call and the next.
typename detail::weight_t_of_impl< base_t< ValueSet >>::type weight_t_of