Vcsn  2.4
Be Rational
distance.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <algorithm>
4 #include <iostream>
5 #include <limits>
6 #include <queue>
7 #include <unordered_set>
8 #include <unordered_map>
9 #include <vector>
10 
11 #include <boost/range/algorithm/max_element.hpp>
12 
13 #include <vcsn/algos/copy.hh>
14 #include <vcsn/ctx/context.hh>
15 #include <vcsn/dyn/value.hh>
16 #include <vcsn/misc/deque.hh>
17 #include <vcsn/misc/pair.hh>
18 #include <vcsn/misc/queue.hh>
19 #include <vcsn/weightset/nmin.hh>
20 
21 namespace vcsn
22 {
26  template <Automaton Aut>
27  std::vector<weight_t_of<Aut>>
29  {
30  using weight_t = weight_t_of<Aut>;
31  using state_t = state_t_of<Aut>;
32 
33  auto ws = *aut->weightset();
34  auto d = std::vector<weight_t>(states_size(aut), ws.zero());
35  d[s0] = ws.one();
36  auto r = d;
37 
38  auto todo = std::deque<state_t>{s0};
39  while (!todo.empty())
40  {
41  auto s = todo.front();
42  todo.pop_front();
43  auto r1 = r[s];
44  r[s] = ws.zero();
45  for (auto t : all_out(aut, s))
46  {
47  auto dst = aut->dst_of(t);
48  auto w1 = ws.mul(r1, aut->weight_of(t));
49  auto w = ws.add(d[dst], w1);
50  if (!ws.equal(d[dst], w))
51  {
52  d[dst] = w;
53  r[dst] = ws.add(r[dst], w1);
54  if (!has(todo, dst))
55  todo.emplace_back(dst);
56  }
57  }
58  }
59  return d;
60  }
61 
68  template <Automaton Aut>
69  std::unordered_map<state_t_of<Aut>,
70  std::pair<unsigned,
71  transition_t_of<Aut>>>
72  paths_ibfs(const Aut& aut, const std::vector<state_t_of<Aut>>& start)
73  {
74  using automaton_t = Aut;
75  using state_t = state_t_of<automaton_t>;
76  using transition_t = transition_t_of<automaton_t>;
77 
78  auto todo = detail::make_queue(start);
79  auto marked = std::unordered_set<state_t>{};
80  auto parent
81  = std::unordered_map<state_t, std::pair<unsigned, transition_t>>{};
82 
83  while (!todo.empty())
84  {
85  state_t p = todo.front();
86  todo.pop();
87  marked.insert(p);
88  for (auto t : all_in(aut, p))
89  {
90  auto s = aut->src_of(t);
91  if (marked.find(s) == marked.end())
92  {
93  todo.push(s);
94  auto cur_p = parent.find(p);
95  unsigned cur_d
96  = cur_p == parent.end() ? 1
97  : cur_p->second.first + 1;
98  parent[s] = {cur_d, t};
99  }
100  }
101  }
102  return parent;
103  }
104 
105  template <Automaton Aut>
106  std::vector<std::vector<weight_t_of<Aut>>>
107  all_distances(const Aut& aut)
108  {
109  using automaton_t = Aut;
110  using weight_t = weight_t_of<automaton_t>;
111 
112  auto ws = aut->weightset();
113  auto n = states_size(aut);
114  std::vector<std::vector<weight_t>> res(
115  n, std::vector<weight_t>(n, ws->zero()));
116 
117  for (auto t : all_transitions(aut))
118  {
119  auto i = aut->src_of(t);
120  auto j = aut->dst_of(t);
121  res[i][j] = ws->add(res[i][j], aut->weight_of(t));
122  }
123  for (auto k : aut->states())
124  {
125  auto reskk = res[k][k] = ws->star(res[k][k]);
126  for (auto i : aut->all_states())
127  for (auto j : aut->all_states())
128  if (i != k && j != k)
129  res[i][j] = ws->add(
130  res[i][j],
131  ws->mul(res[i][k], reskk, res[k][j])
132  );
133  for (auto i : aut->all_states())
134  if (i != k)
135  {
136  res[k][i] = ws->mul(reskk, res[k][i]);
137  res[i][k] = ws->mul(res[i][k], reskk);
138  }
139  }
140  return res;
141  }
142 }
std::unordered_map< state_t_of< Aut >, std::pair< unsigned, transition_t_of< Aut > > > paths_ibfs(const Aut &aut, const std::vector< state_t_of< Aut >> &start)
Find the shortest paths from some states to all the states.
Definition: distance.hh:72
std::queue< typename Range::value_type > make_queue(const Range &range)
The content of cont as a queue.
Definition: queue.hh:16
return res
Definition: multiply.hh:398
value_t mul(const Ts &...ts) const
A variadic multiplication.
Definition: weightset.hh:60
Provide a variadic mul on top of a binary mul(), and one().
Definition: fwd.hh:46
std::vector< std::vector< weight_t_of< Aut > > > all_distances(const Aut &aut)
Definition: distance.hh:107
size_t states_size(const Aut &aut)
The largest state number, plus one.
Definition: automaton.hh:40
Definition: a-star.hh:8
auto all_out(const Aut &aut, state_t_of< Aut > s)
Indexes of transitions leaving state s.
Definition: automaton.hh:66
pair_automaton< Aut > pair(const Aut &aut, bool keep_initials=false)
Definition: pair.hh:252
typename detail::weight_t_of_impl< base_t< ValueSet >>::type weight_t_of
Definition: traits.hh:66
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
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
auto all_in(const Aut &aut, state_t_of< Aut > s)
Indexes of transitions entering state s.
Definition: automaton.hh:115
auto all_transitions(const Aut &aut)
All the transition indexes between all states (including pre and post).
Definition: automaton.hh:213
std::vector< weight_t_of< Aut > > ss_shortest_distance(const Aut &aut, state_t_of< Aut > s0)
Single source shortest distance.
Definition: distance.hh:28