Vcsn  2.2
Be Rational
vcsn::detail::lightest_impl< Aut > Class Template Reference

The lightest algorithm computes the paths between pre and post with the smallest weight possible. More...

#include <lightest.hh>

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

Classes

struct  profile_less
 

Public Types

using automaton_t = Aut
 
using context_t = context_t_of< Aut >
 
using wordset_context_t = word_context_t< context_t >
 
using polynomialset_t = polynomialset< wordset_context_t >
 
using polynomial_t = typename polynomialset_t::value_t
 
using monomial_t = typename polynomialset_t::monomial_t
 
using labelset_t = labelset_t_of< polynomialset_t >
 Wordset. More...
 
using word_t = word_t_of< automaton_t >
 
using weightset_t = weightset_t_of< automaton_t >
 
using weight_t = weight_t_of< automaton_t >
 
using state_t = state_t_of< automaton_t >
 
using profile_t = std::tuple< state_t, word_t, weight_t >
 
using queue_t = boost::heap::binomial_heap< profile_t, boost::heap::compare< profile_less >>
 

Public Member Functions

 lightest_impl (const automaton_t &aut)
 Prepare to compute an approximation of the behavior. More...
 
polynomial_t operator() (unsigned num)
 The approximated behavior of the automaton. More...
 

Private Member Functions

polynomial_t lightest_ (unsigned num)
 
void show_heap_ (const queue_t &q, std::ostream &os=std::cerr)
 Show the heap, for debugging. More...
 

Private Attributes

automaton_t aut_
 The automaton whose behavior to approximate. More...
 
const weightset_tws_ = *aut_->weightset()
 
const polynomialset_t ps_ = make_word_polynomialset(aut_->context())
 
const labelset_tls_ = *ps_.labelset()
 

Detailed Description

template<Automaton Aut>
class vcsn::detail::lightest_impl< Aut >

The lightest algorithm computes the paths between pre and post with the smallest weight possible.

This functor will construct the polynomial composed with each one of the num smallest paths. This implementation uses a priority queue that will order states by their weights (then labels).

Definition at line 38 of file lightest.hh.

Member Typedef Documentation

template<Automaton Aut>
using vcsn::detail::lightest_impl< Aut >::automaton_t = Aut

Definition at line 41 of file lightest.hh.

template<Automaton Aut>
using vcsn::detail::lightest_impl< Aut >::context_t = context_t_of<Aut>

Definition at line 42 of file lightest.hh.

template<Automaton Aut>
using vcsn::detail::lightest_impl< Aut >::labelset_t = labelset_t_of<polynomialset_t>

Wordset.

Definition at line 50 of file lightest.hh.

template<Automaton Aut>
using vcsn::detail::lightest_impl< Aut >::monomial_t = typename polynomialset_t::monomial_t

Definition at line 47 of file lightest.hh.

template<Automaton Aut>
using vcsn::detail::lightest_impl< Aut >::polynomial_t = typename polynomialset_t::value_t

Definition at line 46 of file lightest.hh.

Definition at line 45 of file lightest.hh.

template<Automaton Aut>
using vcsn::detail::lightest_impl< Aut >::profile_t = std::tuple<state_t, word_t, weight_t>

Definition at line 57 of file lightest.hh.

template<Automaton Aut>
using vcsn::detail::lightest_impl< Aut >::queue_t = boost::heap::binomial_heap<profile_t, boost::heap::compare<profile_less>>

Definition at line 90 of file lightest.hh.

template<Automaton Aut>
using vcsn::detail::lightest_impl< Aut >::state_t = state_t_of<automaton_t>

Definition at line 55 of file lightest.hh.

template<Automaton Aut>
using vcsn::detail::lightest_impl< Aut >::weight_t = weight_t_of<automaton_t>

Definition at line 54 of file lightest.hh.

template<Automaton Aut>
using vcsn::detail::lightest_impl< Aut >::weightset_t = weightset_t_of<automaton_t>

Definition at line 53 of file lightest.hh.

template<Automaton Aut>
using vcsn::detail::lightest_impl< Aut >::word_t = word_t_of<automaton_t>

Definition at line 51 of file lightest.hh.

template<Automaton Aut>
using vcsn::detail::lightest_impl< Aut >::wordset_context_t = word_context_t<context_t>

Definition at line 44 of file lightest.hh.

Constructor & Destructor Documentation

template<Automaton Aut>
vcsn::detail::lightest_impl< Aut >::lightest_impl ( const automaton_t aut)
inline

Prepare to compute an approximation of the behavior.

Parameters
autthe automaton to approximate

Definition at line 95 of file lightest.hh.

Member Function Documentation

template<Automaton Aut>
polynomial_t vcsn::detail::lightest_impl< Aut >::lightest_ ( unsigned  num)
inlineprivate

Fuse equivalent cases, which might increase the first element's weight. Hence, restart loop with sorted queue.

Definition at line 109 of file lightest.hh.

References vcsn::detail::all_out(), vcsn::detail::lightest_impl< Aut >::aut_, vcsn::detail::lightest_impl< Aut >::ls_, vcsn::detail::lightest_impl< Aut >::ps_, and vcsn::detail::lightest_impl< Aut >::ws_.

Referenced by vcsn::detail::lightest_impl< Aut >::operator()().

Here is the call graph for this function:

template<Automaton Aut>
polynomial_t vcsn::detail::lightest_impl< Aut >::operator() ( unsigned  num)
inline

The approximated behavior of the automaton.

Parameters
numnumber of words looked for.

Definition at line 101 of file lightest.hh.

References vcsn::detail::lightest_impl< Aut >::aut_, vcsn::has_lightening_cycle(), vcsn::detail::lightest_impl< Aut >::lightest_(), and vcsn::require().

Here is the call graph for this function:

template<Automaton Aut>
void vcsn::detail::lightest_impl< Aut >::show_heap_ ( const queue_t q,
std::ostream &  os = std::cerr 
)
inlineprivate

Member Data Documentation

template<Automaton Aut>
automaton_t vcsn::detail::lightest_impl< Aut >::aut_
private
template<Automaton Aut>
const labelset_t& vcsn::detail::lightest_impl< Aut >::ls_ = *ps_.labelset()
private
template<Automaton Aut>
const polynomialset_t vcsn::detail::lightest_impl< Aut >::ps_ = make_word_polynomialset(aut_->context())
private

Definition at line 180 of file lightest.hh.

Referenced by vcsn::detail::lightest_impl< Aut >::lightest_().

template<Automaton Aut>
const weightset_t& vcsn::detail::lightest_impl< Aut >::ws_ = *aut_->weightset()
private

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