Vcsn  2.0
Be Rational
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
Public Types | Public Member Functions | Private Types | Private Member Functions | Private Attributes | List of all members
vcsn::detail::synchronizer< Aut > Class Template Reference

#include <synchronizing-word.hh>

Collaboration diagram for vcsn::detail::synchronizer< Aut >:

Public Types

using automaton_t = Aut
 
using word_t = typename labelset_t_of< automaton_t >::word_t
 
using state_t = state_t_of< automaton_t >
 
using transition_t = transition_t_of< automaton_t >
 
using label_t = label_t_of< automaton_t >
 

Public Member Functions

 synchronizer (const automaton_t &aut)
 
bool is_synchronizing ()
 
word_t greedy ()
 
word_t cycle ()
 
word_t synchroP ()
 
word_t synchroPL ()
 
word_t fastsynchro ()
 

Private Types

using pair_t = std::pair< state_t, state_t >
 
using dist_transition_t = std::pair< unsigned, transition_t >
 
using heuristic_t = auto(synchronizer::*)(state_t) -> int
 

Private Member Functions

void init_pair (bool keep_initials=false)
 
void init_synchro (bool keep_initials=false)
 
std::vector< transition_t > recompose_path (state_t from)
 
int dist (state_t s)
 
state_t dest_state (state_t s, const label_t &l)
 
void apply_label (const label_t &label)
 
void apply_path (const std::vector< transition_t > &path)
 
word_t synchro (heuristic_t heuristic)
 
word_t cycle_ ()
 
word_t fastsynchro_ ()
 
int delta (state_t p, const std::vector< transition_t > &w)
 Compute dist(d(s, w)) - dist(s). More...
 
int phi_1 (state_t p)
 Heuristic used for SynchroP. More...
 
int phi_2 (state_t p)
 Heuristic used for SynchroPL. More...
 
int phi_3 (const label_t &l)
 Heuristic used for FastSynchro. More...
 

Private Attributes

automaton_t aut_
 
pair_automaton< Aut > pair_
 
std::unordered_map< state_t,
dist_transition_t > 		paths_
 
std::unordered_set< state_t > todo_
 
word_t res_
 

Detailed Description

template<typename Aut>
class vcsn::detail::synchronizer< Aut >

Definition at line 92 of file synchronizing-word.hh.

Member Typedef Documentation

template<typename Aut>
using vcsn::detail::synchronizer< Aut >::automaton_t = Aut

Definition at line 95 of file synchronizing-word.hh.

template<typename Aut>
using vcsn::detail::synchronizer< Aut >::dist_transition_t = std::pair<unsigned, transition_t>
private

Definition at line 103 of file synchronizing-word.hh.

template<typename Aut>
using vcsn::detail::synchronizer< Aut >::heuristic_t = auto (synchronizer::*)(state_t) -> int
private

Definition at line 233 of file synchronizing-word.hh.

template<typename Aut>
using vcsn::detail::synchronizer< Aut >::label_t = label_t_of<automaton_t>

Definition at line 99 of file synchronizing-word.hh.

template<typename Aut>
using vcsn::detail::synchronizer< Aut >::pair_t = std::pair<state_t, state_t>
private

Definition at line 102 of file synchronizing-word.hh.

template<typename Aut>
using vcsn::detail::synchronizer< Aut >::state_t = state_t_of<automaton_t>

Definition at line 97 of file synchronizing-word.hh.

template<typename Aut>
using vcsn::detail::synchronizer< Aut >::transition_t = transition_t_of<automaton_t>

Definition at line 98 of file synchronizing-word.hh.

template<typename Aut>
using vcsn::detail::synchronizer< Aut >::word_t = typename labelset_t_of<automaton_t>::word_t

Definition at line 96 of file synchronizing-word.hh.

Constructor & Destructor Documentation

template<typename Aut>
vcsn::detail::synchronizer< Aut >::synchronizer ( const automaton_t &  aut)
inline

Definition at line 112 of file synchronizing-word.hh.

Member Function Documentation

template<typename Aut>
void vcsn::detail::synchronizer< Aut >::apply_label ( const label_t &  label)
inlineprivate

Definition at line 173 of file synchronizing-word.hh.

References vcsn::detail::synchronizer< Aut >::aut_, vcsn::detail::synchronizer< Aut >::dest_state(), vcsn::detail::synchronizer< Aut >::pair_, vcsn::detail::synchronizer< Aut >::res_, and vcsn::detail::synchronizer< Aut >::todo_.

Referenced by vcsn::detail::synchronizer< Aut >::apply_path(), and vcsn::detail::synchronizer< Aut >::fastsynchro_().

Here is the call graph for this function:

template<typename Aut>
void vcsn::detail::synchronizer< Aut >::apply_path ( const std::vector< transition_t > &  path)
inlineprivate

Definition at line 188 of file synchronizing-word.hh.

References vcsn::detail::synchronizer< Aut >::apply_label(), and vcsn::detail::synchronizer< Aut >::pair_.

Referenced by vcsn::detail::synchronizer< Aut >::cycle_(), vcsn::detail::synchronizer< Aut >::fastsynchro_(), and vcsn::detail::synchronizer< Aut >::synchro().

Here is the call graph for this function:

template<typename Aut>
word_t vcsn::detail::synchronizer< Aut >::cycle ( )
inline

Definition at line 212 of file synchronizing-word.hh.

References vcsn::detail::synchronizer< Aut >::cycle_().

Referenced by vcsn::synchronizing_word().

Here is the call graph for this function:

template<typename Aut>
word_t vcsn::detail::synchronizer< Aut >::cycle_ ( )
inlineprivate

Definition at line 257 of file synchronizing-word.hh.

References vcsn::detail::synchronizer< Aut >::apply_path(), vcsn::detail::synchronizer< Aut >::dist(), vcsn::detail::synchronizer< Aut >::init_synchro(), vcsn::detail::synchronizer< Aut >::pair_, vcsn::detail::synchronizer< Aut >::recompose_path(), vcsn::detail::synchronizer< Aut >::res_, and vcsn::detail::synchronizer< Aut >::todo_.

Referenced by vcsn::detail::synchronizer< Aut >::cycle().

Here is the call graph for this function:

template<typename Aut>
int vcsn::detail::synchronizer< Aut >::delta ( state_t  p,
const std::vector< transition_t > &  w 
)
inlineprivate

Compute dist(d(s, w)) - dist(s).

Definition at line 341 of file synchronizing-word.hh.

References vcsn::detail::synchronizer< Aut >::dest_state(), vcsn::detail::synchronizer< Aut >::dist(), and vcsn::detail::synchronizer< Aut >::pair_.

Referenced by vcsn::detail::synchronizer< Aut >::phi_1().

Here is the call graph for this function:

template<typename Aut>
state_t vcsn::detail::synchronizer< Aut >::dest_state ( state_t  s,
const label_t &  l 
)
inlineprivate

Definition at line 164 of file synchronizing-word.hh.

References vcsn::detail::synchronizer< Aut >::pair_, and vcsn::require().

Referenced by vcsn::detail::synchronizer< Aut >::apply_label(), vcsn::detail::synchronizer< Aut >::delta(), and vcsn::detail::synchronizer< Aut >::phi_3().

Here is the call graph for this function:

template<typename Aut>
int vcsn::detail::synchronizer< Aut >::dist ( state_t  s)
inlineprivate

Definition at line 157 of file synchronizing-word.hh.

References vcsn::detail::synchronizer< Aut >::pair_, and vcsn::detail::synchronizer< Aut >::paths_.

Referenced by vcsn::detail::synchronizer< Aut >::cycle_(), vcsn::detail::synchronizer< Aut >::delta(), vcsn::detail::synchronizer< Aut >::greedy(), vcsn::detail::synchronizer< Aut >::phi_2(), and vcsn::detail::synchronizer< Aut >::phi_3().

template<typename Aut>
word_t vcsn::detail::synchronizer< Aut >::fastsynchro ( )
inline

Definition at line 227 of file synchronizing-word.hh.

References vcsn::detail::synchronizer< Aut >::fastsynchro_().

Referenced by vcsn::synchronizing_word().

Here is the call graph for this function:

template<typename Aut>
word_t vcsn::detail::synchronizer< Aut >::fastsynchro_ ( )
inlineprivate

Definition at line 290 of file synchronizing-word.hh.

References vcsn::detail::synchronizer< Aut >::apply_label(), vcsn::detail::synchronizer< Aut >::apply_path(), vcsn::detail::synchronizer< Aut >::aut_, vcsn::detail::synchronizer< Aut >::init_synchro(), vcsn::detail::synchronizer< Aut >::pair_, vcsn::detail::synchronizer< Aut >::phi_2(), vcsn::detail::synchronizer< Aut >::phi_3(), vcsn::detail::synchronizer< Aut >::recompose_path(), vcsn::detail::synchronizer< Aut >::res_, and vcsn::detail::synchronizer< Aut >::todo_.

Referenced by vcsn::detail::synchronizer< Aut >::fastsynchro().

Here is the call graph for this function:

template<typename Aut>
word_t vcsn::detail::synchronizer< Aut >::greedy ( )
inline

Definition at line 207 of file synchronizing-word.hh.

References vcsn::detail::synchronizer< Aut >::dist(), and vcsn::detail::synchronizer< Aut >::synchro().

Referenced by vcsn::synchronizing_word().

Here is the call graph for this function:

template<typename Aut>
void vcsn::detail::synchronizer< Aut >::init_pair ( bool  keep_initials = false)
inlineprivate

Definition at line 117 of file synchronizing-word.hh.

References vcsn::detail::synchronizer< Aut >::aut_, vcsn::pair(), vcsn::detail::synchronizer< Aut >::pair_, vcsn::detail::synchronizer< Aut >::paths_, and vcsn::paths_ibfs().

Referenced by vcsn::detail::synchronizer< Aut >::init_synchro(), and vcsn::detail::synchronizer< Aut >::is_synchronizing().

Here is the call graph for this function:

template<typename Aut>
void vcsn::detail::synchronizer< Aut >::init_synchro ( bool  keep_initials = false)
inlineprivate

Definition at line 132 of file synchronizing-word.hh.

References vcsn::detail::synchronizer< Aut >::init_pair(), vcsn::detail::synchronizer< Aut >::pair_, vcsn::detail::synchronizer< Aut >::paths_, vcsn::require(), and vcsn::detail::synchronizer< Aut >::todo_.

Referenced by vcsn::detail::synchronizer< Aut >::cycle_(), vcsn::detail::synchronizer< Aut >::fastsynchro_(), and vcsn::detail::synchronizer< Aut >::synchro().

Here is the call graph for this function:

template<typename Aut>
bool vcsn::detail::synchronizer< Aut >::is_synchronizing ( )
inline

Definition at line 201 of file synchronizing-word.hh.

References vcsn::detail::synchronizer< Aut >::init_pair(), vcsn::detail::synchronizer< Aut >::pair_, and vcsn::detail::synchronizer< Aut >::paths_.

Referenced by vcsn::is_synchronizing().

Here is the call graph for this function:

template<typename Aut>
int vcsn::detail::synchronizer< Aut >::phi_1 ( state_t  p)
inlineprivate

Heuristic used for SynchroP.

phi_1(p) = Sum delta(s, w) for all s in the active states, with s != p. w is the shortest word that syncs the pair p.

Definition at line 352 of file synchronizing-word.hh.

References vcsn::detail::synchronizer< Aut >::delta(), vcsn::detail::synchronizer< Aut >::recompose_path(), and vcsn::detail::synchronizer< Aut >::todo_.

Referenced by vcsn::detail::synchronizer< Aut >::phi_2(), and vcsn::detail::synchronizer< Aut >::synchroP().

Here is the call graph for this function:

template<typename Aut>
int vcsn::detail::synchronizer< Aut >::phi_2 ( state_t  p)
inlineprivate

Heuristic used for SynchroPL.

phi2(p) = phi_1(p).

Definition at line 364 of file synchronizing-word.hh.

References vcsn::detail::synchronizer< Aut >::dist(), and vcsn::detail::synchronizer< Aut >::phi_1().

Referenced by vcsn::detail::synchronizer< Aut >::fastsynchro_(), and vcsn::detail::synchronizer< Aut >::synchroPL().

Here is the call graph for this function:

template<typename Aut>
int vcsn::detail::synchronizer< Aut >::phi_3 ( const label_t &  l)
inlineprivate

Heuristic used for FastSynchro.

phi3(l) = Sum dist(d(s, l)) - dist(s) forall s in the active states.

Definition at line 371 of file synchronizing-word.hh.

References vcsn::detail::synchronizer< Aut >::dest_state(), vcsn::detail::synchronizer< Aut >::dist(), and vcsn::detail::synchronizer< Aut >::todo_.

Referenced by vcsn::detail::synchronizer< Aut >::fastsynchro_().

Here is the call graph for this function:

template<typename Aut>
std::vector<transition_t> vcsn::detail::synchronizer< Aut >::recompose_path ( state_t  from)
inlineprivate

Definition at line 144 of file synchronizing-word.hh.

References vcsn::detail::synchronizer< Aut >::pair_, and vcsn::detail::synchronizer< Aut >::paths_.

Referenced by vcsn::detail::synchronizer< Aut >::cycle_(), vcsn::detail::synchronizer< Aut >::fastsynchro_(), vcsn::detail::synchronizer< Aut >::phi_1(), and vcsn::detail::synchronizer< Aut >::synchro().

template<typename Aut>
word_t vcsn::detail::synchronizer< Aut >::synchro ( heuristic_t  heuristic)
inlineprivate

Definition at line 235 of file synchronizing-word.hh.

References vcsn::detail::synchronizer< Aut >::apply_path(), vcsn::detail::synchronizer< Aut >::init_synchro(), vcsn::detail::synchronizer< Aut >::recompose_path(), vcsn::detail::synchronizer< Aut >::res_, and vcsn::detail::synchronizer< Aut >::todo_.

Referenced by vcsn::detail::synchronizer< Aut >::greedy(), vcsn::detail::synchronizer< Aut >::synchroP(), and vcsn::detail::synchronizer< Aut >::synchroPL().

Here is the call graph for this function:

template<typename Aut>
word_t vcsn::detail::synchronizer< Aut >::synchroP ( )
inline

Definition at line 217 of file synchronizing-word.hh.

References vcsn::detail::synchronizer< Aut >::phi_1(), and vcsn::detail::synchronizer< Aut >::synchro().

Referenced by vcsn::synchronizing_word().

Here is the call graph for this function:

template<typename Aut>
word_t vcsn::detail::synchronizer< Aut >::synchroPL ( )
inline

Definition at line 222 of file synchronizing-word.hh.

References vcsn::detail::synchronizer< Aut >::phi_2(), and vcsn::detail::synchronizer< Aut >::synchro().

Referenced by vcsn::synchronizing_word().

Here is the call graph for this function:

Member Data Documentation

template<typename Aut>
automaton_t vcsn::detail::synchronizer< Aut >::aut_
private

Definition at line 105 of file synchronizing-word.hh.

Referenced by vcsn::detail::synchronizer< Aut >::apply_label(), vcsn::detail::synchronizer< Aut >::fastsynchro_(), and vcsn::detail::synchronizer< Aut >::init_pair().

template<typename Aut>
pair_automaton<Aut> vcsn::detail::synchronizer< Aut >::pair_
private

Definition at line 106 of file synchronizing-word.hh.

Referenced by vcsn::detail::synchronizer< Aut >::apply_label(), vcsn::detail::synchronizer< Aut >::apply_path(), vcsn::detail::synchronizer< Aut >::cycle_(), vcsn::detail::synchronizer< Aut >::delta(), vcsn::detail::synchronizer< Aut >::dest_state(), vcsn::detail::synchronizer< Aut >::dist(), vcsn::detail::synchronizer< Aut >::fastsynchro_(), vcsn::detail::synchronizer< Aut >::init_pair(), vcsn::detail::synchronizer< Aut >::init_synchro(), vcsn::detail::synchronizer< Aut >::is_synchronizing(), and vcsn::detail::synchronizer< Aut >::recompose_path().

template<typename Aut>
std::unordered_map<state_t, dist_transition_t> vcsn::detail::synchronizer< Aut >::paths_
private

Definition at line 107 of file synchronizing-word.hh.

Referenced by vcsn::detail::synchronizer< Aut >::dist(), vcsn::detail::synchronizer< Aut >::init_pair(), vcsn::detail::synchronizer< Aut >::init_synchro(), vcsn::detail::synchronizer< Aut >::is_synchronizing(), and vcsn::detail::synchronizer< Aut >::recompose_path().

template<typename Aut>
word_t vcsn::detail::synchronizer< Aut >::res_
private

Definition at line 109 of file synchronizing-word.hh.

Referenced by vcsn::detail::synchronizer< Aut >::apply_label(), vcsn::detail::synchronizer< Aut >::cycle_(), vcsn::detail::synchronizer< Aut >::fastsynchro_(), and vcsn::detail::synchronizer< Aut >::synchro().

template<typename Aut>
std::unordered_set<state_t> vcsn::detail::synchronizer< Aut >::todo_
private

Definition at line 108 of file synchronizing-word.hh.

Referenced by vcsn::detail::synchronizer< Aut >::apply_label(), vcsn::detail::synchronizer< Aut >::cycle_(), vcsn::detail::synchronizer< Aut >::fastsynchro_(), vcsn::detail::synchronizer< Aut >::init_synchro(), vcsn::detail::synchronizer< Aut >::phi_1(), vcsn::detail::synchronizer< Aut >::phi_3(), and vcsn::detail::synchronizer< Aut >::synchro().

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