Vcsn  2.2a
Be Rational
is-partial-identity.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <queue>
4 #include <utility>
5 
7 #include <vcsn/dyn/automaton.hh>
8 #include <vcsn/dyn/fwd.hh>
11 
12 namespace vcsn
13 {
14 
20  template <Automaton Aut>
21  bool is_partial_identity(const Aut& aut)
22  {
23  using state_t = state_t_of<Aut>;
24  using labelset_t = labelset_t_of<Aut>;
25 
27  using wordset_t = detail::law_t<labelset_t>;
28  using word_t = typename wordset_t::value_t;
29  wordset_t ls = make_wordset(*aut->labelset());
31  auto ls1 = ls.template set<0>();
34  std::unordered_map<state_t, word_t> rs;
35 
36  auto coaccessibles = coaccessible_states(aut);
37  std::queue<state_t> todo;
38  auto pre = aut->pre();
39  todo.push(pre);
40  rs.emplace(pre, ls.one());
41  // When reaching the final state, there must be no residue.
42  // Instead of checking this case especially, just make sure
43  // that when we reach post, we only collected (\e, \e).
44  rs.emplace(aut->post(), ls.one());
45 
46  while (!todo.empty())
47  {
48  auto s = todo.front();
49  todo.pop();
50  for (auto t : all_out(aut, s))
51  {
52  auto dst = aut->dst_of(t);
53  if (has(coaccessibles, dst))
54  {
55  // Compute the new residue.
56  auto r = ls.mul(rs[s], aut->label_of(t));
57  // Eliminate longest common prefix.
58  ls.lnormalize_here(r);
59  if (!has(rs, dst))
60  {
61  rs.emplace(dst, r);
62  todo.emplace(dst);
63  }
64  else if (!ls.equal(r, rs[dst]))
65  {
66  return false;
67  }
68  }
69  }
70  }
71  return true;
72  }
73 
74  namespace dyn
75  {
76  namespace detail
77  {
79  template <Automaton Aut>
80  bool is_partial_identity(const automaton& aut)
81  {
82  return is_partial_identity(aut->as<Aut>());
83  }
84  }
85  }
86 }
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
Provide a variadic mul on top of a binary mul(), and one().
Definition: fwd.hh:46
typename law_traits< LabelSet >::type law_t
The smallest wordset that includes LabelSet.
Definition: labelset.hh:264
A dyn automaton.
Definition: automaton.hh:19
law_t< LabelSet > make_wordset(const LabelSet &ls)
The wordset of a labelset.
Definition: labelset.hh:269
bool is_partial_identity(const automaton &aut)
Bridge.
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_out(const Aut &aut, state_t_of< Aut > s)
Indexes of transitions leaving state s.
Definition: automaton.hh:37
auto rs
Definition: lift.hh:151
bool is_partial_identity(const Aut &aut)
Whether transducer aut is equivalent to a partial identity function on all successful paths...
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
Definition: traits.hh:56
auto & as()
Extract wrapped typed automaton.
Definition: automaton.hh:39
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
Definition: traits.hh:55
value_t mul(const Ts &...ts) const
A variadic multiplication.
Definition: weightset.hh:36
Definition: a-star.hh:8