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/tags.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/getargs.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_impl< Aut, Tag >
	Class template for strongly-connected-components computations. More...
class	vcsn::detail::scc_impl< Aut, dijkstra_tag >
	Compute the strongly connected components using Dijkstra's algorithm. More...
struct	vcsn::kosaraju_tag
	Request the Kosaraju's algorithm to compute the SCCs. More...
class	vcsn::detail::scc_impl< Aut, kosaraju_tag >
	Compute the strongly connected components using Kosaraju's algorithm. More...
struct	vcsn::tarjan_iterative_tag
	Request the Tarjan's algorithm to compute the SCCs, implemented with explicit stack handling. More...
class	vcsn::detail::scc_impl< Aut, tarjan_iterative_tag >
	Tarjan's algorithm to find all strongly connected components: iterative implementation. More...
struct	vcsn::detail::scc_impl< Aut, tarjan_iterative_tag >::step_t
	Step of one state contain infomation next successor and end iterator(output transitions or successors of this state). More...
struct	vcsn::tarjan_recursive_tag
	Request the Tarjan's algorithm to compute the SCCs, implemented with recursion. More...
class	vcsn::detail::scc_impl< Aut, tarjan_recursive_tag >
	Tarjan's algorithm to find all strongly connected components: recursive implementation. More...
class	vcsn::detail::scc_impl< Aut, auto_tag >
	By default, use Tarjan iterative. 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<Automaton Aut>
using	vcsn::detail::component_t = std::unordered_set< state_t_of< Aut >>
	A strongly-connected component: set of states. More...
template<Automaton Aut>
using	vcsn::detail::components_t = std::vector< component_t< Aut >>
	A set of strongly-connected components. More...
template<Automaton Aut>
using	vcsn::scc_automaton = std::shared_ptr< detail::scc_automaton_impl< Aut >>

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

Functions
template<Automaton 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<Automaton Aut, typename Tag = auto_tag>
const detail::components_t< Aut >	vcsn::strong_components (const Aut &aut, Tag={})
	Find all strongly connected components of aut. More...
template<Automaton 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<Automaton 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<Automaton Aut>
scc_automaton< Aut >	vcsn::scc (const Aut &aut, const std::string &algo="auto")
	Get scc_automaton from aut. More...
template<Automaton Aut, typename String >
automaton	vcsn::dyn::detail::scc (const automaton &aut, const std::string &algo)
	Bridge. More...
template<Automaton Aut>
std::size_t	vcsn::num_components (const scc_automaton< Aut > &aut)
	Get number of strongly connected components. More...
template<Automaton Aut>
std::size_t	vcsn::num_components (const Aut &)
template<Automaton Aut>
std::size_t	vcsn::dyn::detail::num_components (const automaton &aut)
	Bridge. More...
template<Automaton Aut>
filter_automaton< scc_automaton< Aut > >	vcsn::component (const scc_automaton< Aut > &aut, unsigned num)
	An SCC as a subautomaton. More...
template<Automaton Aut>
void	vcsn::component (const Aut &, unsigned)
template<Automaton Aut, typename Unsigned >
automaton	vcsn::dyn::detail::component (const automaton &aut, unsigned num)
	Bridge. More...
template<Automaton 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<Automaton Aut>
partition_automaton< Aut >	vcsn::condense (const Aut &)
template<Automaton Aut>
automaton	vcsn::dyn::detail::condense (const automaton &aut)
	Bridge. More...