Vcsn  2.2
Be Rational
quotient.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <algorithm> // min_element.
4 #include <unordered_map>
5 
6 #include <boost/range/algorithm/min_element.hpp>
7 #include <boost/range/algorithm/sort.hpp>
8 
10 #include <vcsn/dyn/automaton.hh>
11 
12 namespace vcsn
13 {
14 
15  namespace detail
16  {
20  template <Automaton Aut>
21  class quotienter
22  {
23  public:
24  using automaton_t = Aut;
26 
27  template <typename Ctx = context_t_of<Aut>>
29 
31 
32  using class_t = unsigned;
34  using set_t = std::vector<state_t>;
35  using state_to_class_t = std::unordered_map<state_t, class_t>;
36  using class_to_set_t = std::vector<set_t>;
37  using class_to_state_t = std::vector<state_t>;
38 
42  quotienter(class_to_set_t& class_to_set)
43  : class_to_set_(class_to_set)
45  {
46  sort_classes_();
47  }
48 
56  {
57  // For each class, put its smallest numbered state first
58  // (set_t is not a std::set, it's a vector!). We don't need
59  // to fully sort.
60  for (unsigned c = 0; c < num_classes_; ++c)
61  std::swap(class_to_set_[c][0],
62  *boost::min_element(class_to_set_[c]));
63 
64  // Sort class numbers by smallest state number.
66  [](const set_t& lhs, const set_t& rhs)
67  {
68  return lhs[0] < rhs[0];
69  });
70  }
71 
75  {
76  state_to_class_t state_to_class;
77  for (unsigned c = 0; c < num_classes_; ++c)
78  for (auto s: class_to_set_[c])
79  state_to_class[s] = c;
80 
81  auto origins = origins_t{};
82  auto res = make_fresh_automaton(aut);
83  auto class_to_res_state = class_to_state_t(num_classes_);
84  for (unsigned c = 0; c < num_classes_; ++c)
85  {
86  const std::vector<state_t>& set = class_to_set_[c];
87  state_t s = set[0];
88  class_to_res_state[c]
89  = s == aut->pre() ? res->pre()
90  : s == aut->post() ? res->post()
91  : res->new_state();
92  origins[class_to_res_state[c]].insert(begin(set), end(set));
93  }
94  for (unsigned c = 0; c < num_classes_; ++c)
95  {
96  // Copy the outgoing transitions of the first state of the
97  // class in the result.
98  state_t s = class_to_set_[c][0];
99  state_t src = class_to_res_state[c];
100  for (auto t : all_out(aut, s))
101  {
102  state_t d = aut->dst_of(t);
103  state_t dst = class_to_res_state[state_to_class[d]];
104  res->add_transition(src, dst,
105  aut->label_of(t), aut->weight_of(t));
106  }
107  }
108  return make_partition_automaton(res, aut, origins);
109  }
110 
111  private:
113  unsigned num_classes_;
114  };
115  }
116 
118  template <Automaton Aut>
120 
121  template <Automaton Aut>
122  inline
123  auto
124  quotient(const Aut& a,
126  -> quotient_t<Aut>
127  {
129  return quotient(a);
130  }
131 
132 } // namespace vcsn
auto all_out(const Aut &aut, state_t_of< Aut > s)
Indexes of transitions leaving state s.
Definition: automaton.hh:37
origins_t_of< quotient_t > origins_t
Definition: quotient.hh:30
auto make_partition_automaton(const fresh_automaton_t_of< Aut > &res, const Aut &input, const typename detail::partition_automaton_impl< Aut >::origins_t origins) -> partition_automaton_t< Aut >
Build a partition_automaton.
void sort_classes_()
Sort the classes.
Definition: quotient.hh:55
partition_automaton_t< Aut > quotient_t
The return type when calling quotient on Aut.
Definition: quotient.hh:119
typename detail::partition_automaton_t_impl< Aut >::type partition_automaton_t
The return type when calling quotient on Aut.
Request the set implementation (bool weights).
Definition: a-star.hh:8
fresh_automaton_t_of< automaton_t, Ctx > fresh_automaton_t
Definition: quotient.hh:28
state_t_of< automaton_t > state_t
Definition: quotient.hh:33
auto quotient(const Aut &a, typename detail::quotienter< Aut >::class_to_set_t &cs) -> quotient_t< Aut >
Definition: quotient.hh:124
quotienter(class_to_set_t &class_to_set)
Definition: quotient.hh:42
Apply a quotient onto an automaton: fuse equivalent states.
Definition: quotient.hh:21
std::vector< state_t > set_t
Definition: quotient.hh:34
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
Definition: traits.hh:56
typename Aut::element_type::template fresh_automaton_t< Context > fresh_automaton_t_of
Given an automaton type, the type of its copies.
Definition: traits.hh:74
std::vector< set_t > class_to_set_t
Definition: quotient.hh:36
std::unordered_map< state_t, class_t > state_to_class_t
Definition: quotient.hh:35
AutOut make_fresh_automaton(const AutIn &model)
Create an empty, mutable, automaton, based on another one.
Definition: copy.hh:90
partition_automaton_t< automaton_t > quotient_t
Definition: quotient.hh:25
auto sort(const Aut &a) -> permutation_automaton< Aut >
Definition: sort.hh:163
std::vector< state_t > class_to_state_t
Definition: quotient.hh:37
quotient_t operator()(const automaton_t &aut)
Build the resulting automaton.
Definition: quotient.hh:74
size_t size(const ExpSet &rs, const typename ExpSet::value_t &r)
typename origins_t_of_impl< Aut >::type origins_t_of
The type of the origins map for a partition automaton, or a transposed one.
class_to_set_t & class_to_set_
Definition: quotient.hh:112