Vcsn  2.3
Be Rational
vcsn::are_isomorphicer< Aut1, Aut2 > Class Template Reference

#include <are-isomorphic.hh>

Collaboration diagram for vcsn::are_isomorphicer< Aut1, Aut2 >:

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 Types

using automaton1_t = Aut1
 
using context1_t = context_t_of< automaton1_t >
 
using weightset1_t = weightset_t_of< automaton1_t >
 
using labelset1_t = labelset_t_of< context1_t >
 
using state1_t = state_t_of< automaton1_t >
 
using label1_t = label_t_of< automaton1_t >
 
using weight1_t = weight_t_of< automaton1_t >
 
using transition1_t = transition_t_of< automaton1_t >
 
using automaton2_t = Aut2
 
using context2_t = context_t_of< automaton2_t >
 
using weightset2_t = weightset_t_of< automaton1_t >
 
using labelset2_t = labelset_t_of< context2_t >
 
using state2_t = state_t_of< automaton2_t >
 
using label2_t = label_t_of< automaton2_t >
 
using weight2_t = weight_t_of< automaton2_t >
 
using transition2_t = transition_t_of< automaton2_t >
 
using weightset_t = weightset1_t
 
using labelset_t = labelset1_t
 
using states_t = std::pair< state1_t, state2_t >
 
template<Automaton Aut>
using dout_t = 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 >>>>
 See the comment for out_ in minimize.hh. More...
 
template<Automaton Aut>
using nout_t = 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 >>>>
 For the nonsequential case. More...
 
using pair_t = std::pair< state1_t, state2_t >
 A worklist of pairs of states which are candidate to be isomorphic. More...
 
using worklist_t = std::stack< pair_t >
 
using s1tos2_t = std::unordered_map< state1_t, state2_t >
 The maps associating the states of a1_ and the states of a2_-> More...
 
using s2tos1_t = std::unordered_map< state2_t, state1_t >
 

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_tdout1_
 For the simpler, faster sequential case. More...
 
dout_t< automaton2_tdout2_
 
nout_t< automaton1_tnout1_
 
nout_t< automaton2_tnout2_
 
worklist_t worklist_
 
struct vcsn::are_isomorphicer::full_response fr_
 

Detailed Description

template<Automaton Aut1, Automaton Aut2>
class vcsn::are_isomorphicer< Aut1, Aut2 >

Definition at line 32 of file are-isomorphic.hh.

Member Typedef Documentation

template<Automaton Aut1, Automaton Aut2>
using vcsn::are_isomorphicer< Aut1, Aut2 >::automaton1_t = Aut1
private

Definition at line 35 of file are-isomorphic.hh.

template<Automaton Aut1, Automaton Aut2>
using vcsn::are_isomorphicer< Aut1, Aut2 >::automaton2_t = Aut2
private

Definition at line 44 of file are-isomorphic.hh.

template<Automaton Aut1, Automaton Aut2>
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.

template<Automaton Aut1, Automaton Aut2>
using vcsn::are_isomorphicer< Aut1, Aut2 >::class_pair_t = std::pair<states1_t, states2_t>

Definition at line 251 of file are-isomorphic.hh.

template<Automaton Aut1, Automaton Aut2>
using vcsn::are_isomorphicer< Aut1, Aut2 >::context1_t = context_t_of<automaton1_t>
private

Definition at line 36 of file are-isomorphic.hh.

template<Automaton Aut1, Automaton Aut2>
using vcsn::are_isomorphicer< Aut1, Aut2 >::context2_t = context_t_of<automaton2_t>
private

Definition at line 45 of file are-isomorphic.hh.

template<Automaton Aut1, Automaton Aut2>
template<Automaton Aut>
using vcsn::are_isomorphicer< Aut1, Aut2 >::dout_t = 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>>>>
private

See the comment for out_ in minimize.hh.

Definition at line 77 of file are-isomorphic.hh.

template<Automaton Aut1, Automaton Aut2>
using vcsn::are_isomorphicer< Aut1, Aut2 >::label1_t = label_t_of<automaton1_t>
private

Definition at line 40 of file are-isomorphic.hh.

template<Automaton Aut1, Automaton Aut2>
using vcsn::are_isomorphicer< Aut1, Aut2 >::label2_t = label_t_of<automaton2_t>
private

Definition at line 49 of file are-isomorphic.hh.

template<Automaton Aut1, Automaton Aut2>
using vcsn::are_isomorphicer< Aut1, Aut2 >::labelset1_t = labelset_t_of<context1_t>
private

Definition at line 38 of file are-isomorphic.hh.

template<Automaton Aut1, Automaton Aut2>
using vcsn::are_isomorphicer< Aut1, Aut2 >::labelset2_t = labelset_t_of<context2_t>
private

Definition at line 47 of file are-isomorphic.hh.

template<Automaton Aut1, Automaton Aut2>
using vcsn::are_isomorphicer< Aut1, Aut2 >::labelset_t = labelset1_t
private

Definition at line 62 of file are-isomorphic.hh.

template<Automaton Aut1, Automaton Aut2>
template<Automaton Aut>
using vcsn::are_isomorphicer< Aut1, Aut2 >::nout_t = 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>>>>
private

For the nonsequential case.

Definition at line 95 of file are-isomorphic.hh.

template<Automaton Aut1, Automaton Aut2>
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.

template<Automaton Aut1, Automaton Aut2>
using vcsn::are_isomorphicer< Aut1, Aut2 >::pair_t = std::pair<state1_t, state2_t>
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.

template<Automaton Aut1, Automaton Aut2>
using vcsn::are_isomorphicer< Aut1, Aut2 >::s1tos2_t = std::unordered_map<state1_t, state2_t>
private

The maps associating the states of a1_ and the states of a2_->

Definition at line 107 of file are-isomorphic.hh.

template<Automaton Aut1, Automaton Aut2>
using vcsn::are_isomorphicer< Aut1, Aut2 >::s2tos1_t = std::unordered_map<state2_t, state1_t>
private

Definition at line 108 of file are-isomorphic.hh.

template<Automaton Aut1, Automaton Aut2>
using vcsn::are_isomorphicer< Aut1, Aut2 >::state1_t = state_t_of<automaton1_t>
private

Definition at line 39 of file are-isomorphic.hh.

template<Automaton Aut1, Automaton Aut2>
using vcsn::are_isomorphicer< Aut1, Aut2 >::state2_t = state_t_of<automaton2_t>
private

Definition at line 48 of file are-isomorphic.hh.

template<Automaton Aut1, Automaton Aut2>
using vcsn::are_isomorphicer< Aut1, Aut2 >::state_classes_t = std::vector<class_pair_t>

Definition at line 252 of file are-isomorphic.hh.

template<Automaton Aut1, Automaton Aut2>
using vcsn::are_isomorphicer< Aut1, Aut2 >::states1_t = std::vector<state1_t>

Definition at line 243 of file are-isomorphic.hh.

template<Automaton Aut1, Automaton Aut2>
using vcsn::are_isomorphicer< Aut1, Aut2 >::states2_t = std::vector<state2_t>

Definition at line 244 of file are-isomorphic.hh.

template<Automaton Aut1, Automaton Aut2>
using vcsn::are_isomorphicer< Aut1, Aut2 >::states_t = std::pair<state1_t, state2_t>
private

Definition at line 64 of file are-isomorphic.hh.

template<Automaton Aut1, Automaton Aut2>
using vcsn::are_isomorphicer< Aut1, Aut2 >::transition1_t = transition_t_of<automaton1_t>
private

Definition at line 42 of file are-isomorphic.hh.

template<Automaton Aut1, Automaton Aut2>
using vcsn::are_isomorphicer< Aut1, Aut2 >::transition2_t = transition_t_of<automaton2_t>
private

Definition at line 51 of file are-isomorphic.hh.

template<Automaton Aut1, Automaton Aut2>
using vcsn::are_isomorphicer< Aut1, Aut2 >::weight1_t = weight_t_of<automaton1_t>
private

Definition at line 41 of file are-isomorphic.hh.

template<Automaton Aut1, Automaton Aut2>
using vcsn::are_isomorphicer< Aut1, Aut2 >::weight2_t = weight_t_of<automaton2_t>
private

Definition at line 50 of file are-isomorphic.hh.

template<Automaton Aut1, Automaton Aut2>
using vcsn::are_isomorphicer< Aut1, Aut2 >::weightset1_t = weightset_t_of<automaton1_t>
private

Definition at line 37 of file are-isomorphic.hh.

template<Automaton Aut1, Automaton Aut2>
using vcsn::are_isomorphicer< Aut1, Aut2 >::weightset2_t = weightset_t_of<automaton1_t>
private

Definition at line 46 of file are-isomorphic.hh.

template<Automaton Aut1, Automaton Aut2>
using vcsn::are_isomorphicer< Aut1, Aut2 >::weightset_t = weightset1_t
private

Definition at line 61 of file are-isomorphic.hh.

template<Automaton Aut1, Automaton Aut2>
using vcsn::are_isomorphicer< Aut1, Aut2 >::worklist_t = std::stack<pair_t>
private

Definition at line 103 of file are-isomorphic.hh.

Constructor & Destructor Documentation

template<Automaton Aut1, Automaton Aut2>
vcsn::are_isomorphicer< Aut1, Aut2 >::are_isomorphicer ( const Aut1 &  a1,
const Aut2 &  a2 
)
inline

Definition at line 203 of file are-isomorphic.hh.

Member Function Documentation

template<Automaton Aut1, Automaton Aut2>
void vcsn::are_isomorphicer< Aut1, Aut2 >::clear ( )
inlineprivate
template<Automaton Aut1, Automaton Aut2>
long vcsn::are_isomorphicer< Aut1, Aut2 >::factorial ( long  n)
inline
template<Automaton Aut1, Automaton Aut2>
void vcsn::are_isomorphicer< Aut1, Aut2 >::fill_nouts_ ( )
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().

Here is the call graph for this function:

template<Automaton Aut1, Automaton Aut2>
const full_response vcsn::are_isomorphicer< Aut1, Aut2 >::get_full_response_sequential ( )
inline
template<Automaton Aut1, Automaton Aut2>
void vcsn::are_isomorphicer< Aut1, Aut2 >::initialize_next_class_combination_state ( )
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().

Here is the call graph for this function:

template<Automaton Aut1, Automaton Aut2>
bool vcsn::are_isomorphicer< Aut1, Aut2 >::is_isomorphism_valid ( )
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().

Here is the call graph for this function:

template<Automaton Aut1, Automaton Aut2>
bool vcsn::are_isomorphicer< Aut1, Aut2 >::is_isomorphism_valid_throwing ( )
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().

Here is the call graph for this function:

template<Automaton Aut1, Automaton Aut2>
template<Automaton Aut>
bool vcsn::are_isomorphicer< Aut1, Aut2 >::is_sequential_filling ( const Aut &  a,
dout_t< Aut > &  dout 
)
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().

Here is the call graph for this function:

template<Automaton Aut1, Automaton Aut2>
const state_classes_t vcsn::are_isomorphicer< Aut1, Aut2 >::make_state_classes ( )
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().

Here is the call graph for this function:

template<Automaton Aut1, Automaton Aut2>
bool vcsn::are_isomorphicer< Aut1, Aut2 >::next_class_combination ( )
inline
template<Automaton Aut1, Automaton Aut2>
bool vcsn::are_isomorphicer< Aut1, Aut2 >::operator() ( )
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.

Here is the call graph for this function:

template<Automaton Aut1, Automaton Aut2>
origins_t vcsn::are_isomorphicer< Aut1, Aut2 >::origins ( )
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_.

Here is the call graph for this function:

template<Automaton Aut1, Automaton Aut2>
static std::ostream& vcsn::are_isomorphicer< Aut1, Aut2 >::print ( const origins_t orig,
std::ostream &  o 
)
inlinestatic

Print origins.

Definition at line 676 of file are-isomorphic.hh.

template<Automaton Aut1, Automaton Aut2>
void vcsn::are_isomorphicer< Aut1, Aut2 >::print_class_stats ( const state_classes_t cs,
std::ostream &  o = std::cerr 
) const
inline

Handy debugging method.

Definition at line 347 of file are-isomorphic.hh.

References vcsn::min.

template<Automaton Aut1, Automaton Aut2>
void vcsn::are_isomorphicer< Aut1, Aut2 >::print_classes ( const state_classes_t cs,
std::ostream &  o = std::cerr 
)
inline

Handy debugging method.

Definition at line 367 of file are-isomorphic.hh.

template<Automaton Aut1, Automaton Aut2>
template<Automaton Aut>
class_id vcsn::are_isomorphicer< Aut1, Aut2 >::state_to_class ( state_t_of< Aut >  s,
Aut &  a 
)
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().

Here is the call graph for this function:

template<Automaton Aut1, Automaton Aut2>
bool vcsn::are_isomorphicer< Aut1, Aut2 >::trivially_different ( )
inlineprivate

Member Data Documentation

template<Automaton Aut1, Automaton Aut2>
automaton1_t vcsn::are_isomorphicer< Aut1, Aut2 >::a1_
private

Definition at line 66 of file are-isomorphic.hh.

template<Automaton Aut1, Automaton Aut2>
automaton2_t vcsn::are_isomorphicer< Aut1, Aut2 >::a2_
private

Definition at line 67 of file are-isomorphic.hh.

template<Automaton Aut1, Automaton Aut2>
std::vector<long> vcsn::are_isomorphicer< Aut1, Aut2 >::class_permutation_generated_

Definition at line 481 of file are-isomorphic.hh.

template<Automaton Aut1, Automaton Aut2>
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.

template<Automaton Aut1, Automaton Aut2>
dout_t<automaton1_t> vcsn::are_isomorphicer< Aut1, Aut2 >::dout1_
private

For the simpler, faster sequential case.

Definition at line 80 of file are-isomorphic.hh.

template<Automaton Aut1, Automaton Aut2>
dout_t<automaton2_t> vcsn::are_isomorphicer< Aut1, Aut2 >::dout2_
private

Definition at line 81 of file are-isomorphic.hh.

template<Automaton Aut1, Automaton Aut2>
nout_t<automaton1_t> vcsn::are_isomorphicer< Aut1, Aut2 >::nout1_
private

Definition at line 96 of file are-isomorphic.hh.

template<Automaton Aut1, Automaton Aut2>
nout_t<automaton2_t> vcsn::are_isomorphicer< Aut1, Aut2 >::nout2_
private

Definition at line 97 of file are-isomorphic.hh.

template<Automaton Aut1, Automaton Aut2>
state_classes_t vcsn::are_isomorphicer< Aut1, Aut2 >::state_classes_

Definition at line 253 of file are-isomorphic.hh.

template<Automaton Aut1, Automaton Aut2>
worklist_t vcsn::are_isomorphicer< Aut1, Aut2 >::worklist_
private

Definition at line 104 of file are-isomorphic.hh.


The documentation for this class was generated from the following file: