Vcsn  2.4
Be Rational
bellman-ford.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <boost/optional.hpp>
4 
5 #include <vcsn/core/automaton.hh> // states_size
6 #include <vcsn/misc/set.hh>
7 #include <vcsn/weightset/fwd.hh>
8 
9 namespace vcsn
10 {
11  /*-----------------------------------------------.
12  | Shortest path through Bellman-Ford algorithm. |
13  `-----------------------------------------------*/
14 
18  struct bellman_ford_tag {};
19 
20  namespace detail
21  {
27  template <Automaton Aut>
28  boost::optional<std::vector<transition_t_of<Aut>>>
29  bellman_ford_impl(const Aut& aut, state_t_of<Aut> source)
30  {
31  using transition_t = transition_t_of<Aut>;
32  auto size = states_size(aut);
33  auto dist = std::vector<weight_t_of<Aut>>(size);
34  auto res = std::vector<transition_t>(size, aut->null_transition());
35  auto ws = *aut->weightset();
36 
37  dist[source] = ws.one();
38 
39  // Iterate one time for each state over each transitions.
40  for (auto _: aut->all_states())
41  for (auto t: all_transitions(aut))
42  {
43  auto src = aut->src_of(t);
44 
45  if (res[src] != aut->null_transition() || src == source)
46  {
47  auto dst = aut->dst_of(t);
48  auto nw = ws.mul(dist[src], aut->weight_of(t));
49  if (res[dst] == aut->null_transition()
50  || ws.less(nw, dist[dst]))
51  {
52  dist[dst] = nw;
53  res[dst] = t;
54  }
55  }
56  }
57 
58  // Check for lightening cycles.
59  for (auto t: transitions(aut))
60  {
61  auto src = aut->src_of(t);
62  auto dst = aut->dst_of(t);
63  if (res[src] != aut->null_transition()
64  && (res[dst] == aut->null_transition()
65  || ws.less(ws.mul(dist[src], aut->weight_of(t)), dist[dst])))
66  return boost::none;
67  }
68 
69  return std::move(res);
70  }
71  }
72 
75  template <Automaton Aut>
76  std::vector<transition_t_of<Aut>>
79  {
80  auto res = bellman_ford_impl(aut, source);
81  require(res, "bellman-ford: automaton with negative cycle");
82  return std::move(*res);
83  }
84 }
auto transitions(const Aut &aut) -> decltype(all_transitions(aut, is_special_t< Aut >
All the transition indexes between visible states.
Definition: automaton.hh:247
return res
Definition: multiply.hh:398
void require(Bool b, Args &&...args)
If b is not verified, raise an error with args as message.
Definition: raise.hh:91
size_t states_size(const Aut &aut)
The largest state number, plus one.
Definition: automaton.hh:40
boost::optional< std::vector< transition_t_of< Aut > > > bellman_ford_impl(const Aut &aut, state_t_of< Aut > source)
Bellman-Ford implementation of lightest automaton.
Definition: bellman-ford.hh:29
Definition: a-star.hh:8
size_t size(const ExpSet &rs, const typename ExpSet::value_t &r)
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
Bellman-Ford implementation (from vcsn/algos/bellman-ford.hh).
Definition: bellman-ford.hh:18
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
auto all_transitions(const Aut &aut)
All the transition indexes between all states (including pre and post).
Definition: automaton.hh:213