Vcsn  2.4
Be Rational
k-lightest-path.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <algorithm>
4 
5 #include <boost/heap/fibonacci_heap.hpp>
6 
8 #include <vcsn/algos/dijkstra.hh>
10 #include <vcsn/algos/filter.hh>
11 
12 namespace vcsn
13 {
17  struct yen_tag {};
18 
19  namespace detail
20  {
38  template <Automaton Aut, typename ValueSet,
39  typename Mul, typename GetValue>
40  struct yen_impl
41  {
42  using automaton_t = Aut;
48  using paths_t = std::vector<path_t>;
49 
50  using valueset_t = ValueSet;
51  using value_t = typename valueset_t::value_t;
52 
53  yen_impl(const automaton_t& aut, const ValueSet& vs,
54  Mul mul, GetValue get_value)
55  : aut_{aut}
56  , vs_{vs}
57  , mul_{mul}
58  , get_value_(get_value)
59  {}
60 
61  struct profile
62  {
63  profile(const path_t& path, const valueset_t& vs,
64  const value_t& v)
65  : path_{path}
66  , vs_{vs}
67  , v_{v}
68  {}
69 
70  bool operator<(const profile& rhs) const
71  {
72  return vs_.less(rhs.v_, v_);
73  }
74 
76  const valueset_t& vs_;
78  };
79 
80  using heap_t = boost::heap::fibonacci_heap<profile>;
81 
90  template <Automaton AnyAut>
92  path(const AnyAut& aut,
94  state_t_of<AnyAut> src = AnyAut::element_type::pre(),
95  state_t_of<AnyAut> dst = AnyAut::element_type::post())
96  {
98  for (auto t = path[dst];
99  t != aut->null_transition();
100  t = path[aut->src_of(t)])
101  {
102  res.emplace_back(t);
103  if (aut->src_of(t) == src)
104  break;
105  }
106  std::reverse(res.begin(), res.end());
107  return res;
108  }
109 
116  template <Automaton AnyAut>
118  compute_lightest_path(const AnyAut& aut,
119  state_t_of<AnyAut> src = Aut::element_type::pre(),
120  state_t_of<AnyAut> dst = Aut::element_type::post())
121  {
122  auto algo = detail::make_dijkstra_impl(aut, vs_, mul_);
123  return std::move(algo(src, dst));
124  }
125 
126  paths_t
127  operator()(state_t src, state_t dst, unsigned k)
128  {
129  auto first = compute_lightest_path(aut_, src, dst);
130  auto res = paths_t{path(aut_, first, src, dst)};
131  auto ps = make_word_polynomialset(aut_->context());
132 
133  auto heap = heap_t();
134 
135  for (unsigned i = 1u; i < k; i++)
136  {
137  const auto& prev = res[i - 1];
138  for (unsigned j = 0u; j < prev.size(); j++)
139  {
140  auto filter_aut = filter<automaton_t, true>(aut_);
141  filter_aut->unhide_all_states();
142  filter_aut->unhide_all_transition();
143  auto spur_node = filter_aut->src_of(prev[j]);
144  auto root_path = path_t(prev.begin(), prev.begin() + j);
145 
146  for (const auto& selected_path: res)
147  if (j < selected_path.size())
148  {
149  auto diff = std::mismatch(root_path.begin(), root_path.end(),
150  selected_path.begin(), selected_path.begin() + j);
151  if (diff.first == root_path.end()
152  && filter_aut->has_transition(selected_path[j]))
153  filter_aut->hide_transition(selected_path[j]);
154  }
155 
156  for (auto t: root_path)
157  if (t != filter_aut->null_transition()
158  && filter_aut->src_of(t) != spur_node
159  && filter_aut->src_of(t) != aut_->pre()
160  && filter_aut->has_state(filter_aut->src_of(t)))
161  filter_aut->hide_state(filter_aut->src_of(t));
162 
163  auto shortest_path
164  = compute_lightest_path(filter_aut, spur_node, dst);
165  auto spur_path
166  = path(filter_aut, shortest_path, spur_node, dst);
167  root_path.insert(root_path.end(),
168  spur_path.begin(), spur_path.end());
169  if (!root_path.empty()
170  && filter_aut->src_of(root_path.front()) == src
171  && filter_aut->dst_of(root_path.back()) == dst)
172  {
173  bool already_found = false;
174  for (const auto& profile: heap)
175  {
176  const auto& selected_path = profile.path_;
177  if (root_path.size() == selected_path.size())
178  {
179  auto diff = std::mismatch(root_path.begin(), root_path.end(),
180  selected_path.begin(), selected_path.end());
181  if (diff.first == root_path.end())
182  {
183  already_found = true;
184  break;
185  }
186  }
187  }
188  if (!already_found)
189  {
190  auto m = *path_monomial(filter_aut, format_lightest(filter_aut, root_path), src, dst);
191  heap.emplace(std::move(root_path), vs_, get_value_(m));
192  }
193  }
194  }
195  if (heap.empty())
196  break;
197  res.push_back(heap.top().path_);
198  heap.pop();
199  }
200  return res;
201  }
202 
204  const ValueSet& vs_;
205  Mul mul_;
206  GetValue get_value_;
207  };
208 
209  template <Automaton Aut, typename ValueSet, typename Mul, typename GetValue>
210  auto
211  make_yen(const Aut& aut, const ValueSet& vs, Mul mul, GetValue get_value)
212  {
214  (aut, vs, mul, get_value));
215  }
216  }
217 
218 
219  template <Automaton Aut>
220  std::vector<path_t_of<Aut>>
222  unsigned k)
223  {
224  auto mul = [&aut](auto lhs, transition_t_of<Aut> t)
225  {
226  return aut->weightset()->mul(lhs, aut->weight_of(t));
227  };
228  auto get_value = [](auto m) { return m.second; };
229  auto yen = detail::make_yen(aut, *aut->weightset(), mul, get_value);
230  return yen(src, dst, k);
231  }
232 
239  template <Automaton Aut>
240  predecessors_t_of<Aut>
241  format_lightest(const Aut& aut, const std::vector<transition_t_of<Aut>>& path)
242  {
243  auto res = predecessors_t_of<Aut>(states_size(aut), aut->null_transition());
244  for (auto t : path)
245  if (t != aut->null_transition())
246  res[aut->dst_of(t)] = t;
247  return res;
248  }
249 
250  template <Automaton Aut>
251  predecessors_t_of<Aut>
253  yen_tag)
254  {
255  auto paths = k_lightest_path(aut, src, dst, 1);
256  auto res
257  = paths.empty() ? std::vector<transition_t_of<Aut>>() : paths.front();
258  return format_lightest(aut, res);
259  }
260 }
profile(const path_t &path, const valueset_t &vs, const value_t &v)
std::vector< path_t_of< Aut > > k_lightest_path(const Aut &aut, state_t_of< Aut > src, state_t_of< Aut > dst, unsigned k)
Yen implementation of the K lightest automaton algorithm.
mutable_automaton< Context > u(const Context &ctx, unsigned n)
The Brzozowski universal witness.
Definition: u.hh:15
return res
Definition: multiply.hh:398
paths_t operator()(state_t src, state_t dst, unsigned k)
path_t_of< AnyAut > path(const AnyAut &aut, const predecessors_t_of< AnyAut > &path, state_t_of< AnyAut > src=AnyAut::element_type::pre(), state_t_of< AnyAut > dst=AnyAut::element_type::post())
Transform a map transition_t -> transition_t representing the predecessors of each transition into a ...
weight_t_of< automaton_t > weight_t
predecessors_t_of< Aut > format_lightest(const Aut &aut, const std::vector< transition_t_of< Aut >> &path)
A state-indexed vector of predecessor transitions from the path path.
#define Automaton
Definition: automaton.hh:23
state_t_of< automaton_t > state_t
auto make_word_polynomialset(const Ctx &ctx) -> word_polynomialset_t< Ctx >
The polynomialset of words of a labelset (not necessarily on words itself).
size_t states_size(const Aut &aut)
The largest state number, plus one.
Definition: automaton.hh:40
const automaton_t & aut_
Definition: a-star.hh:8
predecessors_t_of< AnyAut > compute_lightest_path(const AnyAut &aut, state_t_of< AnyAut > src=Aut::element_type::pre(), state_t_of< AnyAut > dst=Aut::element_type::post())
Compute a lightest path on a part of the automaton.
bool operator<(const profile &rhs) const
typename detail::weight_t_of_impl< base_t< ValueSet >>::type weight_t_of
Definition: traits.hh:66
transition_t_of< automaton_t > transition_t
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
Definition: traits.hh:64
typename valueset_t::value_t value_t
auto make_yen(const Aut &aut, const ValueSet &vs, Mul mul, GetValue get_value)
yen_impl(const automaton_t &aut, const ValueSet &vs, Mul mul, GetValue get_value)
typename detail::transition_t_of_impl< base_t< ValueSet >>::type transition_t_of
Definition: traits.hh:65
std::vector< path_t > paths_t
auto make_dijkstra_impl(const Aut &aut, const ValueSet &vs, Mul mul)
Definition: dijkstra.hh:129
path_t_of< automaton_t > path_t
std::vector< transition_t_of< Aut >> path_t_of
A list of transitions representing a path.
Definition: automaton.hh:27
boost::heap::fibonacci_heap< profile > heap_t
std::vector< transition_t_of< Aut >> predecessors_t_of
A state-indexed vector of predecessor transitions from the path path.
Definition: automaton.hh:18
context_t_of< automaton_t > context_t
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).
Yen implementation.
typename detail::context_t_of_impl< base_t< ValueSet >>::type context_t_of
Definition: traits.hh:61
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