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

Use Tarjan's algorithm to find all strongly connected components. More...

#include <scc.hh>

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

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

Private Member Functions
void	dfs (state_t s, const Aut &aut)

Private Attributes
std::size_t	curr_comp_num_ = 0
	The current component number. More...
std::size_t	curr_vertex_num_ = 0
	The current visited vertex. More...
components_t	components_
	All compnents. More...
std::set< state_t >	marked_
	List visited vertices. More...
std::unordered_map< state_t, std::size_t >	low_
	low_[s] is minimum of vertex that it can go More...
std::stack< state_t >	stack_
	Contains list vertices same the component. More...

Detailed Description

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

Use Tarjan's algorithm to find all strongly connected components.

Definition at line 33 of file scc.hh.

Member Typedef Documentation

template<typename Aut>

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

Definition at line 37 of file scc.hh.

template<typename Aut>

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

Definition at line 38 of file scc.hh.

template<typename Aut>

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

Definition at line 36 of file scc.hh.

Constructor & Destructor Documentation

template<typename Aut>

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

inline

Definition at line 40 of file scc.hh.

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

Here is the call graph for this function:

Member Function Documentation

template<typename Aut>

const components_t vcsn::detail::scc_tarjan_impl< Aut >::components ( )

inline

Definition at line 47 of file scc.hh.

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

Referenced by vcsn::scc().

template<typename Aut>

void vcsn::detail::scc_tarjan_impl< Aut >::dfs ( state_t  s, const Aut &  aut  )

inlineprivate

Definition at line 53 of file scc.hh.

References vcsn::detail::scc_tarjan_impl< Aut >::components_, vcsn::detail::scc_tarjan_impl< Aut >::curr_comp_num_, vcsn::detail::scc_tarjan_impl< Aut >::curr_vertex_num_, vcsn::has(), vcsn::detail::scc_tarjan_impl< Aut >::low_, vcsn::detail::scc_tarjan_impl< Aut >::marked_, and vcsn::detail::scc_tarjan_impl< Aut >::stack_.

Referenced by vcsn::detail::scc_tarjan_impl< Aut >::scc_tarjan_impl().

Here is the call graph for this function:

Member Data Documentation

template<typename Aut>

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

private

All compnents.

Definition at line 94 of file scc.hh.

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

template<typename Aut>

std::size_t vcsn::detail::scc_tarjan_impl< Aut >::curr_comp_num_ = 0

private

The current component number.

Definition at line 90 of file scc.hh.

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

template<typename Aut>

std::size_t vcsn::detail::scc_tarjan_impl< Aut >::curr_vertex_num_ = 0

private

The current visited vertex.

Definition at line 92 of file scc.hh.

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

template<typename Aut>

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

private

low_[s] is minimum of vertex that it can go

Definition at line 98 of file scc.hh.

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

template<typename Aut>

std::set<state_t> vcsn::detail::scc_tarjan_impl< Aut >::marked_

private

List visited vertices.

Definition at line 96 of file scc.hh.

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

template<typename Aut>

std::stack<state_t> vcsn::detail::scc_tarjan_impl< Aut >::stack_

private

Contains list vertices same the component.

Definition at line 100 of file scc.hh.

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

---

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

• vcsn/algos/scc.hh