Vcsn  2.2
Be Rational
a-star.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <boost/heap/fibonacci_heap.hpp>
4 
5 #include <vcsn/misc/set.hh>
7 
8 namespace vcsn
9 {
10  /*-----------------------------------------.
11  | Shortest path through A-Star algorithm. |
12  `-----------------------------------------*/
13 
18  struct a_star_tag {};
19 
20  namespace detail
21  {
28  template <Automaton Aut>
29  struct a_star_impl
30  {
31  using automaton_t = Aut;
37  using distance_t = std::vector<weight_t>;
38 
39  a_star_impl(const Aut& aut)
40  : aut_(aut)
41  , res_(aut_->all_states().back() + 1, aut_->null_transition())
42  , heuristic_dist_(aut_->all_states().back() + 1)
43  {};
44 
45  struct profile
46  {
47  profile(state_t state, const self_t& a_star)
48  : state_(state)
49  , a_star_(a_star)
50  {}
51 
52  bool operator<(const profile& rhs) const
53  {
54  auto ws = *a_star_.aut_->weightset();
55  if (a_star_.res_[state_] == a_star_.aut_->null_transition())
56  return true;
57  else if (a_star_.res_[rhs.state_] == a_star_.aut_->null_transition())
58  return false;
59  else
60  return ws.less(a_star_.heuristic_dist_[rhs.state_],
62  }
63 
64  friend std::ostream& operator<<(std::ostream& o, const profile& p)
65  {
66  auto a = p.a_star_;
67  auto ws = *a.aut_->weightset();
68  a.aut_->print_state_name(p.state_, o) << ':';
69  if (a.res_[p.state_] != a.aut_->null_transition())
70  return ws.print(a.heuristic_dist_[p.state_], o);
71  else
72  return o << "null";
73  }
74 
76  const self_t& a_star_;
77  };
78 
79  using heap_t = boost::heap::fibonacci_heap<profile>;
80 
81  template <typename Heuristic>
82  std::vector<transition_t>
83  operator()(state_t source, state_t dest, Heuristic heuristic)
84  {
85  auto ws = *aut_->weightset();
86  auto size = aut_->all_states().back() + 1;
87 
88  auto done = std::set<state_t>();
89 
90  auto todo = heap_t();
91  std::vector<typename heap_t::handle_type> handles(size);
92 
93  auto dist = distance_t(size);
94 
95  dist[source] = ws.one();
96  heuristic_dist_[source] = ws.add(ws.one(), heuristic(source, dest));
97  handles[source] = todo.emplace(source, *this);
98 
99  while (!todo.empty())
100  {
101  auto p = todo.top();
102  state_t s = p.state_;
103  if (s == dest)
104  return std::move(res_);
105  todo.pop();
106  done.insert(s);
107  for (auto t: all_out(aut_, s))
108  {
109  auto dst = aut_->dst_of(t);
110  if (!has(done, dst))
111  {
112  auto nw = ws.mul(dist[s], aut_->weight_of(t));
113  if (res_[dst] == aut_->null_transition()
114  || ws.less(nw, dist[dst]))
115  {
116  res_[dst] = t;
117  dist[dst] = nw;
118  heuristic_dist_[dst] = ws.add(nw, heuristic(dst, dest));
119  }
120  handles[dst] = todo.emplace(dst, *this);
121  }
122  }
123  }
124 
125  return std::vector<transition_t>(size, aut_->null_transition());
126  }
127 
128  private:
129  void show_heap_(const heap_t& todo)
130  {
131  const char* sep = "";
132  for (auto i = todo.ordered_begin(), end = todo.ordered_end();
133  i != end; ++i)
134  {
135  std::cout << sep << *i;
136  sep = ", ";
137  }
138  std::cout << std::endl;
139  }
140 
141  public:
144  std::vector<transition_t> res_;
146  };
147  }
148 
149  template <Automaton Aut>
150  std::vector<transition_t_of<Aut>>
151  lightest_path(const Aut& aut, state_t_of<Aut> source, state_t_of<Aut> dest,
152  a_star_tag)
153  {
154  using state_t = state_t_of<Aut>;
155  return detail::a_star_impl<Aut>(aut)(source, dest,
156  [aut](state_t, state_t)
157  {
158  return aut->weightset()->zero();
159  });
160  }
161 }
auto all_out(const Aut &aut, state_t_of< Aut > s)
Indexes of transitions leaving state s.
Definition: automaton.hh:37
Container::value_type back(const Container &container)
The last member of this Container.
Definition: algorithm.hh:27
state_t_of< automaton_t > state_t
Definition: a-star.hh:33
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
Definition: traits.hh:59
a_star_impl(const Aut &aut)
Definition: a-star.hh:39
A Star implementation of lightest automaton.
Definition: a-star.hh:29
Definition: a-star.hh:8
typename detail::weight_t_of_impl< base_t< ValueSet >>::type weight_t_of
Definition: traits.hh:58
std::vector< weight_t > distance_t
Definition: a-star.hh:37
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
Definition: traits.hh:56
const automaton_t & aut_
Definition: a-star.hh:142
std::vector< transition_t > res_
For each state, its predecessor.
Definition: a-star.hh:144
distance_t heuristic_dist_
Definition: a-star.hh:145
friend std::ostream & operator<<(std::ostream &o, const profile &p)
Definition: a-star.hh:64
typename detail::transition_t_of_impl< base_t< ValueSet >>::type transition_t_of
Definition: traits.hh:57
transition_t_of< automaton_t > transition_t
Definition: a-star.hh:34
ATTRIBUTE_PURE bool has(const boost::container::flat_set< Key, Compare, Allocator > &s, const Key &e)
Whether e is member of s.
Definition: setalpha.hh:25
boost::heap::fibonacci_heap< profile > heap_t
Definition: a-star.hh:79
profile(state_t state, const self_t &a_star)
Definition: a-star.hh:47
weightset_t_of< automaton_t > weightset_t
Definition: a-star.hh:36
weight_t_of< automaton_t > weight_t
Definition: a-star.hh:35
std::vector< transition_t > operator()(state_t source, state_t dest, Heuristic heuristic)
Definition: a-star.hh:83
size_t size(const ExpSet &rs, const typename ExpSet::value_t &r)
A-Star implementation (from vcsn/algos/a-star.hh).
Definition: a-star.hh:18
bool operator<(const profile &rhs) const
Definition: a-star.hh:52
void show_heap_(const heap_t &todo)
Definition: a-star.hh:129
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