![]() |
Vcsn
2.3a
Be Rational
|
Tarjan's algorithm to find all strongly connected components: recursive implementation. More...
#include <scc.hh>
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... | |
Tarjan's algorithm to find all strongly connected components: recursive implementation.
Often slightly faster than the iterative implementation, but may overflow the stack.
using vcsn::detail::scc_impl< Aut, tarjan_recursive_tag >::component_t = detail::component_t<Aut> |
using vcsn::detail::scc_impl< Aut, tarjan_recursive_tag >::components_t = detail::components_t<Aut> |
using vcsn::detail::scc_impl< Aut, tarjan_recursive_tag >::state_t = state_t_of<Aut> |
|
inline |
|
inline |
|
inlineprivate |
Definition at line 432 of file scc.hh.
References vcsn::has(), vcsn::min, and vcsn::detail::out().
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |