vcsn::detail::scc_dijkstra_impl< Aut > Class Template Reference

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

#include <scc.hh>

Collaboration diagram for vcsn::detail::scc_dijkstra_impl< Aut >:

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_dijkstra_impl (const Aut &aut)
const components_t &	components ()

Private Member Functions
void	dfs (state_t s)

Private Attributes
Aut	aut_
	Input automaton. More...
std::stack< state_t >	unassigned_
	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_t >	uncertain_
	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<typename Aut>
class vcsn::detail::scc_dijkstra_impl< Aut >

Compute the strongly connected components using Dijkstra's algorithm.

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

Definition at line 114 of file scc.hh.

Member Typedef Documentation

template<typename Aut >

using vcsn::detail::scc_dijkstra_impl< Aut >::component_t = detail::component_t<Aut>

Definition at line 118 of file scc.hh.

template<typename Aut >

using vcsn::detail::scc_dijkstra_impl< Aut >::components_t = detail::components_t<Aut>

Definition at line 119 of file scc.hh.

template<typename Aut >

using vcsn::detail::scc_dijkstra_impl< Aut >::state_t = state_t_of<Aut>

Definition at line 117 of file scc.hh.

Constructor & Destructor Documentation

template<typename Aut >

vcsn::detail::scc_dijkstra_impl< Aut >::scc_dijkstra_impl ( const Aut &  aut )

inline

Definition at line 121 of file scc.hh.

Member Function Documentation

template<typename Aut >

const components_t& vcsn::detail::scc_dijkstra_impl< Aut >::components ( )

inline

Definition at line 125 of file scc.hh.

References vcsn::detail::scc_dijkstra_impl< Aut >::aut_, vcsn::detail::scc_dijkstra_impl< Aut >::component_, vcsn::detail::scc_dijkstra_impl< Aut >::components_, vcsn::detail::scc_dijkstra_impl< Aut >::dfs(), and vcsn::has().

Referenced by vcsn::strong_components().

Here is the call graph for this function:

template<typename Aut >

void vcsn::detail::scc_dijkstra_impl< Aut >::dfs ( state_t  s )

inlineprivate

Definition at line 134 of file scc.hh.

References vcsn::detail::scc_dijkstra_impl< Aut >::aut_, vcsn::detail::scc_dijkstra_impl< Aut >::component_, vcsn::detail::scc_dijkstra_impl< Aut >::components_, vcsn::detail::scc_dijkstra_impl< Aut >::count_, vcsn::has(), vcsn::detail::scc_dijkstra_impl< Aut >::preorder_, vcsn::scc(), vcsn::detail::scc_dijkstra_impl< Aut >::unassigned_, and vcsn::detail::scc_dijkstra_impl< Aut >::uncertain_.

Referenced by vcsn::detail::scc_dijkstra_impl< Aut >::components().

Here is the call graph for this function:

Member Data Documentation

template<typename Aut >

Aut vcsn::detail::scc_dijkstra_impl< Aut >::aut_

private

Input automaton.

Definition at line 171 of file scc.hh.

Referenced by vcsn::detail::scc_dijkstra_impl< Aut >::components(), and vcsn::detail::scc_dijkstra_impl< Aut >::dfs().

template<typename Aut >

std::unordered_map<state_t, size_t> vcsn::detail::scc_dijkstra_impl< Aut >::component_

private

For each state, its component number.

Definition at line 184 of file scc.hh.

Referenced by vcsn::detail::scc_dijkstra_impl< Aut >::components(), and vcsn::detail::scc_dijkstra_impl< Aut >::dfs().

template<typename Aut >

components_t vcsn::detail::scc_dijkstra_impl< Aut >::components_

private

All the components.

Definition at line 188 of file scc.hh.

Referenced by vcsn::detail::scc_dijkstra_impl< Aut >::components(), and vcsn::detail::scc_dijkstra_impl< Aut >::dfs().

template<typename Aut >

std::size_t vcsn::detail::scc_dijkstra_impl< Aut >::count_ = 0

private

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

Definition at line 181 of file scc.hh.

Referenced by vcsn::detail::scc_dijkstra_impl< Aut >::dfs().

template<typename Aut >

std::unordered_map<state_t, size_t> vcsn::detail::scc_dijkstra_impl< Aut >::preorder_

private

Definition at line 186 of file scc.hh.

Referenced by vcsn::detail::scc_dijkstra_impl< Aut >::dfs().

template<typename Aut >

std::stack<state_t> vcsn::detail::scc_dijkstra_impl< Aut >::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 175 of file scc.hh.

Referenced by vcsn::detail::scc_dijkstra_impl< Aut >::dfs().

template<typename Aut >

std::stack<state_t> vcsn::detail::scc_dijkstra_impl< Aut >::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 179 of file scc.hh.

Referenced by vcsn::detail::scc_dijkstra_impl< Aut >::dfs().

---

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

• vcsn/algos/scc.hh