vcsn::detail::scc_tarjan_iterative_impl< Aut > Class Template Reference

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

#include <scc.hh>

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

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_tarjan_iterative_impl (const Aut &aut)
const components_t &	components () const

Private Types
using	iterator_t = decltype(aut_->out(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_t >	stack_
	List of states in the same the component. More...
components_t	components_
	All components. More...

Detailed Description

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

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 264 of file scc.hh.

Member Typedef Documentation

template<typename Aut >

using vcsn::detail::scc_tarjan_iterative_impl< Aut >::component_t = detail::component_t<Aut>

Definition at line 270 of file scc.hh.

template<typename Aut >

using vcsn::detail::scc_tarjan_iterative_impl< Aut >::components_t = detail::components_t<Aut>

Definition at line 271 of file scc.hh.

template<typename Aut >

using vcsn::detail::scc_tarjan_iterative_impl< Aut >::iterator_t = decltype(aut_->out(state_t{}).begin())

private

Iterator on outgoing transitions.

Definition at line 359 of file scc.hh.

template<typename Aut >

using vcsn::detail::scc_tarjan_iterative_impl< Aut >::state_t = state_t_of<Aut>

Definition at line 267 of file scc.hh.

template<typename Aut >

using vcsn::detail::scc_tarjan_iterative_impl< Aut >::transition_t = transition_t_of<Aut>

Definition at line 268 of file scc.hh.

Constructor & Destructor Documentation

template<typename Aut >

vcsn::detail::scc_tarjan_iterative_impl< Aut >::scc_tarjan_iterative_impl ( const Aut &  aut )

inline

Definition at line 273 of file scc.hh.

Member Function Documentation

template<typename Aut >

const components_t& vcsn::detail::scc_tarjan_iterative_impl< Aut >::components ( ) const

inline

Definition at line 281 of file scc.hh.

References vcsn::detail::scc_tarjan_iterative_impl< Aut >::components_.

Referenced by vcsn::strong_components().

template<typename Aut >

void vcsn::detail::scc_tarjan_iterative_impl< Aut >::dfs ( state_t  s )

inlineprivate

Definition at line 287 of file scc.hh.

References vcsn::detail::scc_tarjan_iterative_impl< Aut >::aut_, vcsn::detail::scc_tarjan_iterative_impl< Aut >::components_, vcsn::detail::scc_tarjan_iterative_impl< Aut >::curr_state_num_, vcsn::detail::scc_tarjan_iterative_impl< Aut >::dfs_stack_, vcsn::has(), vcsn::detail::scc_tarjan_iterative_impl< Aut >::low_, vcsn::detail::scc_tarjan_iterative_impl< Aut >::low_max_, vcsn::detail::scc_tarjan_iterative_impl< Aut >::number_, and vcsn::detail::scc_tarjan_iterative_impl< Aut >::stack_.

Here is the call graph for this function:

Member Data Documentation

template<typename Aut >

Aut vcsn::detail::scc_tarjan_iterative_impl< Aut >::aut_

private

Input automaton.

Definition at line 338 of file scc.hh.

Referenced by vcsn::detail::scc_tarjan_iterative_impl< Aut >::dfs().

template<typename Aut >

components_t vcsn::detail::scc_tarjan_iterative_impl< Aut >::components_

private

All components.

Definition at line 356 of file scc.hh.

Referenced by vcsn::detail::scc_tarjan_iterative_impl< Aut >::components(), and vcsn::detail::scc_tarjan_iterative_impl< Aut >::dfs().

template<typename Aut >

std::size_t vcsn::detail::scc_tarjan_iterative_impl< Aut >::curr_state_num_ = 0

private

The current visited state.

Definition at line 345 of file scc.hh.

Referenced by vcsn::detail::scc_tarjan_iterative_impl< Aut >::dfs().

template<typename Aut >

std::vector<step_t> vcsn::detail::scc_tarjan_iterative_impl< Aut >::dfs_stack_

private

Definition at line 341 of file scc.hh.

Referenced by vcsn::detail::scc_tarjan_iterative_impl< Aut >::dfs().

template<typename Aut >

std::unordered_map<state_t, std::size_t> vcsn::detail::scc_tarjan_iterative_impl< Aut >::low_

private

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

Definition at line 349 of file scc.hh.

Referenced by vcsn::detail::scc_tarjan_iterative_impl< Aut >::dfs().

template<typename Aut >

std::size_t vcsn::detail::scc_tarjan_iterative_impl< Aut >::low_max_ = std::numeric_limits<unsigned int>::max()

private

the maximum possible of a value in low_.

Definition at line 351 of file scc.hh.

Referenced by vcsn::detail::scc_tarjan_iterative_impl< Aut >::dfs().

template<typename Aut >

std::unordered_map<state_t, std::size_t> vcsn::detail::scc_tarjan_iterative_impl< Aut >::number_

private

Store the visit order of each state.

Definition at line 347 of file scc.hh.

Referenced by vcsn::detail::scc_tarjan_iterative_impl< Aut >::dfs().

template<typename Aut >

std::vector<state_t> vcsn::detail::scc_tarjan_iterative_impl< Aut >::stack_

private

List of states in the same the component.

Definition at line 354 of file scc.hh.

Referenced by vcsn::detail::scc_tarjan_iterative_impl< Aut >::dfs().

---

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

• vcsn/algos/scc.hh