scc.hh File Reference

#include <stack>
#include <vcsn/dyn/automaton.hh>
#include <vcsn/dyn/fwd.hh>
#include <vcsn/algos/transpose.hh>
#include <vcsn/misc/builtins.hh>
#include <vcsn/misc/unordered_map.hh>
#include <vcsn/misc/set.hh>
#include <vcsn/misc/vector.hh>

Include dependency graph for scc.hh:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	vcsn::detail::scc_tarjan_impl< Aut >
	Use Tarjan's algorithm to find all strongly connected components. More...
class	vcsn::detail::reverse_postorder_impl< Aut >
	Get all vertices in reverse postorder by using depth first search. More...
class	vcsn::detail::scc_kosaraju_impl< Aut >
	Use Kosajaju algorithm for finding all of strongly connected components. More...

Namespaces
	vcsn
	vcsn::detail
	vcsn::dyn
	FIXME: duplicate code with determinize.
	vcsn::dyn::detail

Typedefs
template<typename Aut >
using	vcsn::detail::component_t = std::set< state_t_of< Aut >>
	An strongly-connected component: list of states. More...
template<typename Aut >
using	vcsn::detail::components_t = std::vector< component_t< Aut >>
	A set of strongly-connected components. More...

Enumerations
enum	vcsn::SCC_ALGO { vcsn::SCC_ALGO::TARJAN = 0, vcsn::SCC_ALGO::KOSARAJU = 1 }

Functions
template<typename Aut >
std::stack< state_t_of< Aut > >	vcsn::reverse_postorder (const Aut &aut)
	Get all vertices in reverse postorder. More...
template<typename Aut >
const detail::components_t< Aut >	vcsn::scc (const Aut &aut, SCC_ALGO algo=SCC_ALGO::TARJAN)
	Find all strongly connected components of aut. More...
template<typename Aut >
Aut::element_type::automaton_nocv_t	vcsn::aut_of_component (const detail::component_t< Aut > &com, const Aut &aut)
	Generate a subautomaton corresponding to an SCC. More...
template<typename Aut >
std::size_t	vcsn::num_sccs (const Aut &aut)
	Get number of strongly connected components. More...
template<typename Aut >
std::size_t	vcsn::dyn::detail::num_sccs (const automaton &aut)
	vcsn::dyn::detail::REGISTER_DECLARE (num_sccs,(const automaton &) -> std::size_t)