![]() |
Vcsn
2.1
Be Rational
|
#include <are-isomorphic.hh>
Classes | |
struct | full_response |
A datum specifying if two given automata are isomorphic, and why if they are not. More... | |
Public Types | |
using | states1_t = std::vector< state1_t > |
using | states2_t = std::vector< state2_t > |
using | class_id = std::size_t |
Automaton states partitioned into classes. More... | |
using | class_pair_t = std::pair< states1_t, states2_t > |
using | state_classes_t = std::vector< class_pair_t > |
using | origins_t = std::map< state2_t, state1_t > |
A map from each a2_ state to the corresponding a1_ state. More... | |
Public Member Functions | |
are_isomorphicer (const Aut1 &a1, const Aut2 &a2) | |
const full_response | get_full_response () |
template<typename Automaton > | |
class_id | state_to_class (state_t_of< Automaton > s, Automaton &a) |
const state_classes_t | make_state_classes () |
void | print_class_stats (const state_classes_t &cs) |
Handy debugging method. More... | |
void | print_classes (const state_classes_t &cs) |
Handy debugging method. More... | |
bool | is_isomorphism_valid () |
bool | is_isomorphism_valid_throwing () |
void | update_result_isomorphism () |
long | factorial (long n) |
void | initialize_next_class_combination_state () |
bool | next_class_combination () |
const full_response | get_full_response_nonsequential () |
const full_response | get_full_response_sequential () |
bool | operator() () |
origins_t | origins () |
Only meaningful if operator() returned true. More... | |
Static Public Member Functions | |
static std::ostream & | print (const origins_t &orig, std::ostream &o) |
Print origins. More... | |
Public Attributes | |
state_classes_t | state_classes_ |
std::vector< long > | class_permutation_max_ |
We need to keep some (small) state between a next_class_combination call and the next. More... | |
std::vector< long > | class_permutation_generated_ |
Private Member Functions | |
template<typename Automaton > | |
bool | is_sequential_filling (const Automaton &a, dout_t< Automaton > &dout) |
void | fill_nouts_ () |
void | clear () |
bool | trivially_different () |
Private Attributes | |
automaton1_t | a1_ |
automaton2_t | a2_ |
dout_t< automaton1_t > | dout1_ |
For the simpler, faster sequential case. More... | |
dout_t< automaton2_t > | dout2_ |
nout_t< automaton1_t > | nout1_ |
nout_t< automaton2_t > | nout2_ |
worklist_t | worklist_ |
struct vcsn::are_isomorphicer::full_response | fr_ |
Definition at line 32 of file are-isomorphic.hh.
|
private |
Definition at line 35 of file are-isomorphic.hh.
|
private |
Definition at line 44 of file are-isomorphic.hh.
using vcsn::are_isomorphicer< Aut1, Aut2 >::class_id = std::size_t |
Automaton states partitioned into classes.
It's guaranteed that a left[right] state in a given class can not be isomorphic to a right[left] in a different class. The idea of course is to restrict the brute-force search to the states within a single class.
Definition at line 245 of file are-isomorphic.hh.
using vcsn::are_isomorphicer< Aut1, Aut2 >::class_pair_t = std::pair<states1_t, states2_t> |
Definition at line 246 of file are-isomorphic.hh.
|
private |
Definition at line 36 of file are-isomorphic.hh.
|
private |
Definition at line 45 of file are-isomorphic.hh.
|
private |
See the comment for out_ in minimize.hh.
Definition at line 72 of file are-isomorphic.hh.
|
private |
Definition at line 40 of file are-isomorphic.hh.
|
private |
Definition at line 49 of file are-isomorphic.hh.
|
private |
Definition at line 38 of file are-isomorphic.hh.
|
private |
Definition at line 47 of file are-isomorphic.hh.
|
private |
Definition at line 56 of file are-isomorphic.hh.
|
private |
For the nonsequential case.
Definition at line 90 of file are-isomorphic.hh.
using vcsn::are_isomorphicer< Aut1, Aut2 >::origins_t = std::map<state2_t, state1_t> |
A map from each a2_ state to the corresponding a1_ state.
The map is ordered, as usual for origins, hence different from fr_.s2tos1_.
Definition at line 651 of file are-isomorphic.hh.
|
private |
A worklist of pairs of states which are candidate to be isomorphic.
Or "A candidate-isomorphic state pair worklist", written in Reverse-Polish English.
Definition at line 97 of file are-isomorphic.hh.
|
private |
The maps associating the states of a1_ and the states of a2_->
Definition at line 102 of file are-isomorphic.hh.
|
private |
Definition at line 103 of file are-isomorphic.hh.
|
private |
Definition at line 39 of file are-isomorphic.hh.
|
private |
Definition at line 48 of file are-isomorphic.hh.
using vcsn::are_isomorphicer< Aut1, Aut2 >::state_classes_t = std::vector<class_pair_t> |
Definition at line 247 of file are-isomorphic.hh.
using vcsn::are_isomorphicer< Aut1, Aut2 >::states1_t = std::vector<state1_t> |
Definition at line 238 of file are-isomorphic.hh.
using vcsn::are_isomorphicer< Aut1, Aut2 >::states2_t = std::vector<state2_t> |
Definition at line 239 of file are-isomorphic.hh.
|
private |
Definition at line 58 of file are-isomorphic.hh.
|
private |
Definition at line 42 of file are-isomorphic.hh.
|
private |
Definition at line 51 of file are-isomorphic.hh.
|
private |
Definition at line 41 of file are-isomorphic.hh.
|
private |
Definition at line 50 of file are-isomorphic.hh.
|
private |
Definition at line 37 of file are-isomorphic.hh.
|
private |
Definition at line 46 of file are-isomorphic.hh.
|
private |
Definition at line 55 of file are-isomorphic.hh.
|
private |
Definition at line 98 of file are-isomorphic.hh.
|
inline |
Definition at line 198 of file are-isomorphic.hh.
|
inlineprivate |
Definition at line 170 of file are-isomorphic.hh.
Referenced by vcsn::are_isomorphicer< Aut1, Aut2 >::get_full_response().
|
inline |
Definition at line 463 of file are-isomorphic.hh.
Referenced by vcsn::are_isomorphicer< Aut1, Aut2 >::initialize_next_class_combination_state().
|
inlineprivate |
Definition at line 160 of file are-isomorphic.hh.
Referenced by vcsn::are_isomorphicer< Aut1, Aut2 >::get_full_response().
|
inline |
Definition at line 204 of file are-isomorphic.hh.
References vcsn::are_isomorphicer< Aut1, Aut2 >::clear(), vcsn::are_isomorphicer< Aut1, Aut2 >::fill_nouts_(), vcsn::are_isomorphicer< Aut1, Aut2 >::fr_, vcsn::are_isomorphicer< Aut1, Aut2 >::get_full_response_nonsequential(), vcsn::are_isomorphicer< Aut1, Aut2 >::get_full_response_sequential(), vcsn::is_accessible(), vcsn::are_isomorphicer< Aut1, Aut2 >::is_sequential_filling(), vcsn::require(), vcsn::are_isomorphicer< Aut1, Aut2 >::full_response::response, vcsn::are_isomorphicer< Aut1, Aut2 >::full_response::trivially_different, and vcsn::are_isomorphicer< Aut1, Aut2 >::trivially_different().
Referenced by vcsn::are_isomorphicer< Aut1, Aut2 >::operator()().
|
inline |
Definition at line 539 of file are-isomorphic.hh.
References vcsn::are_isomorphicer< Aut1, Aut2 >::fr_, vcsn::are_isomorphicer< Aut1, Aut2 >::initialize_next_class_combination_state(), vcsn::are_isomorphicer< Aut1, Aut2 >::is_isomorphism_valid(), vcsn::are_isomorphicer< Aut1, Aut2 >::full_response::isomorphic, vcsn::are_isomorphicer< Aut1, Aut2 >::make_state_classes(), vcsn::are_isomorphicer< Aut1, Aut2 >::next_class_combination(), vcsn::are_isomorphicer< Aut1, Aut2 >::full_response::nocounterexample, vcsn::are_isomorphicer< Aut1, Aut2 >::full_response::response, and vcsn::are_isomorphicer< Aut1, Aut2 >::update_result_isomorphism().
Referenced by vcsn::are_isomorphicer< Aut1, Aut2 >::get_full_response().
|
inline |
Definition at line 574 of file are-isomorphic.hh.
References vcsn::are_isomorphicer< Aut1, Aut2 >::full_response::counterexample, vcsn::are_isomorphicer< Aut1, Aut2 >::fr_, vcsn::are_isomorphicer< Aut1, Aut2 >::full_response::isomorphic, vcsn::are_isomorphicer< Aut1, Aut2 >::full_response::response, vcsn::are_isomorphicer< Aut1, Aut2 >::full_response::s1tos2_, vcsn::are_isomorphicer< Aut1, Aut2 >::full_response::s2tos1_, and vcsn::rat::size().
Referenced by vcsn::are_isomorphicer< Aut1, Aut2 >::get_full_response().
|
inline |
Definition at line 476 of file are-isomorphic.hh.
References vcsn::are_isomorphicer< Aut1, Aut2 >::factorial().
Referenced by vcsn::are_isomorphicer< Aut1, Aut2 >::get_full_response_nonsequential().
|
inline |
Definition at line 375 of file are-isomorphic.hh.
References vcsn::are_isomorphicer< Aut1, Aut2 >::is_isomorphism_valid_throwing().
Referenced by vcsn::are_isomorphicer< Aut1, Aut2 >::get_full_response_nonsequential().
|
inline |
Definition at line 386 of file are-isomorphic.hh.
References vcsn::are_isomorphicer< Aut1, Aut2 >::fr_, vcsn::has(), vcsn::are_isomorphicer< Aut1, Aut2 >::full_response::s1tos2_, and vcsn::are_isomorphicer< Aut1, Aut2 >::full_response::s2tos1_.
Referenced by vcsn::are_isomorphicer< Aut1, Aut2 >::is_isomorphism_valid().
|
inlineprivate |
Definition at line 141 of file are-isomorphic.hh.
Referenced by vcsn::are_isomorphicer< Aut1, Aut2 >::get_full_response().
|
inline |
Definition at line 305 of file are-isomorphic.hh.
References vcsn::sort(), and vcsn::are_isomorphicer< Aut1, Aut2 >::state_to_class().
Referenced by vcsn::are_isomorphicer< Aut1, Aut2 >::get_full_response_nonsequential().
|
inline |
Definition at line 490 of file are-isomorphic.hh.
Referenced by vcsn::are_isomorphicer< Aut1, Aut2 >::get_full_response_nonsequential().
|
inline |
Definition at line 642 of file are-isomorphic.hh.
References vcsn::are_isomorphicer< Aut1, Aut2 >::get_full_response(), vcsn::are_isomorphicer< Aut1, Aut2 >::full_response::isomorphic, and vcsn::are_isomorphicer< Aut1, Aut2 >::full_response::response.
|
inline |
Only meaningful if operator() returned true.
Definition at line 655 of file are-isomorphic.hh.
References vcsn::are_isomorphicer< Aut1, Aut2 >::fr_, vcsn::are_isomorphicer< Aut1, Aut2 >::full_response::isomorphic, vcsn::require(), and vcsn::are_isomorphicer< Aut1, Aut2 >::full_response::s2tos1_.
|
inlinestatic |
Print origins.
Definition at line 668 of file are-isomorphic.hh.
|
inline |
Handy debugging method.
Definition at line 342 of file are-isomorphic.hh.
References vcsn::sum().
|
inline |
Handy debugging method.
Definition at line 361 of file are-isomorphic.hh.
|
inline |
Definition at line 251 of file are-isomorphic.hh.
References vcsn::hash_combine(), and HASH_TRANSITIONS.
Referenced by vcsn::are_isomorphicer< Aut1, Aut2 >::make_state_classes().
|
inlineprivate |
Definition at line 178 of file are-isomorphic.hh.
Referenced by vcsn::are_isomorphicer< Aut1, Aut2 >::get_full_response().
|
inline |
Definition at line 451 of file are-isomorphic.hh.
References vcsn::are_isomorphicer< Aut1, Aut2 >::fr_, vcsn::are_isomorphicer< Aut1, Aut2 >::full_response::s1tos2_, and vcsn::are_isomorphicer< Aut1, Aut2 >::full_response::s2tos1_.
Referenced by vcsn::are_isomorphicer< Aut1, Aut2 >::get_full_response_nonsequential().
|
private |
Definition at line 60 of file are-isomorphic.hh.
|
private |
Definition at line 61 of file are-isomorphic.hh.
std::vector<long> vcsn::are_isomorphicer< Aut1, Aut2 >::class_permutation_generated_ |
Definition at line 474 of file are-isomorphic.hh.
std::vector<long> vcsn::are_isomorphicer< Aut1, Aut2 >::class_permutation_max_ |
We need to keep some (small) state between a next_class_combination call and the next.
Definition at line 473 of file are-isomorphic.hh.
|
private |
For the simpler, faster sequential case.
Definition at line 75 of file are-isomorphic.hh.
|
private |
Definition at line 76 of file are-isomorphic.hh.
|
private |
Referenced by vcsn::are_isomorphicer< Aut1, Aut2 >::get_full_response(), vcsn::are_isomorphicer< Aut1, Aut2 >::get_full_response_nonsequential(), vcsn::are_isomorphicer< Aut1, Aut2 >::get_full_response_sequential(), vcsn::are_isomorphicer< Aut1, Aut2 >::is_isomorphism_valid_throwing(), vcsn::are_isomorphicer< Aut1, Aut2 >::origins(), and vcsn::are_isomorphicer< Aut1, Aut2 >::update_result_isomorphism().
|
private |
Definition at line 91 of file are-isomorphic.hh.
|
private |
Definition at line 92 of file are-isomorphic.hh.
state_classes_t vcsn::are_isomorphicer< Aut1, Aut2 >::state_classes_ |
Definition at line 248 of file are-isomorphic.hh.
|
private |
Definition at line 99 of file are-isomorphic.hh.