Vcsn  2.5.dev
Be Rational
Classes | Public Types | Public Member Functions | Public Attributes | List of all members
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 = vcsn::min_fibonacci_heap< profile >
 

Public Member Functions

 dijkstra_impl (const Aut &aut, const ValueSet &vs, Mul mul)
 
predecessors_t_of< automaton_t > operator() (state_t source, state_t dest)
 

Public Attributes

const automaton_t & aut_
 
predecessors_t_of< automaton_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
ValueSetcould be either a labelset or weightset. Must have a less and a one member function.
Mullambda multiplying the current best candidate with the value taken from the transition given in parameter.

Definition at line 30 of file dijkstra.hh.

Member Typedef Documentation

◆ automaton_t

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

Definition at line 32 of file dijkstra.hh.

◆ context_t

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 39 of file dijkstra.hh.

◆ distance_t

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

Definition at line 43 of file dijkstra.hh.

◆ heap_t

template<Automaton Aut, typename ValueSet, typename Mul>
using vcsn::detail::dijkstra_impl< Aut, ValueSet, Mul >::heap_t = vcsn::min_fibonacci_heap<profile>

Definition at line 74 of file dijkstra.hh.

◆ label_t

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 36 of file dijkstra.hh.

◆ self_t

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

Definition at line 33 of file dijkstra.hh.

◆ state_t

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 34 of file dijkstra.hh.

◆ transition_t

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 35 of file dijkstra.hh.

◆ value_t

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 42 of file dijkstra.hh.

◆ valueset_t

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

Definition at line 41 of file dijkstra.hh.

◆ weight_t

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 37 of file dijkstra.hh.

◆ weightset_t

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 38 of file dijkstra.hh.

◆ wordset_context_t

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 40 of file dijkstra.hh.

Constructor & Destructor Documentation

◆ dijkstra_impl()

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 45 of file dijkstra.hh.

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

Member Function Documentation

◆ operator()()

template<Automaton Aut, typename ValueSet, typename Mul>
predecessors_t_of<automaton_t> vcsn::detail::dijkstra_impl< Aut, ValueSet, Mul >::operator() ( state_t  source,
state_t  dest 
)
inline

Definition at line 77 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(), vcsn::detail::states_size(), and vcsn::detail::dijkstra_impl< Aut, ValueSet, Mul >::vs_.

Here is the call graph for this function:

Member Data Documentation

◆ aut_

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

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<().

◆ dist_

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

Definition at line 125 of file dijkstra.hh.

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

◆ mul_

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

Definition at line 127 of file dijkstra.hh.

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

◆ res_

template<Automaton Aut, typename ValueSet, typename Mul>
predecessors_t_of<automaton_t> vcsn::detail::dijkstra_impl< Aut, ValueSet, Mul >::res_

For each state, its predecessor.

Definition at line 124 of file dijkstra.hh.

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

◆ vs_

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

Definition at line 126 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: