scc.hh File Reference

#include <iterator>
#include <limits>
#include <stack>
#include <boost/range/rbegin.hpp>
#include <boost/range/rend.hpp>
#include <vcsn/algos/copy.hh>
#include <vcsn/algos/filter.hh>
#include <vcsn/algos/transpose.hh>
#include <vcsn/core/partition-automaton.hh>
#include <vcsn/dyn/automaton.hh>
#include <vcsn/dyn/fwd.hh>
#include <vcsn/misc/builtins.hh>
#include <vcsn/misc/unordered_map.hh>
#include <vcsn/misc/unordered_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::reverse_postorder_impl< Aut >
	Get all states in reverse postorder using depth first search. More...
class	vcsn::detail::scc_dijkstra_impl< Aut >
	Compute the strongly connected components using Dijkstra's algorithm. More...
class	vcsn::detail::scc_kosaraju_impl< Aut >
	Compute the strongly connected components using Kosaraju's algorithm. More...
class	vcsn::detail::scc_tarjan_iterative_impl< Aut >
	Tarjan's algorithm to find all strongly connected components: iterative implementation. More...
struct	vcsn::detail::scc_tarjan_iterative_impl< Aut >::step_t
	Step of one state contain infomation next successor and end iterator(output transitions or successors of this state). More...
class	vcsn::detail::scc_tarjan_recursive_impl< Aut >
	Tarjan's algorithm to find all strongly connected components: recursive implementation. More...
class	vcsn::detail::scc_automaton_impl< Aut >
	An automaton decorator that maps states to their scc-number. More...

Namespaces
	vcsn
	vcsn::detail
	vcsn::dyn
	vcsn::dyn::detail

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

Enumerations
enum	vcsn::scc_algo_t { vcsn::scc_algo_t::dijkstra, vcsn::scc_algo_t::tarjan_iterative, vcsn::scc_algo_t::tarjan_recursive, vcsn::scc_algo_t::kosaraju }

Functions
template<typename Aut >
std::vector< state_t_of< Aut > >	vcsn::reverse_postorder (const Aut &aut)
	Get all states in reverse postorder. More...
scc_algo_t	vcsn::scc_algo (const std::string &algo)
template<typename Aut >
const detail::components_t< Aut >	vcsn::strong_components (const Aut &aut, scc_algo_t algo=scc_algo_t::tarjan_iterative)
	Find all strongly connected components of aut. More...
template<typename Aut >
fresh_automaton_t_of< Aut >	vcsn::aut_of_component (const detail::component_t< Aut > &com, const Aut &aut)
	Generate a subautomaton corresponding to an SCC. More...
template<typename Aut >
scc_automaton< Aut >	vcsn::scc (const Aut &aut, const std::string &algo="auto")
	Get scc_automaton from aut. More...
template<typename Aut , typename String >
automaton	vcsn::dyn::detail::scc (const automaton &aut, const std::string &algo)
	Bridge. More...
template<typename Aut >
std::size_t	vcsn::num_components (const scc_automaton< Aut > &aut)
	Get number of strongly connected components. More...
template<typename Aut >
std::size_t	vcsn::num_components (const Aut &)
template<typename Aut >
std::size_t	vcsn::dyn::detail::num_components (const automaton &aut)
	Bridge. More...
template<typename Aut >
filter_automaton< scc_automaton< Aut > >	vcsn::component (const scc_automaton< Aut > &aut, unsigned num)
	An SCC as a subautomaton. More...
template<typename Aut >
void	vcsn::component (const Aut &, unsigned)
template<typename Aut , typename Unsigned >
automaton	vcsn::dyn::detail::component (const automaton &aut, unsigned num)
	Bridge. More...
template<typename Aut >
partition_automaton< scc_automaton< Aut > >	vcsn::condense (const scc_automaton< Aut > &aut)
	Create a condensation of automaton with each its state who is a strongly connected component of aut. More...
template<typename Aut >
partition_automaton< Aut >	vcsn::condense (const Aut &)
template<typename Aut >
automaton	vcsn::dyn::detail::condense (const automaton &aut)
	Bridge. More...