Eliminate states in an automaton. More...

#include <to-expression.hh>

Collaboration diagram for vcsn::detail::state_eliminator< Aut, Profiler >:

Public Types
using	profiler_t = Profiler

using	profile_t = typename profiler_t::state_profile

using	automaton_t = std::remove_cv_t< Aut >

using	state_t = state_t_of< automaton_t >

Public Member Functions
	state_eliminator (automaton_t &aut, profiler_t &profiler)
	Prepare for state-elimination. More...

void	operator() (state_t s)
	Eliminate state s. More...

void	operator() ()
	Eliminate all the states, in the order specified by next_state. More...

Private Types
using	heap_t = vcsn::min_fibonacci_heap< profile_t >
	Max-heap to decide the order of state-elimination. More...

Private Member Functions
void	update_heap_ ()

void	show_heap_ () const
	Show the heap, for debugging. More...

template<typename Kind = typename context_t_of<automaton_t>::kind_t>
auto	eliminate_state_ (state_t s) -> std::enable_if_t< std::is_same< Kind, labels_are_one >::value, void >
	Eliminate state s in the case of labels are one. More...

template<typename Kind >
auto	eliminate_state_impl_ (state_t s) -> std::enable_if_t< std::is_same< Kind, labels_are_expressions >::value, void >
	Eliminate state s in the case of labels are expressions. More...

Private Attributes
automaton_t	aut_
	The automaton we work on. More...

profiler_t &	profiler_
	The profiler we work with. Corresponding to a specific heuristic. More...

heap_t	todo_

std::vector< typename heap_t::handle_type >	handles_
	Map: state -> heap-handle. More...

std::unordered_set< state_t >	neighbors_

Detailed Description

template<Automaton Aut, typename Profiler>
struct vcsn::detail::state_eliminator< Aut, Profiler >

Eliminate states in an automaton.

Precondition: The labelset is oneset or expressionset.

Definition at line 226 of file to-expression.hh.

Member Typedef Documentation

◆ automaton_t

template<Automaton Aut, typename Profiler >

using vcsn::detail::state_eliminator< Aut, Profiler >::automaton_t = std::remove_cv_t<Aut>

Definition at line 230 of file to-expression.hh.

◆ heap_t

template<Automaton Aut, typename Profiler >

using vcsn::detail::state_eliminator< Aut, Profiler >::heap_t = vcsn::min_fibonacci_heap<profile_t>

private

Max-heap to decide the order of state-elimination.

Definition at line 415 of file to-expression.hh.

◆ profile_t

template<Automaton Aut, typename Profiler >

using vcsn::detail::state_eliminator< Aut, Profiler >::profile_t = typename profiler_t::state_profile

Definition at line 229 of file to-expression.hh.

◆ profiler_t

template<Automaton Aut, typename Profiler >

using vcsn::detail::state_eliminator< Aut, Profiler >::profiler_t = Profiler

Definition at line 228 of file to-expression.hh.

◆ state_t

template<Automaton Aut, typename Profiler >

using vcsn::detail::state_eliminator< Aut, Profiler >::state_t = state_t_of<automaton_t>

Definition at line 231 of file to-expression.hh.

Constructor & Destructor Documentation

◆ state_eliminator()

template<Automaton Aut, typename Profiler >

vcsn::detail::state_eliminator< Aut, Profiler >::state_eliminator	(	automaton_t &	aut,
		profiler_t &	profiler
	)

inline

Prepare for state-elimination.

Parameters

aut	the input automaton
profiler	the generator of state profiles.

Definition at line 237 of file to-expression.hh.

References vcsn::detail::naive_profiler< Aut >::aut_.

Member Function Documentation

◆ eliminate_state_()

template<Automaton Aut, typename Profiler >

template<typename Kind = typename context_t_of<automaton_t>::kind_t>

auto vcsn::detail::state_eliminator< Aut, Profiler >::eliminate_state_ ( state_t s ) -> std::enable_if_t<std::is_same<Kind, labels_are_one>::value, void>

inlineprivate

Eliminate state s in the case of labels are one.

Definition at line 311 of file to-expression.hh.

References vcsn::detail::all_in(), vcsn::detail::all_out(), vcsn::detail::naive_profiler< Aut >::aut_, vcsn::detail::in(), vcsn::detail::make_vector(), vcsn::detail::out(), vcsn::detail::outin(), and vcsn::rat::size().

Here is the call graph for this function:

◆ eliminate_state_impl_()

template<Automaton Aut, typename Profiler >

template<typename Kind >

auto vcsn::detail::state_eliminator< Aut, Profiler >::eliminate_state_impl_ ( state_t s ) -> std::enable_if_t<std::is_same<Kind, labels_are_expressions>::value, void>

inlineprivate

Eliminate state s in the case of labels are expressions.

Definition at line 369 of file to-expression.hh.

References vcsn::detail::all_in(), vcsn::detail::all_out(), vcsn::detail::naive_profiler< Aut >::aut_, vcsn::detail::in(), vcsn::detail::make_vector(), vcsn::detail::out(), and vcsn::detail::outin().

Here is the call graph for this function:

◆ operator()() [1/2]

template<Automaton Aut, typename Profiler >

void vcsn::detail::state_eliminator< Aut, Profiler >::operator() ( state_t s )

inline

Eliminate state s.

Definition at line 247 of file to-expression.hh.

References vcsn::detail::naive_profiler< Aut >::aut_, and vcsn::require().

Here is the call graph for this function:

◆ operator()() [2/2]

template<Automaton Aut, typename Profiler >

void vcsn::detail::state_eliminator< Aut, Profiler >::operator() ( )

inline

Eliminate all the states, in the order specified by next_state.

Definition at line 262 of file to-expression.hh.

◆ show_heap_()

template<Automaton Aut, typename Profiler >

void vcsn::detail::state_eliminator< Aut, Profiler >::show_heap_ ( ) const

inlineprivate

Show the heap, for debugging.

Definition at line 298 of file to-expression.hh.

◆ update_heap_()

template<Automaton Aut, typename Profiler >

void vcsn::detail::state_eliminator< Aut, Profiler >::update_heap_ ( )

inlineprivate

Definition at line 277 of file to-expression.hh.

References vcsn::detail::naive_profiler< Aut >::aut_.

Member Data Documentation

◆ aut_

template<Automaton Aut, typename Profiler >

automaton_t vcsn::detail::state_eliminator< Aut, Profiler >::aut_

private

The automaton we work on.

Definition at line 410 of file to-expression.hh.

◆ handles_

template<Automaton Aut, typename Profiler >

std::vector<typename heap_t::handle_type> vcsn::detail::state_eliminator< Aut, Profiler >::handles_

private

Map: state -> heap-handle.

Definition at line 418 of file to-expression.hh.

◆ neighbors_

template<Automaton Aut, typename Profiler >

std::unordered_set<state_t> vcsn::detail::state_eliminator< Aut, Profiler >::neighbors_

private

Definition at line 420 of file to-expression.hh.

◆ profiler_

template<Automaton Aut, typename Profiler >

profiler_t& vcsn::detail::state_eliminator< Aut, Profiler >::profiler_

private

The profiler we work with. Corresponding to a specific heuristic.

Definition at line 412 of file to-expression.hh.

◆ todo_

template<Automaton Aut, typename Profiler >

heap_t vcsn::detail::state_eliminator< Aut, Profiler >::todo_

private

Definition at line 416 of file to-expression.hh.

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

vcsn/algos/to-expression.hh

Public Types

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Detailed Description

template<Automaton Aut, typename Profiler> struct vcsn::detail::state_eliminator< Aut, Profiler >

Member Typedef Documentation

◆ automaton_t

◆ heap_t

◆ profile_t

◆ profiler_t

◆ state_t

Constructor & Destructor Documentation

◆ state_eliminator()

Member Function Documentation

◆ eliminate_state_()

◆ eliminate_state_impl_()

◆ operator()() [1/2]

◆ operator()() [2/2]

◆ show_heap_()

◆ update_heap_()

Member Data Documentation

◆ aut_

◆ handles_

◆ neighbors_

◆ profiler_

◆ todo_

template<Automaton Aut, typename Profiler>
struct vcsn::detail::state_eliminator< Aut, Profiler >