Vcsn  2.3
Be Rational
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...