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