7 #include <boost/heap/binomial_heap.hpp>
8 #include <boost/optional.hpp>
25 template <
typename Aut>
45 using datum_t = std::tuple<state_t, word_t, weight_t>;
51 if (labelset_t::less(std::get<1>(l), std::get<1>(r)))
53 else if (labelset_t::less(std::get<1>(r), std::get<1>(l)))
56 return std::get<0>(l) < std::get<0>(r);
71 boost::optional<unsigned> len)
74 num = !len ? 1 : std::numeric_limits<unsigned>::max();
76 len = std::numeric_limits<unsigned>::max();
91 template <
typename LabelSet = labelset_t_of<context_t>>
97 if (len != std::numeric_limits<unsigned>::max())
100 using queue_t = std::deque<datum_t>;
106 !queue.empty() && i < len && output.size() < num;
110 for (
const auto& sm: queue)
113 std::tie(s, l, w) = sm;
114 for (
const auto t:
aut_->all_out(s))
116 auto dst =
aut_->dst_of(t);
117 auto nw =
ws_.mul(w,
aut_->weight_of(t));
119 q2.emplace_back(dst, l, std::move(nw));
120 else if (dst ==
aut_->post())
121 ps_.add_here(output, l, std::move(nw));
132 for (
const auto& m: output)
134 ps_.add_here(res, m);
145 template <
typename LabelSet = labelset_t_of<context_t>>
152 boost::heap::binomial_heap<
datum_t,
153 boost::heap::compare<datum_less>>;
155 auto queue = queue_t{};
156 queue.emplace(
aut_->pre(),
ls_.one(),
ws_.one());
160 while (!queue.empty())
163 std::tie(s, l, w) = queue.top();
175 while (!queue.empty()
176 && std::get<0>(queue.top()) == s
177 &&
ls_.equal(std::get<1>(queue.top()), l))
179 w =
ws_.add(w, std::get<2>(queue.top()));
183 for (
const auto t:
aut_->all_out(s))
185 auto dst =
aut_->dst_of(t);
186 auto nw =
ws_.mul(w,
aut_->weight_of(t));
188 queue.emplace(dst, l, std::move(nw));
189 else if (dst ==
aut_->post())
190 ps_.add_here(res, l, std::move(nw));
193 auto nl =
ls_.mul(l,
aut_->label_of(t));
195 if (
ls_.size(nl) <= len)
196 queue.emplace(dst, std::move(nl), std::move(nw));
204 || (num == res.size()
205 && !
ls_.equal(std::get<1>(queue.top()), l)))
214 template <
typename Queue>
217 const char* sep =
"";
218 for (
auto i = q.ordered_begin(), end = q.ordered_end();
223 aut_->print_state_name(std::get<0>(*i),
os) <<
":<";
224 ws_.print(std::get<2>(*i),
os) <<
'>';
225 ls_.print(std::get<1>(*i),
os);
243 template <
typename Automaton>
247 boost::optional<unsigned> num = {},
248 boost::optional<unsigned> len = {})
250 detail::enumerater<Automaton> enumerater(aut);
251 return enumerater(num, len);
259 template <
typename Automaton>
261 typename detail::enumerater<Automaton>::polynomial_t
264 return shortest(aut, boost::none, len);
273 template <
typename Aut,
typename Num,
typename Len>
276 boost::optional<unsigned> num,
277 boost::optional<unsigned> len)
279 const auto& a = aut->as<Aut>();
bool operator()(const datum_t &r, const datum_t &l) const
Whether l < r (as this is a max heap).
state_t_of< automaton_t > state_t
polynomial shortest(const automaton &aut, boost::optional< unsigned > num, boost::optional< unsigned > len)
Bridge.
labelset_t_of< polynomialset_t > labelset_t
Wordset.
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
typename detail::context_t_of_impl< base_t< ValueSet >>::type context_t_of
auto shortest_(unsigned num, unsigned len) -> enable_if_t< LabelSet::is_free(), polynomial_t >
Case of free labelsets (e.g., lal or lal x lal).
detail::enumerater< Automaton >::polynomial_t shortest(const Automaton &aut, boost::optional< unsigned > num={}, boost::optional< unsigned > len={})
The approximated behavior of an automaton.
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
typename std::enable_if< Cond, T >::type enable_if_t
automaton_t aut_
The automaton whose behavior to approximate.
typename polynomialset_t::value_t polynomial_t
word_t_of< automaton_t > word_t
std::tuple< state_t, word_t, weight_t > datum_t
Used in the case of non-free labelsets.
typename labelset_t_of< base_t< ValueSet >>::word_t word_t_of
polynomial make_polynomial(const PolynomialSet &ps, const typename PolynomialSet::value_t &p)
weight_t_of< automaton_t > weight_t
Provide a variadic mul on top of a binary mul(), and one().
auto make_word_polynomialset(const Ctx &ctx) -> word_polynomialset_t< Ctx >
The polynomialset of words of a labelset (not necessarily on words itself).
std::shared_ptr< detail::automaton_base > automaton
weightset_t_of< automaton_t > weightset_t
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
std::ostringstream os
The output stream: the corresponding C++ snippet to compile.
enumerater(const automaton_t &aut)
Prepare to compute an approximation of the behavior.
const polynomialset_t ps_
detail::enumerater< Automaton >::polynomial_t enumerate(const Automaton &aut, unsigned len)
The approximated behavior of an automaton.
context_t_of< Aut > context_t
std::shared_ptr< const detail::polynomial_base > polynomial
auto shortest_(unsigned num, unsigned len) -> enable_if_t<!LabelSet::is_free(), polynomial_t >
Case of non free labelsets (e.g., law, lan x lan).
void show_heap_(const Queue &q, std::ostream &os=std::cerr) const
Show the heap, for debugging.
polynomial_t operator()(boost::optional< unsigned > num, boost::optional< unsigned > len)
The approximated behavior of the automaton.
typename detail::weight_t_of_impl< base_t< ValueSet >>::type weight_t_of