Vcsn  2.2
Be Rational
vcsn::detail::word_synchronizer< Aut > Class Template Reference

#include <synchronizing-word.hh>

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

Public Types

using automaton_t = Aut
 
using word_t = word_t_of< automaton_t >
 
using transition_t = transition_t_of< automaton_t >
 
using label_t = label_t_of< automaton_t >
 

Public Member Functions

 word_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 state_t = state_t_of< automaton_t >
 
using pair_automaton_t = pair_automaton< automaton_t >
 
using state_name_t = std::pair< state_t, state_t >
 
using dist_transition_t = std::pair< unsigned, transition_t_of< pair_automaton_t >>
 
using paths_t = std::unordered_map< state_t_of< pair_automaton_t >, dist_transition_t >
 
using path_t = typename paths_t::value_type
 
using heuristic_t = auto(word_synchronizer::*)(state_t) const -> int
 

Private Member Functions

void init_pair (bool keep_initials=false)
 
void init_synchro (bool keep_initials=false)
 
std::vector< transition_trecompose_path (state_t from) const
 
int dist (state_t s) const
 
state_t dest_state (state_t s, const label_t &l) const
 
void apply_label (const label_t &label)
 
void apply_path (const std::vector< transition_t > &path)
 "Apply" a word to the set of active states (for each state, for each label, perform s = d(s)) More...
 
word_t synchro (heuristic_t heuristic)
 
word_t cycle_ ()
 
word_t fastsynchro_ ()
 
int delta (state_t p, const std::vector< transition_t > &w) const
 Compute dist(d(s, w)) - dist(s). More...
 
int phi_1 (state_t p) const
 Heuristic used for SynchroP. More...
 
int phi_2 (state_t p) const
 Heuristic used for SynchroPL. More...
 
int phi_3 (const label_t &l) const
 Heuristic used for FastSynchro. More...
 

Private Attributes

automaton_t aut_
 Input automaton. More...
 
pair_automaton_t pair_
 Corresponding pair automaton. More...
 
paths_t paths_
 
std::unordered_set< state_ttodo_
 
word_t res_
 

Detailed Description

template<Automaton Aut>
class vcsn::detail::word_synchronizer< Aut >

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

Member Typedef Documentation

template<Automaton Aut>
using vcsn::detail::word_synchronizer< Aut >::automaton_t = Aut

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

template<Automaton Aut>
using vcsn::detail::word_synchronizer< Aut >::dist_transition_t = std::pair<unsigned, transition_t_of<pair_automaton_t>>
private

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

template<Automaton Aut>
using vcsn::detail::word_synchronizer< Aut >::heuristic_t = auto (word_synchronizer::*)(state_t) const -> int
private

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

template<Automaton Aut>
using vcsn::detail::word_synchronizer< Aut >::label_t = label_t_of<automaton_t>

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

template<Automaton Aut>
using vcsn::detail::word_synchronizer< Aut >::pair_automaton_t = pair_automaton<automaton_t>
private

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

template<Automaton Aut>
using vcsn::detail::word_synchronizer< Aut >::path_t = typename paths_t::value_type
private

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

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

template<Automaton Aut>
using vcsn::detail::word_synchronizer< Aut >::state_name_t = std::pair<state_t, state_t>
private

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

template<Automaton Aut>
using vcsn::detail::word_synchronizer< Aut >::state_t = state_t_of<automaton_t>
private

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

template<Automaton Aut>
using vcsn::detail::word_synchronizer< Aut >::transition_t = transition_t_of<automaton_t>

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

template<Automaton Aut>
using vcsn::detail::word_synchronizer< Aut >::word_t = word_t_of<automaton_t>

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

Constructor & Destructor Documentation

template<Automaton Aut>
vcsn::detail::word_synchronizer< Aut >::word_synchronizer ( const automaton_t aut)
inline

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

Member Function Documentation

template<Automaton Aut>
void vcsn::detail::word_synchronizer< Aut >::apply_label ( const label_t label)
inlineprivate

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

References vcsn::detail::word_synchronizer< Aut >::dest_state().

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

Here is the call graph for this function:

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

"Apply" a word to the set of active states (for each state, for each label, perform s = d(s))

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

References vcsn::detail::word_synchronizer< Aut >::apply_label().

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

Here is the call graph for this function:

template<Automaton Aut>
word_t vcsn::detail::word_synchronizer< Aut >::cycle ( )
inline

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

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

Referenced by vcsn::synchronizing_word().

Here is the call graph for this function:

template<Automaton Aut>
word_t vcsn::detail::word_synchronizer< Aut >::cycle_ ( )
inlineprivate
template<Automaton Aut>
int vcsn::detail::word_synchronizer< Aut >::delta ( state_t  p,
const std::vector< transition_t > &  w 
) const
inlineprivate

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

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

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

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

Here is the call graph for this function:

template<Automaton Aut>
state_t vcsn::detail::word_synchronizer< Aut >::dest_state ( state_t  s,
const label_t l 
) const
inlineprivate

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

References vcsn::detail::out(), vcsn::require(), and vcsn::rat::size().

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

Here is the call graph for this function:

template<Automaton Aut>
word_t vcsn::detail::word_synchronizer< Aut >::fastsynchro ( )
inline

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

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

Referenced by vcsn::synchronizing_word().

Here is the call graph for this function:

template<Automaton Aut>
word_t vcsn::detail::word_synchronizer< Aut >::greedy ( )
inline

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

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

Referenced by vcsn::synchronizing_word().

Here is the call graph for this function:

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

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

References vcsn::detail::erase_if(), vcsn::pair(), and vcsn::paths_ibfs().

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

Here is the call graph for this function:

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

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

References vcsn::detail::word_synchronizer< Aut >::init_pair(), and vcsn::require().

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

Here is the call graph for this function:

template<Automaton Aut>
bool vcsn::detail::word_synchronizer< Aut >::is_synchronizing ( )
inline

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

References vcsn::detail::word_synchronizer< Aut >::init_pair().

Referenced by vcsn::is_synchronizing().

Here is the call graph for this function:

template<Automaton Aut>
int vcsn::detail::word_synchronizer< Aut >::phi_1 ( state_t  p) const
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 354 of file synchronizing-word.hh.

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

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

Here is the call graph for this function:

template<Automaton Aut>
int vcsn::detail::word_synchronizer< Aut >::phi_2 ( state_t  p) const
inlineprivate

Heuristic used for SynchroPL.

phi2(p) = phi_1(p).

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

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

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

Here is the call graph for this function:

template<Automaton Aut>
int vcsn::detail::word_synchronizer< Aut >::phi_3 ( const label_t l) const
inlineprivate

Heuristic used for FastSynchro.

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

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

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

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

Here is the call graph for this function:

template<Automaton Aut>
word_t vcsn::detail::word_synchronizer< Aut >::synchro ( heuristic_t  heuristic)
inlineprivate
template<Automaton Aut>
word_t vcsn::detail::word_synchronizer< Aut >::synchroP ( )
inline

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

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

Referenced by vcsn::synchronizing_word().

Here is the call graph for this function:

template<Automaton Aut>
word_t vcsn::detail::word_synchronizer< Aut >::synchroPL ( )
inline

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

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

Referenced by vcsn::synchronizing_word().

Here is the call graph for this function:

Member Data Documentation

template<Automaton Aut>
automaton_t vcsn::detail::word_synchronizer< Aut >::aut_
private

Input automaton.

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

template<Automaton Aut>
pair_automaton_t vcsn::detail::word_synchronizer< Aut >::pair_
private

Corresponding pair automaton.

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

template<Automaton Aut>
paths_t vcsn::detail::word_synchronizer< Aut >::paths_
private

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

template<Automaton Aut>
std::unordered_set<state_t> vcsn::detail::word_synchronizer< Aut >::todo_
private

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


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