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