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_t &	ws_ = *aut_->weightset()
const polynomialset_t	ps_ = make_word_polynomialset(aut_->context())
const labelset_t &	ls_ = *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 37 of file lightest.hh.

Member Typedef Documentation

template<Automaton Aut>

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

Definition at line 40 of file lightest.hh.

template<Automaton Aut>

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

Definition at line 41 of file lightest.hh.

template<Automaton Aut>

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

Wordset.

Definition at line 49 of file lightest.hh.

template<Automaton Aut>

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

Definition at line 46 of file lightest.hh.

template<Automaton Aut>

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

Definition at line 45 of file lightest.hh.

template<Automaton Aut>

using vcsn::detail::lightest_impl< Aut >::polynomialset_t = polynomialset<wordset_context_t>

Definition at line 44 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 56 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 89 of file lightest.hh.

template<Automaton Aut>

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

Definition at line 54 of file lightest.hh.

template<Automaton Aut>

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

Definition at line 53 of file lightest.hh.

template<Automaton Aut>

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

Definition at line 52 of file lightest.hh.

template<Automaton Aut>

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

Definition at line 50 of file lightest.hh.

template<Automaton Aut>

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

Definition at line 43 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

aut	the automaton to approximate

Definition at line 94 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 108 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_, vcsn::res, 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

num	number of words looked for.

Definition at line 100 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

Show the heap, for debugging.

Definition at line 160 of file lightest.hh.

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

Member Data Documentation

template<Automaton Aut>

automaton_t vcsn::detail::lightest_impl< Aut >::aut_

private

The automaton whose behavior to approximate.

Definition at line 177 of file lightest.hh.

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

template<Automaton Aut>

const labelset_t& vcsn::detail::lightest_impl< Aut >::ls_ = *ps_.labelset()

private

Definition at line 180 of file lightest.hh.

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

template<Automaton Aut>

const polynomialset_t vcsn::detail::lightest_impl< Aut >::ps_ = make_word_polynomialset(aut_->context())

private

Definition at line 179 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

Definition at line 178 of file lightest.hh.

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

---

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

• vcsn/algos/lightest.hh