vcsn::detail::scc_impl< Aut, tarjan_recursive_tag > Class Template Reference

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

#include <scc.hh>

Collaboration diagram for vcsn::detail::scc_impl< Aut, tarjan_recursive_tag >:

Public Types
using	state_t = state_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_t &	components () const

Private Member Functions
void	dfs (state_t s)

Private Attributes
Aut	aut_
	Input automaton. More...
std::size_t	curr_state_num_ = 0
	The current visited state. More...
components_t	components_
	All components. More...
std::unordered_set< state_t >	marked_
	Visited states. More...
std::unordered_map< state_t, std::size_t >	low_
	low_[s] is minimum of low_{X}, with X is all states on output transitions of s. More...
std::vector< state_t >	stack_
	List of states in the same the component. More...

Detailed Description

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

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

Often slightly faster than the iterative implementation, but may overflow the stack.

Definition at line 415 of file scc.hh.

Member Typedef Documentation

component_t

template<Automaton Aut>

using vcsn::detail::scc_impl< Aut, tarjan_recursive_tag >::component_t = detail::component_t<Aut>

Definition at line 419 of file scc.hh.

components_t

template<Automaton Aut>

using vcsn::detail::scc_impl< Aut, tarjan_recursive_tag >::components_t = detail::components_t<Aut>

Definition at line 420 of file scc.hh.

state_t

template<Automaton Aut>

using vcsn::detail::scc_impl< Aut, tarjan_recursive_tag >::state_t = state_t_of<Aut>

Definition at line 418 of file scc.hh.

Constructor & Destructor Documentation

scc_impl()

template<Automaton Aut>

vcsn::detail::scc_impl< Aut, tarjan_recursive_tag >::scc_impl ( const Aut &  aut )

inline

Definition at line 422 of file scc.hh.

References vcsn::detail::reverse_postorder_impl< Aut >::dfs(), vcsn::has(), and vcsn::detail::reverse_postorder_impl< Aut >::marked_.

Here is the call graph for this function:

Member Function Documentation

components()

template<Automaton Aut>

const components_t& vcsn::detail::scc_impl< Aut, tarjan_recursive_tag >::components ( ) const

inline

Definition at line 430 of file scc.hh.

dfs()

template<Automaton Aut>

void vcsn::detail::scc_impl< Aut, tarjan_recursive_tag >::dfs ( state_t  s )

inlineprivate

Definition at line 436 of file scc.hh.

References vcsn::detail::reverse_postorder_impl< Aut >::dfs(), vcsn::has(), vcsn::detail::reverse_postorder_impl< Aut >::marked_, vcsn::min, and vcsn::detail::out().

Here is the call graph for this function:

Member Data Documentation

aut_

template<Automaton Aut>

Aut vcsn::detail::scc_impl< Aut, tarjan_recursive_tag >::aut_

private

Input automaton.

Definition at line 473 of file scc.hh.

components_

template<Automaton Aut>

components_t vcsn::detail::scc_impl< Aut, tarjan_recursive_tag >::components_

private

All components.

Definition at line 478 of file scc.hh.

curr_state_num_

template<Automaton Aut>

std::size_t vcsn::detail::scc_impl< Aut, tarjan_recursive_tag >::curr_state_num_ = 0

private

The current visited state.

It used to preorder number counter.

Definition at line 476 of file scc.hh.

low_

template<Automaton Aut>

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

private

low_[s] is minimum of low_{X}, with X is all states on output transitions of s.

Definition at line 483 of file scc.hh.

marked_

template<Automaton Aut>

std::unordered_set<state_t> vcsn::detail::scc_impl< Aut, tarjan_recursive_tag >::marked_

private

Visited states.

Definition at line 480 of file scc.hh.

stack_

template<Automaton Aut>

std::vector<state_t> vcsn::detail::scc_impl< Aut, tarjan_recursive_tag >::stack_

private

List of states in the same the component.

Definition at line 485 of file scc.hh.

---

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

• vcsn/algos/scc.hh