Vcsn  2.2
Be Rational
vcsn::detail::scc_impl< Aut, tarjan_iterative_tag > Class Template Reference

Tarjan's algorithm to find all strongly connected components: iterative implementation. More...

#include <scc.hh>

Inheritance diagram for vcsn::detail::scc_impl< Aut, tarjan_iterative_tag >:
Collaboration diagram for vcsn::detail::scc_impl< Aut, tarjan_iterative_tag >:

Classes

struct  step_t
 Step of one state contain infomation next successor and end iterator(output transitions or successors of this state). More...
 

Public Types

using state_t = state_t_of< Aut >
 
using transition_t = transition_t_of< Aut >
 
using component_t = detail::component_t< Aut >
 
using components_t = detail::components_t< Aut >
 

Public Member Functions

 scc_impl (const Aut &aut)
 
const components_tcomponents () const
 

Private Types

using iterator_t = decltype(out(aut_, state_t{}).begin())
 Iterator on outgoing transitions. More...
 

Private Member Functions

void dfs (state_t s)
 

Private Attributes

Aut aut_
 Input automaton. More...
 
std::vector< step_t > dfs_stack_
 
std::size_t curr_state_num_ = 0
 The current visited state. More...
 
std::unordered_map< state_t, std::size_t > number_
 Store the visit order of each state. More...
 
std::unordered_map< state_t, std::size_t > low_
 low_[s] is minimum of state that it can go. More...
 
std::size_t low_max_ = std::numeric_limits<unsigned int>::max()
 the maximum possible of a value in low_. More...
 
std::vector< state_tstack_
 List of states in the same the component. More...
 
components_t components_
 All components. More...
 

Detailed Description

template<Automaton Aut>
class vcsn::detail::scc_impl< Aut, tarjan_iterative_tag >

Tarjan's algorithm to find all strongly connected components: iterative implementation.

Often slightly slower than the recursive implementation, but no limitation due to the stack.

Definition at line 285 of file scc.hh.

Member Typedef Documentation

template<Automaton Aut>
using vcsn::detail::scc_impl< Aut, tarjan_iterative_tag >::component_t = detail::component_t<Aut>

Definition at line 291 of file scc.hh.

template<Automaton Aut>
using vcsn::detail::scc_impl< Aut, tarjan_iterative_tag >::components_t = detail::components_t<Aut>

Definition at line 292 of file scc.hh.

template<Automaton Aut>
using vcsn::detail::scc_impl< Aut, tarjan_iterative_tag >::iterator_t = decltype(out(aut_, state_t{}).begin())
private

Iterator on outgoing transitions.

Definition at line 380 of file scc.hh.

template<Automaton Aut>
using vcsn::detail::scc_impl< Aut, tarjan_iterative_tag >::state_t = state_t_of<Aut>

Definition at line 288 of file scc.hh.

template<Automaton Aut>
using vcsn::detail::scc_impl< Aut, tarjan_iterative_tag >::transition_t = transition_t_of<Aut>

Definition at line 289 of file scc.hh.

Constructor & Destructor Documentation

template<Automaton Aut>
vcsn::detail::scc_impl< Aut, tarjan_iterative_tag >::scc_impl ( const Aut &  aut)
inline

Definition at line 294 of file scc.hh.

Member Function Documentation

template<Automaton Aut>
const components_t& vcsn::detail::scc_impl< Aut, tarjan_iterative_tag >::components ( ) const
inline

Definition at line 302 of file scc.hh.

template<Automaton Aut>
void vcsn::detail::scc_impl< Aut, tarjan_iterative_tag >::dfs ( state_t  s)
inlineprivate

Definition at line 308 of file scc.hh.

References vcsn::has(), and vcsn::detail::out().

Here is the call graph for this function:

Member Data Documentation

template<Automaton Aut>
Aut vcsn::detail::scc_impl< Aut, tarjan_iterative_tag >::aut_
private

Input automaton.

Definition at line 359 of file scc.hh.

template<Automaton Aut>
components_t vcsn::detail::scc_impl< Aut, tarjan_iterative_tag >::components_
private

All components.

Definition at line 377 of file scc.hh.

template<Automaton Aut>
std::size_t vcsn::detail::scc_impl< Aut, tarjan_iterative_tag >::curr_state_num_ = 0
private

The current visited state.

Definition at line 366 of file scc.hh.

template<Automaton Aut>
std::vector<step_t> vcsn::detail::scc_impl< Aut, tarjan_iterative_tag >::dfs_stack_
private

Definition at line 362 of file scc.hh.

template<Automaton Aut>
std::unordered_map<state_t, std::size_t> vcsn::detail::scc_impl< Aut, tarjan_iterative_tag >::low_
private

low_[s] is minimum of state that it can go.

Definition at line 370 of file scc.hh.

template<Automaton Aut>
std::size_t vcsn::detail::scc_impl< Aut, tarjan_iterative_tag >::low_max_ = std::numeric_limits<unsigned int>::max()
private

the maximum possible of a value in low_.

Definition at line 372 of file scc.hh.

template<Automaton Aut>
std::unordered_map<state_t, std::size_t> vcsn::detail::scc_impl< Aut, tarjan_iterative_tag >::number_
private

Store the visit order of each state.

Definition at line 368 of file scc.hh.

template<Automaton Aut>
std::vector<state_t> vcsn::detail::scc_impl< Aut, tarjan_iterative_tag >::stack_
private

List of states in the same the component.

Definition at line 375 of file scc.hh.


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