#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_t >	recompose_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_t >	todo_

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.

template<Automaton Aut>

using vcsn::detail::word_synchronizer< Aut >::paths_t = std::unordered_map<state_t_of<pair_automaton_t>, dist_transition_t>

private

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

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

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

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

Here is the call graph for this function:

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>

int vcsn::detail::word_synchronizer< Aut >::dist ( state_t s ) const

inlineprivate

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

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

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 >::fastsynchro_ ( )

inlineprivate

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

References vcsn::detail::word_synchronizer< Aut >::apply_label(), vcsn::detail::word_synchronizer< Aut >::apply_path(), vcsn::detail::word_synchronizer< Aut >::init_synchro(), vcsn::detail::word_synchronizer< Aut >::phi_2(), vcsn::detail::word_synchronizer< Aut >::phi_3(), vcsn::detail::word_synchronizer< Aut >::recompose_path(), and vcsn::detail::word_synchronizer< Aut >::res_.

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 >::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>

std::vector<transition_t> vcsn::detail::word_synchronizer< Aut >::recompose_path ( state_t from ) const

inlineprivate

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

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

template<Automaton Aut>

word_t vcsn::detail::word_synchronizer< Aut >::synchro ( heuristic_t heuristic )

inlineprivate

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

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

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

Here is the call graph for this function:

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>

word_t vcsn::detail::word_synchronizer< Aut >::res_

private

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

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

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:

vcsn/algos/synchronizing-word.hh

Public Types

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Detailed Description

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

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

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