![]() |
Vcsn
2.3a
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<Automaton Aut> | |
class_id | state_to_class (state_t_of< Aut > s, Aut &a) |
const state_classes_t | make_state_classes () |
void | print_class_stats (const state_classes_t &cs, std::ostream &o=std::cerr) const |
Handy debugging method. More... | |
void | print_classes (const state_classes_t &cs, std::ostream &o=std::cerr) |
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<Automaton Aut> | |
bool | is_sequential_filling (const Aut &a, dout_t< Aut > &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 250 of file are-isomorphic.hh.
using vcsn::are_isomorphicer< Aut1, Aut2 >::class_pair_t = std::pair<states1_t, states2_t> |
Definition at line 251 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 77 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 62 of file are-isomorphic.hh.
|
private |
For the nonsequential case.
Definition at line 95 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 659 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 102 of file are-isomorphic.hh.
|
private |
The maps associating the states of a1_ and the states of a2_->
Definition at line 107 of file are-isomorphic.hh.
|
private |
Definition at line 108 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 252 of file are-isomorphic.hh.
using vcsn::are_isomorphicer< Aut1, Aut2 >::states1_t = std::vector<state1_t> |
Definition at line 243 of file are-isomorphic.hh.
using vcsn::are_isomorphicer< Aut1, Aut2 >::states2_t = std::vector<state2_t> |
Definition at line 244 of file are-isomorphic.hh.
|
private |
Definition at line 64 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 61 of file are-isomorphic.hh.
|
private |
Definition at line 103 of file are-isomorphic.hh.
|
inline |
Definition at line 203 of file are-isomorphic.hh.
|
inlineprivate |
Definition at line 175 of file are-isomorphic.hh.
Referenced by vcsn::are_isomorphicer< Aut1, Aut2 >::get_full_response().
|
inline |
Definition at line 470 of file are-isomorphic.hh.
References vcsn::res.
Referenced by vcsn::are_isomorphicer< Aut1, Aut2 >::initialize_next_class_combination_state().
|
inlineprivate |
Definition at line 165 of file are-isomorphic.hh.
References vcsn::detail::all_transitions().
Referenced by vcsn::are_isomorphicer< Aut1, Aut2 >::get_full_response().
|
inline |
Definition at line 209 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 547 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 582 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 483 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 382 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 393 of file are-isomorphic.hh.
References vcsn::detail::all_out(), 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 146 of file are-isomorphic.hh.
References vcsn::detail::all_transitions().
Referenced by vcsn::are_isomorphicer< Aut1, Aut2 >::get_full_response().
|
inline |
Definition at line 310 of file are-isomorphic.hh.
References vcsn::res, 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 498 of file are-isomorphic.hh.
Referenced by vcsn::are_isomorphicer< Aut1, Aut2 >::get_full_response_nonsequential().
|
inline |
Definition at line 650 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 663 of file are-isomorphic.hh.
References vcsn::are_isomorphicer< Aut1, Aut2 >::fr_, vcsn::are_isomorphicer< Aut1, Aut2 >::full_response::isomorphic, vcsn::require(), vcsn::res, and vcsn::are_isomorphicer< Aut1, Aut2 >::full_response::s2tos1_.
|
inlinestatic |
Print origins.
Definition at line 676 of file are-isomorphic.hh.
|
inline |
|
inline |
Handy debugging method.
Definition at line 367 of file are-isomorphic.hh.
|
inline |
Definition at line 256 of file are-isomorphic.hh.
References vcsn::detail::all_in(), vcsn::detail::all_out(), vcsn::hash_combine(), HASH_TRANSITIONS, and vcsn::res.
Referenced by vcsn::are_isomorphicer< Aut1, Aut2 >::make_state_classes().
|
inlineprivate |
Definition at line 183 of file are-isomorphic.hh.
Referenced by vcsn::are_isomorphicer< Aut1, Aut2 >::get_full_response().
|
inline |
Definition at line 458 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 66 of file are-isomorphic.hh.
|
private |
Definition at line 67 of file are-isomorphic.hh.
std::vector<long> vcsn::are_isomorphicer< Aut1, Aut2 >::class_permutation_generated_ |
Definition at line 481 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 480 of file are-isomorphic.hh.
|
private |
For the simpler, faster sequential case.
Definition at line 80 of file are-isomorphic.hh.
|
private |
Definition at line 81 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 96 of file are-isomorphic.hh.
|
private |
Definition at line 97 of file are-isomorphic.hh.
state_classes_t vcsn::are_isomorphicer< Aut1, Aut2 >::state_classes_ |
Definition at line 253 of file are-isomorphic.hh.
|
private |
Definition at line 104 of file are-isomorphic.hh.