Vcsn  2.4
Be Rational
lightest-path.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <boost/optional.hpp>
4 
6 #include <vcsn/algos/a-star.hh>
8 #include <vcsn/algos/dijkstra.hh>
9 #include <vcsn/algos/tags.hh>
12 #include <vcsn/misc/getargs.hh>
13 
14 namespace vcsn
15 {
17  template <Automaton Aut, typename Tag = auto_tag>
18  std::vector<transition_t_of<Aut>>
19  lightest_path(const Aut& aut, Tag tag = {})
20  {
21  return lightest_path(aut, aut->pre(), aut->post(), tag);
22  }
23 
24  template <Automaton Aut>
25  std::vector<transition_t_of<Aut>>
26  lightest_path(const Aut& aut, state_t_of<Aut> source, state_t_of<Aut> dest,
27  auto_tag = {})
28  {
29  if (weightset_t_of<Aut>::has_lightening_weights())
30  return lightest_path(aut, source, dest, bellman_ford_tag{});
31  else
32  return lightest_path(aut, source, dest, dijkstra_tag{});
33  }
34 
35  namespace detail
36  {
38  template <Automaton Aut, typename Tag>
39  std::vector<transition_t_of<Aut>>
40  lightest_path_tag(const Aut& aut,
42  {
43  return lightest_path(aut, src, dst, Tag{});
44  }
45  }
46 
48  template <Automaton Aut>
49  std::vector<transition_t_of<Aut>>
50  lightest_path(const Aut& aut, state_t_of<Aut> src, state_t_of<Aut> dst,
51  const std::string& algo)
52  {
53  using state_t = state_t_of<Aut>;
54  using path_t = std::vector<transition_t_of<Aut>>;
55  static const auto map
57  {
58  "lightest-path algorithm",
59  {
60  {"auto", detail::lightest_path_tag<Aut, auto_tag>},
61  {"a-star", detail::lightest_path_tag<Aut, a_star_tag>},
62  {"bellman-ford", detail::lightest_path_tag<Aut, bellman_ford_tag>},
63  {"dijkstra", detail::lightest_path_tag<Aut, dijkstra_tag>},
64  {"yen", detail::lightest_path_tag<Aut, yen_tag>},
65  }
66  };
67  return map[algo](aut, src, dst);
68  }
69 
74  template <Automaton Aut>
75  auto
76  path_monomial(const Aut& aut,
77  const std::vector<transition_t_of<Aut>>& path,
78  state_t_of<Aut> src = Aut::element_type::pre(),
79  state_t_of<Aut> dst = Aut::element_type::post())
80  -> boost::optional<typename detail::word_polynomialset_t<context_t_of<Aut>>::monomial_t>
81  {
82  auto ps = make_word_polynomialset(aut->context());
83  const auto& pls = *ps.labelset();
84  const auto& pws = *ps.weightset();
85  const auto& ls = *aut->labelset();
86  auto w = pws.one();
87  auto l = pls.one();
88  for (auto t = path[dst]; t != aut->null_transition();
89  t = path[aut->src_of(t)])
90  {
91  w = pws.mul(aut->weight_of(t), w);
92  auto nl = aut->label_of(t);
93  if (!ls.is_special(nl))
94  l = pls.mul(nl, l);
95  if (aut->src_of(t) == src)
96  return {{l, w}};
97  }
98  return boost::none;
99  }
100 }
auto make_word_polynomialset(const Ctx &ctx) -> word_polynomialset_t< Ctx >
The polynomialset of words of a labelset (not necessarily on words itself).
Tag to request the most appropriate version of an algorithm.
Definition: tags.hh:16
Definition: a-star.hh:8
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
Definition: traits.hh:64
typename detail::transition_t_of_impl< base_t< ValueSet >>::type transition_t_of
Definition: traits.hh:65
A mapping from strings to Values.
Definition: getargs.hh:33
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).
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
Paths in filesystems, i.e., file names.
Definition: path.hh:21