Vcsn  2.3
Be Rational
dijkstra.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <boost/heap/fibonacci_heap.hpp>
4 
5 #include <vcsn/algos/tags.hh>
7 
8 namespace vcsn
9 {
10 
11  /*-------------------------------------------.
12  | Shortest path through Dijkstra algorithm. |
13  `-------------------------------------------*/
14 
15  namespace detail
16  {
30  template <Automaton Aut, typename ValueSet, typename Mul>
32  {
33  using automaton_t = Aut;
42  using valueset_t = ValueSet;
43  using value_t = typename valueset_t::value_t;
44  using distance_t = std::vector<value_t>;
45 
46  dijkstra_impl(const Aut& aut, const ValueSet& vs, Mul mul)
47  : aut_(aut)
48  , res_(states_size(aut_), aut_->null_transition())
50  , vs_{vs}
51  , mul_{mul}
52  {};
53 
54  struct profile
55  {
56  profile(state_t state, const self_t& d)
57  : state_(state)
58  , self_(d)
59  {}
60 
61  bool operator<(const profile& rhs) const
62  {
63  if (self_.res_[state_] == self_.aut_->null_transition())
64  return true;
65  else if (self_.res_[rhs.state_] == self_.aut_->null_transition())
66  return false;
67  else
68  return self_.vs_.less(self_.dist_[rhs.state_], self_.dist_[state_]);
69  }
70 
72  const self_t& self_;
73  };
74 
75  using heap_t = boost::heap::fibonacci_heap<profile>;
76 
77  std::vector<transition_t>
78  operator()(state_t source, state_t dest)
79  {
80  auto size = states_size(aut_);
81  auto handles = std::vector<typename heap_t::handle_type>(size);
82  auto todo = heap_t();
83 
84  dist_[source] = vs_.one();
85  handles[source] = todo.emplace(source, *this);
86 
87  while (!todo.empty())
88  {
89  auto p = todo.top();
90  todo.pop();
91  state_t s = p.state_;
92  if (s == dest)
93  break;
94  else
95  for (auto t: all_out(aut_, s))
96  {
97  auto dst = aut_->dst_of(t);
98  auto nv = mul_(dist_[s], t);
99  if (res_[dst] == aut_->null_transition())
100  {
101  // First visit.
102  dist_[dst] = nv;
103  res_[dst] = t;
104  handles[dst] = todo.emplace(dst, *this);
105  }
106  else if (vs_.less(nv, dist_[dst]))
107  {
108  // Lighter path.
109  dist_[dst] = nv;
110  res_[dst] = t;
111  todo.update(handles[dst]);
112  }
113  }
114  }
115  return std::move(res_);
116  }
117 
118  public:
121  std::vector<transition_t> res_;
123  const ValueSet& vs_;
124  Mul mul_;
125  };
126 
127  template <Automaton Aut, typename ValueSet, typename Mul>
128  auto
129  make_dijkstra_impl(const Aut& aut, const ValueSet& vs, Mul mul)
130  {
131  return dijkstra_impl<Aut, ValueSet, Mul>(aut, vs, mul);
132  }
133  }
134 
135  template <Automaton Aut>
136  std::vector<transition_t_of<Aut>>
137  lightest_path(const Aut& aut, state_t_of<Aut> source, state_t_of<Aut> dest,
138  dijkstra_tag)
139  {
140  auto get_value = [&aut](auto lhs, transition_t_of<Aut> t)
141  {
142  return aut->weightset()->mul(lhs, aut->weight_of(t));
143  };
144  auto algo = detail::make_dijkstra_impl(aut, *aut->weightset(), get_value);
145  return std::move(algo(source, dest));
146  }
147 }
label_t_of< automaton_t > label_t
Definition: dijkstra.hh:37
typename detail::weight_t_of_impl< base_t< ValueSet >>::type weight_t_of
Definition: traits.hh:66
bool operator<(const profile &rhs) const
Definition: dijkstra.hh:61
std::vector< transition_t > res_
For each state, its predecessor.
Definition: dijkstra.hh:121
typename detail::transition_t_of_impl< base_t< ValueSet >>::type transition_t_of
Definition: traits.hh:65
size_t states_size(const Aut &aut)
The largest state number, plus one.
Definition: automaton.hh:19
size_t size(const ExpSet &rs, const typename ExpSet::value_t &r)
typename detail::context_t_of_impl< base_t< ValueSet >>::type context_t_of
Definition: traits.hh:61
Dijkstra implementation of lightest automaton.
Definition: dijkstra.hh:31
typename valueset_t::value_t value_t
Definition: dijkstra.hh:43
const automaton_t & aut_
Definition: dijkstra.hh:119
transition_t_of< automaton_t > transition_t
Definition: dijkstra.hh:36
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
Definition: traits.hh:64
Dijkstra implementation.
Definition: tags.hh:135
profile(state_t state, const self_t &d)
Definition: dijkstra.hh:56
weightset_t_of< automaton_t > weightset_t
Definition: dijkstra.hh:39
Definition: a-star.hh:8
typename detail::label_t_of_impl< base_t< ValueSet >>::type label_t_of
Definition: traits.hh:62
std::vector< value_t > distance_t
Definition: dijkstra.hh:44
context_t_of< automaton_t > context_t
Definition: dijkstra.hh:40
state_t_of< automaton_t > state_t
Definition: dijkstra.hh:35
boost::heap::fibonacci_heap< profile > heap_t
Definition: dijkstra.hh:75
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
Definition: traits.hh:67
weight_t_of< automaton_t > weight_t
Definition: dijkstra.hh:38
dijkstra_impl(const Aut &aut, const ValueSet &vs, Mul mul)
Definition: dijkstra.hh:46
auto all_out(const Aut &aut, state_t_of< Aut > s)
Indexes of transitions leaving state s.
Definition: automaton.hh:45
const ValueSet & vs_
Definition: dijkstra.hh:123
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 make_dijkstra_impl(const Aut &aut, const ValueSet &vs, Mul mul)
Definition: dijkstra.hh:129
std::vector< transition_t > operator()(state_t source, state_t dest)
Definition: dijkstra.hh:78