Vcsn  2.3
Be Rational
accessible.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <queue>
4 
5 #include <vcsn/algos/filter.hh>
7 #include <vcsn/dyn/fwd.hh>
10 
11 namespace vcsn
12 {
13 
14  /*--------------------------------------------------.
15  | Sets of accessible, coaccessible, useful states. |
16  `--------------------------------------------------*/
17 
18  template <Automaton Aut>
19  using states_t = std::unordered_set<state_t_of<Aut>>;
20 
25  template <Automaton Aut>
27  accessible_states(const Aut& aut, bool strict = true)
28  {
29  using automaton_t = Aut;
30  using state_t = state_t_of<automaton_t>;
31 
32  // Reachable states.
33  auto res = states_t<Aut>{aut->pre()};
34 
35  // States work list.
36  using worklist_t = std::queue<state_t>;
37  auto todo = worklist_t{};
38  todo.emplace(aut->pre());
39 
40  while (!todo.empty())
41  {
42  const state_t src = todo.front();
43  todo.pop();
44 
45  if (strict || !aut->is_lazy(src))
46  for (auto tr : all_out(aut, src))
47  {
48  state_t dst = aut->dst_of(tr);
49  // If we have not seen it already, explore its successors.
50  if (res.emplace(dst).second)
51  todo.emplace(dst);
52  }
53  }
54 
55  return res;
56  }
57 
62  template <Automaton Aut>
63  states_t<Aut>
64  coaccessible_states(const Aut& a, bool strict = true)
65  {
66  return accessible_states(transpose(a), strict);
67  }
68 
73  template <Automaton Aut>
74  states_t<Aut>
75  useful_states(const Aut& a, bool strict = true)
76  {
77  auto accessible = accessible_states(a, strict);
78  auto coaccessible = coaccessible_states(a, strict);
80  }
81 
82 
83  /*----------------------------------------------------.
84  | Number of accessible, coaccessible, useful states. |
85  `----------------------------------------------------*/
86 
88  template <Automaton Aut>
89  size_t
90  num_accessible_states(const Aut& a)
91  {
92  auto set = accessible_states(a);
93  size_t res = set.size();
94  // Don't count pre().
95  res -= 1;
96  // Don't count post().
97  if (has(set, a->post()))
98  res -= 1;
99  return res;
100  }
101 
103  template <Automaton Aut>
104  size_t
106  {
107  return num_accessible_states(transpose(a));
108  }
109 
111  template <Automaton Aut>
112  size_t
113  num_useful_states(const Aut& a)
114  {
115  auto set = useful_states(a);
116  size_t res = set.size();
117  // Don't count pre().
118  if (has(set, a->pre()))
119  res -= 1;
120  // Don't count post().
121  if (has(set, a->post()))
122  res -= 1;
123  return res;
124  }
125 
126 
127  /*-----------------------------------------------.
128  | accessible, coaccessible, useful subautomata. |
129  `-----------------------------------------------*/
130 
132  template <Automaton Aut>
133  filter_automaton<Aut>
134  accessible(const Aut& a)
135  {
136  return vcsn::filter(a, accessible_states(a));
137  }
138 
140  template <Automaton Aut>
141  filter_automaton<Aut>
142  coaccessible(const Aut& a)
143  {
144  return vcsn::filter(a, coaccessible_states(a));
145  }
146 
148  template <Automaton Aut>
149  filter_automaton<Aut>
150  trim(const Aut& a)
151  {
152  return vcsn::filter(a, useful_states(a));
153  }
154 
155  /*----------------------------------------------------------------.
156  | is_trim, is_accessible, is_coaccessible, is_empty, is_useless. |
157  `----------------------------------------------------------------*/
158 
160  template <Automaton Aut>
161  bool is_trim(const Aut& a)
162  {
163  return num_useful_states(a) == a->num_states();
164  }
165 
167  template <Automaton Aut>
168  bool is_useless(const Aut& a)
169  {
170  return num_useful_states(a) == 0;
171  }
172 
174  template <Automaton Aut>
175  bool is_accessible(const Aut& a)
176  {
177  return num_accessible_states(a) == a->num_states();
178  }
179 
181  template <Automaton Aut>
182  bool is_coaccessible(const Aut& a)
183  {
184  return num_coaccessible_states(a) == a->num_states();
185  }
186 
187  template <Automaton Aut>
188  bool is_empty(const Aut& a) ATTRIBUTE_PURE;
189 
191  template <Automaton Aut>
192  bool is_empty(const Aut& a)
193  {
194  // FIXME: Beware of the case where there is a transition from
195  // pre() to post().
196  return a->num_states() == 0;
197  }
198 
199  namespace dyn
200  {
201  namespace detail
202  {
204  template <Automaton Aut>
205  automaton
206  accessible(const automaton& aut)
207  {
208  const auto& a = aut->as<Aut>();
210  }
211 
213  template <Automaton Aut>
214  automaton
216  {
217  const auto& a = aut->as<Aut>();
219  }
220 
222  template <Automaton Aut>
223  automaton
224  trim(const automaton& aut)
225  {
226  const auto& a = aut->as<Aut>();
228  }
229 
231  template <Automaton Aut>
232  bool
234  {
235  const auto& a = aut->as<Aut>();
236  return is_accessible(a);
237  }
238 
240  template <Automaton Aut>
241  bool
243  {
244  const auto& a = aut->as<Aut>();
245  return is_coaccessible(a);
246  }
247 
249  template <Automaton Aut>
250  bool
251  is_trim(const automaton& aut)
252  {
253  const auto& a = aut->as<Aut>();
254  return is_trim(a);
255  }
256 
258  template <Automaton Aut>
259  bool
260  is_useless(const automaton& aut)
261  {
262  const auto& a = aut->as<Aut>();
263  return is_useless(a);
264  }
265 
267  template <Automaton Aut>
268  bool
269  is_empty(const automaton& aut)
270  {
271  const auto& a = aut->as<Aut>();
272  return is_empty(a);
273  }
274  }
275  }
276 }
filter_automaton< Aut > trim(const Aut &a)
Useful part of an automaton.
Definition: accessible.hh:150
bool is_trim(const automaton &aut)
Bridge.
Definition: accessible.hh:251
Aut transpose(const transpose_automaton< Aut > &aut)
Definition: transpose.hh:238
std::unordered_set< state_t_of< Aut >> states_t
Definition: accessible.hh:19
bool is_empty(const Aut &a) ATTRIBUTE_PURE
Whether has no states.
Definition: accessible.hh:192
bool is_useless(const Aut &a)
Whether all no state is useful.
Definition: accessible.hh:168
filter_automaton< Aut > accessible(const Aut &a)
Accessible part of an automaton.
Definition: accessible.hh:134
Container set_intersection(const Container &s1, const Container &s2)
The intersection of two sets.
Definition: algorithm.hh:184
automaton trim(const automaton &aut)
Bridge.
Definition: accessible.hh:224
return res
Definition: multiply.hh:398
automaton accessible(const automaton &aut)
Bridge.
Definition: accessible.hh:206
bool is_accessible(const automaton &aut)
Bridge.
Definition: accessible.hh:233
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
automaton coaccessible(const automaton &aut)
Bridge.
Definition: accessible.hh:215
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
Definition: traits.hh:64
Definition: a-star.hh:8
states_t< Aut > coaccessible_states(const Aut &a, bool strict=true)
The set of coaccessible states, including post(), and possibly pre().
Definition: accessible.hh:64
size_t num_accessible_states(const Aut &a)
Number of accessible states, not counting pre() and post().
Definition: accessible.hh:90
A dyn automaton.
Definition: automaton.hh:17
bool is_useless(const automaton &aut)
Bridge.
Definition: accessible.hh:260
filter_automaton< Aut, Trans > filter(const Aut &aut, boost::optional< dynamic_bitset > ss={}, boost::optional< dynamic_bitset > ts={})
Get an automaton who is a part state set ss of aut.
Definition: filter.hh:301
bool is_coaccessible(const automaton &aut)
Bridge.
Definition: accessible.hh:242
bool is_accessible(const Aut &a)
Whether all its states are accessible.
Definition: accessible.hh:175
states_t< Aut > useful_states(const Aut &a, bool strict=true)
The set of useful states, including possibly pre() and post().
Definition: accessible.hh:75
bool is_coaccessible(const Aut &a)
Whether all its states are coaccessible.
Definition: accessible.hh:182
Request the set implementation (bool weights).
size_t num_coaccessible_states(const Aut &a)
Number of accessible states, not counting pre() and post().
Definition: accessible.hh:105
auto & as()
Extract wrapped typed automaton.
Definition: automaton.hh:37
filter_automaton< Aut > coaccessible(const Aut &a)
Coaccessible part of an automaton.
Definition: accessible.hh:142
auto all_out(const Aut &aut, state_t_of< Aut > s)
Indexes of transitions leaving state s.
Definition: automaton.hh:45
states_t< Aut > accessible_states(const Aut &aut, bool strict=true)
The set of accessible states, including pre(), and possibly post().
Definition: accessible.hh:27
bool is_empty(const automaton &aut)
Bridge.
Definition: accessible.hh:269
bool is_trim(const Aut &a)
Whether all its states are useful.
Definition: accessible.hh:161
size_t num_useful_states(const Aut &a)
Number of accessible states, not counting pre() and post().
Definition: accessible.hh:113