Vcsn  2.2
Be Rational
lightest-path.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <vcsn/algos/a-star.hh>
5 #include <vcsn/algos/dijkstra.hh>
6 #include <vcsn/algos/tags.hh>
9 #include <vcsn/misc/getargs.hh>
10 
11 namespace vcsn
12 {
14  template <Automaton Aut, typename Tag = auto_tag>
15  std::vector<transition_t_of<Aut>>
16  lightest_path(const Aut& aut, Tag tag = {})
17  {
18  return lightest_path(aut, aut->pre(), aut->post(), tag);
19  }
20 
21  template <Automaton Aut>
22  std::vector<transition_t_of<Aut>>
23  lightest_path(const Aut& aut, state_t_of<Aut> source, state_t_of<Aut> dest,
24  auto_tag = {})
25  {
26  if (weightset_t_of<Aut>::has_lightening_weights())
27  return lightest_path(aut, source, dest, bellman_ford_tag{});
28  else
29  return lightest_path(aut, source, dest, dijkstra_tag{});
30  }
31 
32  namespace detail
33  {
35  template <Automaton Aut, typename Tag>
36  std::vector<transition_t_of<Aut>>
37  lightest_path_tag(const Aut& aut,
39  {
40  return lightest_path(aut, src, dst, Tag{});
41  }
42  }
43 
45  template <Automaton Aut>
46  std::vector<transition_t_of<Aut>>
47  lightest_path(const Aut& aut, state_t_of<Aut> src, state_t_of<Aut> dst,
48  const std::string& algo)
49  {
50  using state_t = state_t_of<Aut>;
51  using path_t = std::vector<transition_t_of<Aut>>;
52  static const auto map
54  {
55  "lightest-path algorithm",
56  {
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>},
61  }
62  };
63  return map[algo](aut, src, dst);
64  }
65 
70  template <Automaton Aut>
71  auto
72  path_monomial(const Aut& aut,
73  const std::vector<transition_t_of<Aut>>& path,
74  state_t_of<Aut> src = Aut::element_type::pre(),
75  state_t_of<Aut> dst = Aut::element_type::post())
76  -> boost::optional<typename detail::word_polynomialset_t<context_t_of<Aut>>::monomial_t>
77  {
78  auto ps = make_word_polynomialset(aut->context());
79  const auto& pls = *ps.labelset();
80  const auto& pws = *ps.weightset();
81  const auto& ls = *aut->labelset();
82  auto w = pws.one();
83  auto l = pls.one();
84  for (auto t = path[dst]; t != aut->null_transition();
85  t = path[aut->src_of(t)])
86  {
87  w = pws.mul(aut->weight_of(t), w);
88  auto nl = aut->label_of(t);
89  if (!ls.is_special(nl))
90  l = pls.mul(nl, l);
91  if (aut->src_of(t) == src)
92  return {{l, w}};
93  }
94  return boost::none;
95  }
96 }
Definition: a-star.hh:8
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
Definition: traits.hh:56
A mapping from strings to Values.
Definition: getargs.hh:33
Tag to request the most appropriate version of an algorithm.
Definition: tags.hh:16
typename detail::transition_t_of_impl< base_t< ValueSet >>::type transition_t_of
Definition: traits.hh:57
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.
Definition: path.hh:21
std::vector< transition_t_of< Aut > > lightest_path(const Aut &aut, state_t_of< Aut > source, state_t_of< Aut > dest, a_star_tag)
Definition: a-star.hh:151