vcsn::detail::dijkstra_impl< Aut, ValueSet, Mul > Struct Template Reference

Dijkstra implementation of lightest automaton. More...

#include <dijkstra.hh>

Collaboration diagram for vcsn::detail::dijkstra_impl< Aut, ValueSet, Mul >:

Classes
struct	profile

Public Types
using	automaton_t = Aut
using	self_t = dijkstra_impl
using	state_t = state_t_of< automaton_t >
using	transition_t = transition_t_of< automaton_t >
using	label_t = label_t_of< automaton_t >
using	weight_t = weight_t_of< automaton_t >
using	weightset_t = weightset_t_of< automaton_t >
using	context_t = context_t_of< automaton_t >
using	wordset_context_t = word_context_t< context_t >
using	valueset_t = ValueSet
using	value_t = typename valueset_t::value_t
using	distance_t = std::vector< value_t >
using	heap_t = boost::heap::fibonacci_heap< profile >

Public Member Functions
	dijkstra_impl (const Aut &aut, const ValueSet &vs, Mul mul)
std::vector< transition_t >	operator() (state_t source, state_t dest)

Public Attributes
const automaton_t &	aut_
std::vector< transition_t >	res_
	For each state, its predecessor. More...
distance_t	dist_
const ValueSet &	vs_
Mul	mul_

Detailed Description

template<Automaton Aut, typename ValueSet, typename Mul>
struct vcsn::detail::dijkstra_impl< Aut, ValueSet, Mul >

Dijkstra implementation of lightest automaton.

Uses Fibonacci heaps. No preconditions.

Functor taking an automaton as parameter and applying dijkstra algorithm to compute the lightest 'in' transition of each state.

Template Parameters

ValueSet	could be either a labelset or weightset. Must have a less and a one member function.
Mul	lambda multiplying the current best candidate with the value taken from the transition given in parameter.

Definition at line 31 of file dijkstra.hh.

Member Typedef Documentation

template<Automaton Aut, typename ValueSet, typename Mul>

using vcsn::detail::dijkstra_impl< Aut, ValueSet, Mul >::automaton_t = Aut

Definition at line 33 of file dijkstra.hh.

template<Automaton Aut, typename ValueSet, typename Mul>

using vcsn::detail::dijkstra_impl< Aut, ValueSet, Mul >::context_t = context_t_of<automaton_t>

Definition at line 40 of file dijkstra.hh.

template<Automaton Aut, typename ValueSet, typename Mul>

using vcsn::detail::dijkstra_impl< Aut, ValueSet, Mul >::distance_t = std::vector<value_t>

Definition at line 44 of file dijkstra.hh.

template<Automaton Aut, typename ValueSet, typename Mul>

using vcsn::detail::dijkstra_impl< Aut, ValueSet, Mul >::heap_t = boost::heap::fibonacci_heap<profile>

Definition at line 75 of file dijkstra.hh.

template<Automaton Aut, typename ValueSet, typename Mul>

using vcsn::detail::dijkstra_impl< Aut, ValueSet, Mul >::label_t = label_t_of<automaton_t>

Definition at line 37 of file dijkstra.hh.

template<Automaton Aut, typename ValueSet, typename Mul>

using vcsn::detail::dijkstra_impl< Aut, ValueSet, Mul >::self_t = dijkstra_impl

Definition at line 34 of file dijkstra.hh.

template<Automaton Aut, typename ValueSet, typename Mul>

using vcsn::detail::dijkstra_impl< Aut, ValueSet, Mul >::state_t = state_t_of<automaton_t>

Definition at line 35 of file dijkstra.hh.

template<Automaton Aut, typename ValueSet, typename Mul>

using vcsn::detail::dijkstra_impl< Aut, ValueSet, Mul >::transition_t = transition_t_of<automaton_t>

Definition at line 36 of file dijkstra.hh.

template<Automaton Aut, typename ValueSet, typename Mul>

using vcsn::detail::dijkstra_impl< Aut, ValueSet, Mul >::value_t = typename valueset_t::value_t

Definition at line 43 of file dijkstra.hh.

template<Automaton Aut, typename ValueSet, typename Mul>

using vcsn::detail::dijkstra_impl< Aut, ValueSet, Mul >::valueset_t = ValueSet

Definition at line 42 of file dijkstra.hh.

template<Automaton Aut, typename ValueSet, typename Mul>

using vcsn::detail::dijkstra_impl< Aut, ValueSet, Mul >::weight_t = weight_t_of<automaton_t>

Definition at line 38 of file dijkstra.hh.

template<Automaton Aut, typename ValueSet, typename Mul>

using vcsn::detail::dijkstra_impl< Aut, ValueSet, Mul >::weightset_t = weightset_t_of<automaton_t>

Definition at line 39 of file dijkstra.hh.

template<Automaton Aut, typename ValueSet, typename Mul>

using vcsn::detail::dijkstra_impl< Aut, ValueSet, Mul >::wordset_context_t = word_context_t<context_t>

Definition at line 41 of file dijkstra.hh.

Constructor & Destructor Documentation

template<Automaton Aut, typename ValueSet, typename Mul>

vcsn::detail::dijkstra_impl< Aut, ValueSet, Mul >::dijkstra_impl ( const Aut &  aut, const ValueSet &  vs, Mul  mul  )

inline

Definition at line 46 of file dijkstra.hh.

Member Function Documentation

template<Automaton Aut, typename ValueSet, typename Mul>

std::vector<transition_t> vcsn::detail::dijkstra_impl< Aut, ValueSet, Mul >::operator() ( state_t  source, state_t  dest  )

inline

Definition at line 78 of file dijkstra.hh.

References vcsn::detail::all_out(), vcsn::detail::dijkstra_impl< Aut, ValueSet, Mul >::aut_, vcsn::detail::dijkstra_impl< Aut, ValueSet, Mul >::dist_, vcsn::detail::dijkstra_impl< Aut, ValueSet, Mul >::mul_, vcsn::detail::dijkstra_impl< Aut, ValueSet, Mul >::res_, vcsn::rat::size(), and vcsn::detail::dijkstra_impl< Aut, ValueSet, Mul >::vs_.

Here is the call graph for this function:

Member Data Documentation

template<Automaton Aut, typename ValueSet, typename Mul>

const automaton_t& vcsn::detail::dijkstra_impl< Aut, ValueSet, Mul >::aut_

Definition at line 119 of file dijkstra.hh.

Referenced by vcsn::detail::dijkstra_impl< Aut, ValueSet, Mul >::operator()(), and vcsn::detail::dijkstra_impl< Aut, ValueSet, Mul >::profile::operator<().

template<Automaton Aut, typename ValueSet, typename Mul>

distance_t vcsn::detail::dijkstra_impl< Aut, ValueSet, Mul >::dist_

Definition at line 122 of file dijkstra.hh.

Referenced by vcsn::detail::dijkstra_impl< Aut, ValueSet, Mul >::operator()(), and vcsn::detail::dijkstra_impl< Aut, ValueSet, Mul >::profile::operator<().

template<Automaton Aut, typename ValueSet, typename Mul>

Mul vcsn::detail::dijkstra_impl< Aut, ValueSet, Mul >::mul_

Definition at line 124 of file dijkstra.hh.

Referenced by vcsn::detail::dijkstra_impl< Aut, ValueSet, Mul >::operator()().

template<Automaton Aut, typename ValueSet, typename Mul>

std::vector<transition_t> vcsn::detail::dijkstra_impl< Aut, ValueSet, Mul >::res_

For each state, its predecessor.

Definition at line 121 of file dijkstra.hh.

Referenced by vcsn::detail::dijkstra_impl< Aut, ValueSet, Mul >::operator()(), and vcsn::detail::dijkstra_impl< Aut, ValueSet, Mul >::profile::operator<().

template<Automaton Aut, typename ValueSet, typename Mul>

const ValueSet& vcsn::detail::dijkstra_impl< Aut, ValueSet, Mul >::vs_

Definition at line 123 of file dijkstra.hh.

Referenced by vcsn::detail::dijkstra_impl< Aut, ValueSet, Mul >::operator()(), and vcsn::detail::dijkstra_impl< Aut, ValueSet, Mul >::profile::operator<().

---

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

• vcsn/algos/dijkstra.hh