![]() |
Vcsn
2.2
Be Rational
|
#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>
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... | |