14 template <Automaton Aut,
typename Tag = auto_tag>
15 std::vector<transition_t_of<Aut>>
21 template <Automaton Aut>
22 std::vector<transition_t_of<Aut>>
26 if (weightset_t_of<Aut>::has_lightening_weights())
35 template <Automaton Aut,
typename Tag>
36 std::vector<transition_t_of<Aut>>
45 template <Automaton Aut>
46 std::vector<transition_t_of<Aut>>
48 const std::string& algo)
51 using path_t = std::vector<transition_t_of<Aut>>;
55 "lightest-path algorithm",
57 {
"auto", detail::lightest_path_tag<Aut, auto_tag>},
58 {
"a-star", detail::lightest_path_tag<Aut, a_star_tag>},
59 {
"bellman-ford", detail::lightest_path_tag<Aut, bellman_ford_tag>},
60 {
"dijkstra", detail::lightest_path_tag<Aut, dijkstra_tag>},
63 return map[algo](aut, src, dst);
70 template <Automaton Aut>
76 -> boost::optional<typename detail::word_polynomialset_t<context_t_of<Aut>>::monomial_t>
79 const auto& pls = *ps.labelset();
80 const auto& pws = *ps.weightset();
81 const auto& ls = *aut->labelset();
84 for (
auto t =
path[dst]; t != aut->null_transition();
85 t =
path[aut->src_of(t)])
87 w = pws.mul(aut->weight_of(t), w);
88 auto nl = aut->label_of(t);
89 if (!ls.is_special(nl))
91 if (aut->src_of(t) == src)
std::vector< transition_t_of< Aut > > lightest_path_tag(const Aut &aut, state_t_of< Aut > src, state_t_of< Aut > dst)
Tag-based dispatch on implementation.
auto path_monomial(const Aut &aut, const std::vector< transition_t_of< Aut >> &path, state_t_of< Aut > src=Aut::element_type::pre(), state_t_of< Aut > dst=Aut::element_type::post()) -> boost::optional< typename detail::word_polynomialset_t< context_t_of< Aut >>::monomial_t >
Given a path (typically computed by lightest_path), the corresponding monomial (label, weight).
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
A mapping from strings to Values.
Tag to request the most appropriate version of an algorithm.
typename detail::transition_t_of_impl< base_t< ValueSet >>::type transition_t_of
auto make_word_polynomialset(const Ctx &ctx) -> word_polynomialset_t< Ctx >
The polynomialset of words of a labelset (not necessarily on words itself).
Paths in filesystems, i.e., file names.
std::vector< transition_t_of< Aut > > lightest_path(const Aut &aut, state_t_of< Aut > source, state_t_of< Aut > dest, a_star_tag)