Vcsn  2.3a
Be Rational
vcsn::detail::scc_impl< Aut, dijkstra_tag > Class Template Reference

Compute the strongly connected components using Dijkstra's algorithm. More...

#include <scc.hh>

Collaboration diagram for vcsn::detail::scc_impl< Aut, dijkstra_tag >:

Public Types

using state_t = state_t_of< Aut >
 
using component_t = detail::component_t< Aut >
 
using components_t = detail::components_t< Aut >
 

Public Member Functions

 scc_impl (const Aut &aut)
 
const components_tcomponents ()
 

Private Member Functions

void dfs (state_t s)
 

Private Attributes

Aut aut_
 Input automaton. More...
 
std::stack< state_tunassigned_
 Stack S contains all the vertices that have not yet been assigned to a strongly connected component, in the order in which the depth-first search reaches the vertices. More...
 
std::stack< state_tuncertain_
 Stack P contains vertices that have not yet been determined to belong to different strongly connected components from each other. More...
 
std::size_t count_ = 0
 Current state number (not it's id, but its count). More...
 
std::unordered_map< state_t, size_t > component_
 For each state, its component number. More...
 
std::unordered_map< state_t, size_t > preorder_
 
components_t components_
 All the components. More...
 

Detailed Description

template<Automaton Aut>
class vcsn::detail::scc_impl< Aut, dijkstra_tag >

Compute the strongly connected components using Dijkstra's algorithm.

https://en.wikipedia.org/wiki/Path-based_strong_component_algorithm

Definition at line 123 of file scc.hh.

Member Typedef Documentation

template<Automaton Aut>
using vcsn::detail::scc_impl< Aut, dijkstra_tag >::component_t = detail::component_t<Aut>

Definition at line 127 of file scc.hh.

template<Automaton Aut>
using vcsn::detail::scc_impl< Aut, dijkstra_tag >::components_t = detail::components_t<Aut>

Definition at line 128 of file scc.hh.

template<Automaton Aut>
using vcsn::detail::scc_impl< Aut, dijkstra_tag >::state_t = state_t_of<Aut>

Definition at line 126 of file scc.hh.

Constructor & Destructor Documentation

template<Automaton Aut>
vcsn::detail::scc_impl< Aut, dijkstra_tag >::scc_impl ( const Aut &  aut)
inline

Definition at line 130 of file scc.hh.

Member Function Documentation

template<Automaton Aut>
const components_t& vcsn::detail::scc_impl< Aut, dijkstra_tag >::components ( )
inline

Definition at line 134 of file scc.hh.

References vcsn::has().

Here is the call graph for this function:

template<Automaton Aut>
void vcsn::detail::scc_impl< Aut, dijkstra_tag >::dfs ( state_t  s)
inlineprivate

Definition at line 143 of file scc.hh.

References vcsn::has(), vcsn::detail::out(), and vcsn::scc().

Here is the call graph for this function:

Member Data Documentation

template<Automaton Aut>
Aut vcsn::detail::scc_impl< Aut, dijkstra_tag >::aut_
private

Input automaton.

Definition at line 180 of file scc.hh.

template<Automaton Aut>
std::unordered_map<state_t, size_t> vcsn::detail::scc_impl< Aut, dijkstra_tag >::component_
private

For each state, its component number.

Definition at line 193 of file scc.hh.

template<Automaton Aut>
components_t vcsn::detail::scc_impl< Aut, dijkstra_tag >::components_
private

All the components.

Definition at line 197 of file scc.hh.

template<Automaton Aut>
std::size_t vcsn::detail::scc_impl< Aut, dijkstra_tag >::count_ = 0
private

Current state number (not it's id, but its count).

Definition at line 190 of file scc.hh.

template<Automaton Aut>
std::unordered_map<state_t, size_t> vcsn::detail::scc_impl< Aut, dijkstra_tag >::preorder_
private

Definition at line 195 of file scc.hh.

template<Automaton Aut>
std::stack<state_t> vcsn::detail::scc_impl< Aut, dijkstra_tag >::unassigned_
private

Stack S contains all the vertices that have not yet been assigned to a strongly connected component, in the order in which the depth-first search reaches the vertices.

Definition at line 184 of file scc.hh.

template<Automaton Aut>
std::stack<state_t> vcsn::detail::scc_impl< Aut, dijkstra_tag >::uncertain_
private

Stack P contains vertices that have not yet been determined to belong to different strongly connected components from each other.

Definition at line 188 of file scc.hh.


The documentation for this class was generated from the following file: