Vcsn
2.1
Be Rational
|
Tarjan's algorithm to find all strongly connected components: iterative implementation. More...
#include <scc.hh>
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... | |
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.
using vcsn::detail::scc_tarjan_iterative_impl< Aut >::component_t = detail::component_t<Aut> |
using vcsn::detail::scc_tarjan_iterative_impl< Aut >::components_t = detail::components_t<Aut> |
|
private |
using vcsn::detail::scc_tarjan_iterative_impl< Aut >::state_t = state_t_of<Aut> |
using vcsn::detail::scc_tarjan_iterative_impl< Aut >::transition_t = transition_t_of<Aut> |
|
inline |
|
inline |
Definition at line 281 of file scc.hh.
References vcsn::detail::scc_tarjan_iterative_impl< Aut >::components_.
Referenced by vcsn::strong_components().
|
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_.
|
private |
Input automaton.
Definition at line 338 of file scc.hh.
Referenced by vcsn::detail::scc_tarjan_iterative_impl< Aut >::dfs().
|
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().
|
private |
The current visited state.
Definition at line 345 of file scc.hh.
Referenced by vcsn::detail::scc_tarjan_iterative_impl< Aut >::dfs().
|
private |
Definition at line 341 of file scc.hh.
Referenced by vcsn::detail::scc_tarjan_iterative_impl< Aut >::dfs().
|
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().
|
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().
|
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().
|
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().