Vcsn  2.1
Be Rational
Classes | Public Types | Public Member Functions | Private Member Functions | Private Attributes | List of all members
vcsn::detail::weighter< 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::weighter< Aut >:

Classes

struct  datum_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 datum_t = std::tuple< state_t, word_t, weight_t >
 
using queue_t = boost::heap::binomial_heap< datum_t, boost::heap::compare< datum_less >>
 

Public Member Functions

 weighter (const automaton_t &aut)
 Prepare to compute an approximation of the behavior. More...
 
polynomial_t operator() (boost::optional< 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_t & ws_ = *aut_->weightset()
 
const polynomialset_t ps_ = make_word_polynomialset(aut_->context())
 
const labelset_t & ls_ = *ps_.labelset()
 

Detailed Description

template<typename Aut>
class vcsn::detail::weighter< 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 35 of file lightest.hh.

Member Typedef Documentation

template<typename Aut>
using vcsn::detail::weighter< Aut >::automaton_t = Aut

Definition at line 38 of file lightest.hh.

template<typename Aut>
using vcsn::detail::weighter< Aut >::context_t = context_t_of<Aut>

Definition at line 39 of file lightest.hh.

template<typename Aut>
using vcsn::detail::weighter< Aut >::datum_t = std::tuple<state_t, word_t, weight_t>

Definition at line 54 of file lightest.hh.

template<typename Aut>
using vcsn::detail::weighter< Aut >::labelset_t = labelset_t_of<polynomialset_t>

Wordset.

Definition at line 47 of file lightest.hh.

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

Definition at line 44 of file lightest.hh.

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

Definition at line 43 of file lightest.hh.

template<typename Aut>
using vcsn::detail::weighter< Aut >::polynomialset_t = polynomialset<wordset_context_t>

Definition at line 42 of file lightest.hh.

template<typename Aut>
using vcsn::detail::weighter< Aut >::queue_t = boost::heap::binomial_heap<datum_t, boost::heap::compare<datum_less>>

Definition at line 74 of file lightest.hh.

template<typename Aut>
using vcsn::detail::weighter< Aut >::state_t = state_t_of<automaton_t>

Definition at line 52 of file lightest.hh.

template<typename Aut>
using vcsn::detail::weighter< Aut >::weight_t = weight_t_of<automaton_t>

Definition at line 51 of file lightest.hh.

template<typename Aut>
using vcsn::detail::weighter< Aut >::weightset_t = weightset_t_of<automaton_t>

Definition at line 50 of file lightest.hh.

template<typename Aut>
using vcsn::detail::weighter< Aut >::word_t = word_t_of<automaton_t>

Definition at line 48 of file lightest.hh.

template<typename Aut>
using vcsn::detail::weighter< Aut >::wordset_context_t = word_context_t<context_t>

Definition at line 41 of file lightest.hh.

Constructor & Destructor Documentation

template<typename Aut>
vcsn::detail::weighter< Aut >::weighter ( const automaton_t &  aut)
inline

Prepare to compute an approximation of the behavior.

Parameters
autthe automaton to approximate

Definition at line 79 of file lightest.hh.

Member Function Documentation

template<typename Aut>
polynomial_t vcsn::detail::weighter< Aut >::lightest_ ( unsigned  num)
inlineprivate

Definition at line 94 of file lightest.hh.

References vcsn::detail::weighter< Aut >::aut_, vcsn::detail::weighter< Aut >::ls_, vcsn::detail::weighter< Aut >::ps_, and vcsn::detail::weighter< Aut >::ws_.

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

template<typename Aut>
polynomial_t vcsn::detail::weighter< Aut >::operator() ( boost::optional< unsigned >  num)
inline

The approximated behavior of the automaton.

Parameters
numnumber of words looked for.

Definition at line 85 of file lightest.hh.

References vcsn::detail::weighter< Aut >::lightest_().

Here is the call graph for this function:

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

Show the heap, for debugging.

Definition at line 136 of file lightest.hh.

References vcsn::detail::weighter< Aut >::aut_, vcsn::detail::weighter< Aut >::ls_, os, and vcsn::detail::weighter< Aut >::ws_.

Member Data Documentation

template<typename Aut>
automaton_t vcsn::detail::weighter< Aut >::aut_
private

The automaton whose behavior to approximate.

Definition at line 153 of file lightest.hh.

Referenced by vcsn::detail::weighter< Aut >::lightest_(), and vcsn::detail::weighter< Aut >::show_heap_().

template<typename Aut>
const labelset_t& vcsn::detail::weighter< Aut >::ls_ = *ps_.labelset()
private

Definition at line 156 of file lightest.hh.

Referenced by vcsn::detail::weighter< Aut >::lightest_(), and vcsn::detail::weighter< Aut >::show_heap_().

template<typename Aut>
const polynomialset_t vcsn::detail::weighter< Aut >::ps_ = make_word_polynomialset(aut_->context())
private

Definition at line 155 of file lightest.hh.

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

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

Definition at line 154 of file lightest.hh.

Referenced by vcsn::detail::weighter< Aut >::lightest_(), and vcsn::detail::weighter< Aut >::show_heap_().

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