Awali
Another Weighted Automata library
add_path.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_ADD_PATH_HH
18 # define AWALI_ALGOS_ADD_PATH_HH
19 
25 #include <awali/sttc/labelset/traits.hh> // ratexpset_of
26 
27 namespace awali {
28  namespace sttc {
29 
30  /*,---------------------------.
31  | add_path(aut, p, q, exp). |
32  `---------------------------'*/
57  template <typename Aut>
58  auto add_path(Aut& aut, state_t p, state_t q, const typename context_t_of<Aut>::ratexp_t& exp)
59  -> typename std::enable_if<!labelset_t_of<Aut>::has_one(),void>::type {
60  const auto& ws = *aut->weightset();
61  auto ste = standard<Aut>(aut->context(), exp);
62  state_t ste_init = ste->dst_of(*(ste->initial_transitions().begin()));
63  require(!ste->is_final(ste_init),__func__," : proper series required");
64  std::unordered_map<state_t,state_t> map;
65  for(auto s : ste->states())
66  if(s!=ste_init)
67  map[s]=aut->add_state();
68  else
69  map[s]=p;
70  for(auto tr : ste->transitions())
71  aut->new_transition(map[ste->src_of(tr)],
72  map[ste->dst_of(tr)],
73  ste->label_of(tr),
74  ste->weight_of(tr));
75  for(auto ftr : ste->final_transitions()) {
76  auto sq=ste->src_of(ftr);
77  for(auto tr : ste->in(sq)) {
78  auto sp=ste->src_of(tr);
79  aut->add_transition(map[sp], q, ste->label_of(tr), ws.mul(ste->weight_of(tr),ste->weight_of(ftr)));
80  }
81  }
82  for(auto ftr : ste->final_transitions()) {
83  auto sq=ste->src_of(ftr);
84  if(sq!=ste_init) {
85  auto outit = ste->out(sq);
86  if(outit.begin()==outit.end())
87  aut->del_state(map[sq]);
88  }
89  }
90  }
91 
92  template <typename Aut>
93  auto add_path(Aut& aut, state_t p, state_t q, const typename context_t_of<Aut>::ratexp_t& exp)
94  -> typename std::enable_if<labelset_t_of<Aut>::has_one(),void>::type
95  {
96  auto ste = compact_thompson<Aut>(aut->context(), exp);
97  std::unordered_map<state_t,state_t> map;
98  state_t ste_init = ste->dst_of(*(ste->initial_transitions().begin()));
99  state_t ste_fin = ste->src_of(*(ste->final_transitions().begin()));
100  for(auto s : ste->states())
101  if(s==ste_init)
102  map[s]=p;
103  else if(s==ste_fin)
104  map[s]=q;
105  else
106  map[s]=aut->add_state();
107  for(auto tr : ste->transitions())
108  aut->add_transition(map[ste->src_of(tr)],
109  map[ste->dst_of(tr)],
110  ste->label_of(tr),
111  ste->weight_of(tr));
112  }
113 
133  template <typename Aut>
134  void add_path(Aut& aut, state_t p, state_t q, const std::string& s, bool strict_alphabet=true) {
135  auto rs=ratexpset_of<context_t_of<Aut>>(get_rat_context(aut->context()),
137  add_path(aut, p, q, parse_exp(rs, s, true, strict_alphabet));
138  }
139  }
140 }
141 
142 #endif // !AWALI_ALGOS_ADD_PATH_HH
The semiring of rational numbers.
Definition: q.hh:42
static value_t mul(const value_t l, const value_t r)
Definition: q.hh:95
auto map(const std::tuple< Ts... > &ts, Fun f) -> decltype(map_tuple_(f, ts, make_index_sequence< sizeof...(Ts)>()))
Map a function on a tuple, return tuple of the results.
Definition: tuple.hh:134
@ associativity
Trivial identities only + associativity.
auto add_path(Aut &aut, state_t p, state_t q, const typename context_t_of< Aut >::ratexp_t &exp) -> typename std::enable_if<!labelset_t_of< Aut >::has_one(), void >::type
adds a subautomaton realizing the series exp between states p and q of aut.
Definition: add_path.hh:58
RatExpSet::ratexp_t parse_exp(const RatExpSet &ratexpset, const std::string &s, bool check_complete=true, bool strict_alphabet=true)
parser of rational expressions
Definition: exp_parser.hh:438
typename internal::context_t_of_impl< internal::base_t< ValueSet > >::type context_t_of
Helper to retrieve the type of the context of a value set.
Definition: traits.hh:66
void require(bool b, Args &&... args)
If b is not verified, raise an error with args as message.
Definition: raise.hh:55
ratexp_context_of< Context > get_rat_context(const Context &ctx)
Definition: traits.hh:295
Main namespace of Awali.
Definition: ato.hh:22
unsigned state_t
Definition: types.hh:21
Provide a variadic mul on top of a binary mul(), and one().
Definition: weightset.hh:38