Awali
Another Weighted Automata library
allow_words.hh
Go to the documentation of this file.
1 // This file is part of Awali.
2 // Copyright 2016-2022 Sylvain Lombardy, Victor Marsault, Jacques Sakarovitch
3 //
4 // Awali is a free software: you can redistribute it and/or modify
5 // it under the terms of the GNU General Public License as published by
6 // the Free Software Foundation, either version 3 of the License, or
7 // (at your option) any later version.
8 //
9 // This program is distributed in the hope that it will be useful,
10 // but WITHOUT ANY WARRANTY; without even the implied warranty of
11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 // GNU General Public License for more details.
13 //
14 // You should have received a copy of the GNU General Public License
15 // along with this program. If not, see <http://www.gnu.org/licenses/>.
16 
17 #ifndef AWALI_ALGOS_ALLOW_WORDS_HH
18 #define AWALI_ALGOS_ALLOW_WORDS_HH
19 
22 #include <awali/sttc/misc/add_epsilon_trans.hh> // is_epsilon
23 #include <awali/sttc/algos/copy.hh>
24 #include<unordered_map>
25 
26 /*
27  Convert a lal automaton into a law automaton.
28 */
29 
30 namespace awali {
31  namespace sttc
32  {
33  namespace internal {
34  template <typename Aut>
35  struct allowworder {
36  using automaton_t = Aut;
42 
43  static ret_automaton_t allow_words(const automaton_t& aut, bool keep_history) {
44  const auto &labelset=*aut->context().labelset();
45  wordset_t wordset = get_wordset(labelset);
46  auto ret= make_mutable_automaton(ret_context_t{wordset,*aut->context().weightset()});
47  std::unordered_map<state_t,state_t> state_map;
48  for(auto s : aut->states()) {
49  state_map[s]=ret->add_state();
50  }
51  state_map[ret->pre()]=aut->pre();
52  state_map[ret->post()]=aut->post();
53  for(auto tr: aut->all_transitions()) {
54  const auto& w=aut->label_of(tr);
55  if(labelset.is_special(w))
56  ret->new_transition(state_map[aut->src_of(tr)], state_map[aut->dst_of(tr)], wordset.special(), aut->weight_of(tr));
57  else if(labelset.is_one(w))
58  ret->new_transition(state_map[aut->src_of(tr)], state_map[aut->dst_of(tr)], wordset.one(), aut->weight_of(tr));
59  else
60  ret->new_transition(state_map[aut->src_of(tr)], state_map[aut->dst_of(tr)], wordset.word(w), aut->weight_of(tr));
61  }
62  if(keep_history) {
63  auto history = std::make_shared<single_history<Aut>>(aut);
64  ret->set_history(history);
65  for (auto p: aut->all_states()) {
66  history->add_state(state_map[p], p);
67  if(aut->has_name(p)) {
68  ret->set_state_name(state_map[p], aut->get_state_name(p));
69  }
70  }
71  }
72  return ret;
73  }
74  };
75  }//end of internal
76 
88  template<typename Aut>
89  auto allow_words(const Aut& aut, bool keep_history=true) -> typename internal::allowworder<Aut>::ret_automaton_t {
90  return internal::allowworder<Aut>::allow_words(aut, keep_history);
91  }
92 
103  template<typename Aut>
104  void compact_here(Aut& aut) {
105  auto& ws=*aut->context().weightset();
106  for(auto s: aut->states()) {
107  if(aut->is_initial(s) || aut->is_final(s))
108  continue;
109  int ci=0,co=0;
110  transition_t tri,tro;
111  for(auto tria: aut->all_in(s)) {
112  ci++;
113  tri=tria;
114  if(ci>1)
115  break;
116  for(auto troa: aut->all_out(s)) {
117  co++;
118  tro=troa;
119  if(co>1)
120  break;
121  }
122  }
123  if(ci==1 && co==1) {
124  aut->add_transition(aut->src_of(tri),aut->dst_of(tro),aut->label_of(tri)+aut->label_of(tro),ws.mul(aut->weight_of(tri),aut->weight_of(tro)));
125  aut->del_state(s);
126  }
127  }
128  }
129 
140  template <typename Aut>
141  auto
142  compact(const Aut& aut, bool keep_history=true) -> typename internal::allowworder<Aut>::ret_automaton_t
143  {
144  auto ret=allow_words(aut, keep_history);
145  compact_here(ret);
146  return ret;
147  }
148  }
149 }
150 
151 #endif
carries the algebraic settings of automata
Definition: context.hh:40
Implementation of labels are words.
Definition: wordset.hh:35
static value_t one()
Definition: wordset.hh:211
static value_t special()
Definition: wordset.hh:172
word_t word(const value_t &v) const
Convert to a word.
Definition: wordset.hh:106
weightset_description weightset(const std::string &k)
labelset_description wordset(std::string const &s)
auto compact(const Aut &aut, bool keep_history=true) -> typename internal::allowworder< Aut >::ret_automaton_t
Compacts non branching paths.
Definition: allow_words.hh:142
void compact_here(Aut &aut)
Compacts non branching paths.
Definition: allow_words.hh:104
auto allow_words(const Aut &aut, bool keep_history=true) -> typename internal::allowworder< Aut >::ret_automaton_t
Turns the automaton into an automaton labeled with words.
Definition: allow_words.hh:89
typename internal::labelset_t_of_impl< internal::base_t< ValueSet > >::type labelset_t_of
Helper to retrieve the type of the labelset of a value set.
Definition: traits.hh:76
auto get_wordset(const L &labelset) -> typename labelset_trait< L >::wordset_t
Definition: traits.hh:232
mutable_automaton< Context > make_mutable_automaton(const Context &ctx)
Definition: mutable_automaton.hh:915
std::shared_ptr< internal::mutable_automaton_impl< Context > > mutable_automaton
Definition: mutable_automaton.hh:45
typename internal::weightset_t_of_impl< internal::base_t< ValueSet > >::type weightset_t_of
Helper to retrieve the type of the weightset of a value set.
Definition: traits.hh:86
Main namespace of Awali.
Definition: ato.hh:22
unsigned transition_t
Definition: types.hh:22
Definition: allow_words.hh:35
typename labelset_trait< labelset_t >::wordset_t wordset_t
Definition: allow_words.hh:39
static ret_automaton_t allow_words(const automaton_t &aut, bool keep_history)
Definition: allow_words.hh:43
weightset_t_of< Aut > weightset_t
Definition: allow_words.hh:38
mutable_automaton< ret_context_t > ret_automaton_t
Definition: allow_words.hh:41
labelset_t_of< Aut > labelset_t
Definition: allow_words.hh:37
Aut automaton_t
Definition: allow_words.hh:36
L wordset_t
Definition: traits.hh:38