Awali
Another Weighted Automata library
abstract_automaton.hh
Go to the documentation of this file.
1 // This file is part of Awali.
2 // Copyright 2016-2021 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 DYN_ABSTRACT_AUTOMATON_HH
18 #define DYN_ABSTRACT_AUTOMATON_HH
19 
20 #include<vector>
21 #include<iostream>
22 #include<string>
23 #include<memory>
24 #include <awali/common/enums.hh>
25 
31 
33 
34 
35 #include<memory>
36 
37 namespace awali { namespace dyn {
38 
69 
71  virtual state_t null_state () const = 0;
72 
76  virtual transition_t null_transition () const = 0;
77 
79  virtual size_t num_states() const = 0;
80 
82  virtual size_t num_initials() const = 0;
83 
85  virtual size_t num_finals() const = 0;
86 
88  virtual size_t num_transitions() const = 0;
89 
93  virtual const std::string& get_name() const = 0;
94 
98  virtual const std::string& get_desc() const = 0;
99 
100 
112  virtual void set_name(const std::string& name) = 0;
113 
120  virtual void set_desc(const std::string& desc) = 0;
121 
125  virtual bool has_state(state_t s) const = 0;
126 
134  virtual bool is_initial(state_t s) const = 0;
135 
143  virtual bool is_final(state_t s) const = 0;
144 
146  virtual weight_t get_initial_weight(state_t s) const = 0;
147 
149  virtual weight_t get_final_weight(state_t s) const = 0;
150 
156  virtual state_t add_state() = 0;
157 
159  virtual state_t add_state(std::string name) = 0;
160 
162  virtual void del_state(state_t s) = 0;
163 
165  virtual void set_initial(state_t s, weight_t w) = 0;
166 
172  virtual void set_initial(state_t s) = 0;
173 
174 
184  virtual weight_t add_initial(state_t s, weight_t w) = 0;
185 
186 
192  virtual void unset_initial(state_t s) = 0;
193 
194 
197  virtual void set_final(state_t s, weight_t w) = 0;
198 
199 
205  virtual void set_final(state_t s) = 0;
206 
207 
218  virtual weight_t add_final(state_t s, weight_t w) = 0;
219 
220 
226  virtual void unset_final(state_t s) = 0;
227 
228 
236  virtual transition_t get_transition(state_t src, state_t dst, label_t label) const = 0;
237 
241  virtual bool has_transition(state_t src, state_t dst, label_t label) const = 0;
244  virtual bool has_transition(transition_t t) const = 0;
245 
247  virtual state_t src_of(transition_t t) const = 0;
248 
250  virtual state_t dst_of(transition_t t) const = 0;
251 
253  virtual label_t label_of(transition_t t) const = 0;
254 
256  virtual std::list<label_t> labels_of(transition_t t) const = 0;
257 
259  virtual label_t label_of(transition_t t, unsigned i) const = 0;
260 
262  virtual weight_t weight_of(transition_t t) const = 0;
263 
265  virtual bool is_eps_transition(transition_t t) const = 0;
266 
267 
282  virtual transition_t set_transition(state_t src, state_t dst,
283  label_t label, weight_t weight) = 0;
284 
296  virtual transition_t set_transition(state_t src, state_t dst, label_t label)
297  = 0;
298 
307  virtual transition_t set_eps_transition(state_t src, state_t dst) = 0;
308 
320  weight_t weight) = 0;
321 
333  virtual weight_t add_transition(state_t src, state_t dst, label_t label,
334  weight_t weight) = 0;
335 
350  virtual weight_t add_transition(state_t src, state_t dst, label_t label)
351  = 0;
352 
361  virtual weight_t add_eps_transition(state_t src, state_t dst) = 0;
362 
373  virtual weight_t add_eps_transition(state_t src, state_t dst,
374  weight_t weight) = 0;
375 
377  virtual weight_t set_weight(transition_t tr, weight_t w) = 0;
378 
380  virtual weight_t add_weight(transition_t tr, weight_t w) = 0;
381 
383  virtual weight_t lmul_weight(transition_t tr, weight_t w) = 0;
384 
386  virtual weight_t rmul_weight(transition_t tr, weight_t we) = 0;
387 
389  virtual void del_transition(transition_t tr) = 0;
390 
392  virtual transition_t del_transition(state_t src, state_t dst,
393  label_t label) = 0;
395  virtual void del_transition(state_t src, state_t dst) = 0;
396 
398  virtual void del_eps_transition(state_t src, state_t dst) = 0;
399 
400 
409  std::vector<state_t> states(options_t opts = {}) const
410  {
411  return internal::states(this, opts[PREPOST_PARADIGM]);
412  }
413 
422  std::vector<transition_t> transitions(options_t opts = {}) const
423  {
424  return internal::transitions(this, opts[PREPOST_PARADIGM]);
425  }
426 
428  virtual std::vector<state_t> initial_states() const = 0;
429 
431  virtual std::vector<state_t> final_states() const = 0;
432 
433 // virtual std::vector<transition_t> final_transitions() const = 0;
434 // virtual std::vector<transition_t> initial_transitions() const = 0;
435 
437  virtual std::vector<state_t> successors(state_t s) const = 0;
438 
440  virtual std::vector<state_t> successors(state_t s, label_t label) const = 0;
441 
443  virtual std::vector<state_t> predecessors(state_t s) const = 0;
444 
447  virtual std::vector<state_t> predecessors(state_t s, label_t label) const = 0;
448 
450  std::vector<transition_t> out(state_t s, options_t opts = {}) const
451  { return outgoing(s, opts); }
452 
454  std::vector<transition_t> out(state_t s, label_t label) const
455  { return outgoing(s, label); }
456 
458  std::vector<transition_t> in(state_t s, options_t opts = {}) const
459  { return incoming(s, opts); }
460 
461 
463  virtual std::vector<transition_t> in(state_t s, label_t label) const
464  {
465  return incoming(s,label);
466  }
467 
469  virtual std::vector<transition_t> outin(state_t src, state_t dst) const = 0;
470 
475  virtual state_t pre() const = 0 ;
476 
482  virtual state_t post() const = 0 ;
483 
484 // virtual std::vector<state_t> all_states() const = 0; //including pre() and post()
485 // virtual std::vector<transition_t> all_transitions() const = 0; // including initial and final
486 // virtual std::vector<transition_t> all_out(state_t s) const = 0; // including final
487 // virtual std::vector<transition_t> all_in(state_t s) const = 0; // including initial
488 
490  virtual std::vector<label_t> alphabet() const = 0;
491 
493  virtual bool is_transducer() const =0;
494 
497  virtual bool is_int_automaton() const =0;
498 
500  virtual bool is_eps_allowed() const = 0;
501 
503  virtual context_t get_context() const = 0;
504 
509  virtual history_kind_t history_kind() const = 0;
510 
511 
518  virtual state_t origin_of(state_t s) const = 0;
519 
520 
527  virtual std::vector<state_t> origins_of(state_t s) const = 0;
528 
530  virtual void strip_history() = 0;
531 
537  virtual std::string get_state_name(state_t s) const =0;
538 
540  virtual bool has_explicit_name(state_t s) const =0;
541 
542 
544  virtual void set_state_name(state_t s, std::string name) =0;
545 
550  virtual state_t get_state_by_name(std::string name) const =0 ;
551 
556  virtual void set_state_names_from_history() =0;
557 
558 
567  std::vector<transition_t> incoming(state_t s, options_t opts = {}) const
568  {
569  return internal::incoming(this, s, opts[PREPOST_PARADIGM]);
570  }
571 
574  virtual std::vector<transition_t> incoming(state_t s, label_t label) const = 0;
575 
584  std::vector<transition_t> outgoing(state_t s, options_t opts = {}) const
585  {
586  return internal::outgoing(this, s, opts[PREPOST_PARADIGM]);
587  }
588 
591  virtual std::vector<transition_t> outgoing(state_t s, label_t label) const = 0;
593  };
594 
595 
596 
597 }
598 }//end of ns awali::dyn
599 
600 #endif
awali::dyn::abstract_automaton_t::dst_of
virtual state_t dst_of(transition_t t) const =0
Returns the destination state of transition t.
awali::dyn::abstract_automaton_t::add_weight
virtual weight_t add_weight(transition_t tr, weight_t w)=0
Adds w to the weight of transition tr.
awali::dyn::abstract_automaton_t::origins_of
virtual std::vector< state_t > origins_of(state_t s) const =0
[experimental] Gives the origin of state s, in the case where it comes from a tuple of states.
awali::dyn::abstract_automaton_t::num_finals
virtual size_t num_finals() const =0
Returns the number of final states in this abstract_automaton_t.
awali
Main namespace of Awali.
Definition: ato.hh:22
awali::dyn::abstract_automaton_t::in
virtual std::vector< transition_t > in(state_t s, label_t label) const
Alias to incoming(state_t,label_t)const.
Definition: abstract_automaton.hh:463
awali::dyn::internal::incoming
std::vector< transition_t > incoming(abstract_automaton_t const *aut, state_t s, bool all)
awali::dyn::abstract_automaton_t::unset_initial
virtual void unset_initial(state_t s)=0
Sets state s as non-initial.
awali::dyn::internal::states
std::vector< state_t > states(abstract_automaton_t const *aut, bool all)
awali::dyn::abstract_automaton_t::out
std::vector< transition_t > out(state_t s, label_t label) const
Alias to outgoing(state_t, label_t)const.
Definition: abstract_automaton.hh:454
awali::dyn::abstract_automaton_t::rmul_weight
virtual weight_t rmul_weight(transition_t tr, weight_t we)=0
Multiplies by w on the right the weight of transition tr.
awali::dyn::abstract_automaton_t::add_final
virtual weight_t add_final(state_t s, weight_t w)=0
Adds some final weight of state s to w (useful only for weighted automata).
awali::dyn::abstract_automaton_t::add_transition
virtual weight_t add_transition(state_t src, state_t dst, label_t label, weight_t weight)=0
Adds a transition going from src to dst, labelled by label and with weight weight; or adds weight to ...
awali::dyn::transition_t
unsigned transition_t
Type representing automata transitions; currently simply identifiers of type unsigned,...
Definition: typedefs.hh:33
awali::dyn::abstract_automaton_t::set_desc
virtual void set_desc(const std::string &desc)=0
Sets the description of this abstract_automaton_t.
awali::dyn::abstract_automaton_t::get_state_by_name
virtual state_t get_state_by_name(std::string name) const =0
Gets one of the state with given name.
awali::dyn::abstract_automaton_t::src_of
virtual state_t src_of(transition_t t) const =0
Returns the source state of transition t.
awali::dyn::abstract_automaton_t::get_desc
virtual const std::string & get_desc() const =0
Return the description of this abstract_automaton_t.
awali::dyn::abstract_automaton_t::null_state
virtual state_t null_state() const =0
Returns the phony state, used for instance when no state is found.
awali::dyn::abstract_automaton_t::outin
virtual std::vector< transition_t > outin(state_t src, state_t dst) const =0
Returns all transitions going from src to dst.
awali::dyn::abstract_automaton_t::successors
virtual std::vector< state_t > successors(state_t s) const =0
Returns the destinations of all transitions going out of s.
context_description.hh
awali::dyn::any_t
Structure used to erase the type of labels/weights at the dyn layer.
Definition: any.hh:53
awali::dyn::abstract_automaton_t::num_states
virtual size_t num_states() const =0
Returns the number of states in this abstract_automaton_t.
awali::dyn::abstract_automaton_t::num_initials
virtual size_t num_initials() const =0
Returns the number of initial states in this abstract_automaton_t.
awali::dyn::internal::transitions
std::vector< transition_t > transitions(abstract_automaton_t const *aut, bool all)
awali::dyn::abstract_automaton_t::add_eps_transition
virtual weight_t add_eps_transition(state_t src, state_t dst)=0
Adds an epsilon transition going from src to dst.
awali::dyn::label_t
any_t label_t
Type for (transition) labels; it is an alias to any_t since its precise type depends on the weightset...
Definition: typedefs.hh:48
awali::dyn::abstract_automaton_t::set_eps_transition
virtual transition_t set_eps_transition(state_t src, state_t dst)=0
Sets an epsilon transition going from src to dst.
awali::dyn::abstract_automaton_t::lmul_weight
virtual weight_t lmul_weight(transition_t tr, weight_t w)=0
Multiplies by w on the left the weight of transition tr.
awali::dyn::abstract_automaton_t::origin_of
virtual state_t origin_of(state_t s) const =0
[experimental] Gives the the origin of state s, in the case where it comes from a single state.
awali::dyn::abstract_automaton_t::weight_of
virtual weight_t weight_of(transition_t t) const =0
Returns the weight of transition t.
awali::dyn::abstract_automaton_t::add_state
virtual state_t add_state()=0
Adds a new isolated states.
awali::dyn::abstract_automaton_t::final_states
virtual std::vector< state_t > final_states() const =0
Returns the final states of this abstract_automaton_t.
options.hh
awali::dyn::abstract_automaton_t::is_eps_transition
virtual bool is_eps_transition(transition_t t) const =0
Returns true if transition t is an epsilon-transition.
awali::dyn::abstract_automaton_t::get_name
virtual const std::string & get_name() const =0
Return the name of this abstract_automaton_t.
awali::dyn::abstract_automaton_t::initial_states
virtual std::vector< state_t > initial_states() const =0
Returns the initial states of this abstract_automaton_t.
awali::state_t
unsigned state_t
Definition: types.hh:21
awali::dyn::abstract_automaton_t::get_state_name
virtual std::string get_state_name(state_t s) const =0
Gets the name of state s.
awali::dyn::context_t
Dynamical wrapper for a context, that is a weightset and a labelset.
Definition: context.hh:41
awali::dyn::abstract_automaton_t::unset_final
virtual void unset_final(state_t s)=0
Sets state s as non-final.
awali::dyn::abstract_automaton_t::set_state_name
virtual void set_state_name(state_t s, std::string name)=0
Sets to name the name of s.
awali::dyn::abstract_automaton_t::transitions
std::vector< transition_t > transitions(options_t opts={}) const
Returns the transitions in this abstract_automaton_t.
Definition: abstract_automaton.hh:422
awali::dyn::abstract_automaton_t::history_kind
virtual history_kind_t history_kind() const =0
[experimental] Gives the kind of data this abstract_automaton_t comes from.
awali::dyn::abstract_automaton_t::del_transition
virtual void del_transition(transition_t tr)=0
Deletes transition tr.
awali::dyn::abstract_automaton_t::get_final_weight
virtual weight_t get_final_weight(state_t s) const =0
Gets the final weight of s.
awali::dyn::abstract_automaton_t::set_transition
virtual transition_t set_transition(state_t src, state_t dst, label_t label, weight_t weight)=0
Sets (and possibly replaces) a transition going from src to dst, labelled by label and with weight we...
awali::dyn::abstract_automaton_t::del_state
virtual void del_state(state_t s)=0
Deletes state s from this abstract_automaton_t.
enums.hh
awali::dyn::abstract_automaton_t::set_name
virtual void set_name(const std::string &name)=0
Sets the name of this abstract_automaton_t.
awali::dyn::abstract_automaton_t::has_transition
virtual bool has_transition(state_t src, state_t dst, label_t label) const =0
Returns true if there is a transition going from state src to state dst and labelled by label.
awali::dyn::abstract_automaton_t::get_context
virtual context_t get_context() const =0
Gets the context of this abstract_automaton_t.
awali::dyn::abstract_automaton_t::~abstract_automaton_t
virtual ~abstract_automaton_t()
Definition: abstract_automaton.hh:592
awali::dyn::abstract_automaton_t::set_weight
virtual weight_t set_weight(transition_t tr, weight_t w)=0
Sets to w the weight of transition tr.
awali::history_kind_t
history_kind_t
The different kinds of history.
Definition: enums.hh:176
awali::dyn::abstract_automaton_t::alphabet
virtual std::vector< label_t > alphabet() const =0
Return the alphabet of this abstract_automaton_t.
awali::dyn::abstract_automaton_t::in
std::vector< transition_t > in(state_t s, options_t opts={}) const
Alias to incoming.
Definition: abstract_automaton.hh:458
awali::dyn::abstract_automaton_t::is_transducer
virtual bool is_transducer() const =0
Returns true if this abstract_automaton_t has multiple tapes.
awali::dyn::abstract_automaton_t::has_explicit_name
virtual bool has_explicit_name(state_t s) const =0
Returns true if state s has a name set.
awali::dyn::state_t
unsigned state_t
Type representing automata states; currently simply identifiers of type unsigned, but this might chan...
Definition: typedefs.hh:28
awali::dyn::abstract_automaton_t::is_initial
virtual bool is_initial(state_t s) const =0
Returns true if given state s is initial in this abstract_automaton_t.
awali::dyn::options_t
An options_t is a set of optional parameters that is passed on to called functions.
Definition: options.hh:86
awali::dyn::abstract_automaton_t::strip_history
virtual void strip_history()=0
Deletes all state history.
context.hh
awali::dyn::abstract_automaton_t::outgoing
std::vector< transition_t > outgoing(state_t s, options_t opts={}) const
Returns the transitions going out ofstate s.
Definition: abstract_automaton.hh:584
qfraction.hh
context.hh
awali::dyn::PREPOST_PARADIGM
internal::option_t< bool > PREPOST_PARADIGM
Option used to specify whether to consider initial/final status of states as normal transitions.
awali::dyn::abstract_automaton_t::is_final
virtual bool is_final(state_t s) const =0
Returns true if given state s is final in this abstract_automaton_t.
awali::dyn::abstract_automaton_t::out
std::vector< transition_t > out(state_t s, options_t opts={}) const
Alias to outgoing.
Definition: abstract_automaton.hh:450
awali::dyn::abstract_automaton_t::is_int_automaton
virtual bool is_int_automaton() const =0
Returns true if the labelset of this abstract_automaton_t is Z.
awali::dyn::internal::outgoing
std::vector< transition_t > outgoing(abstract_automaton_t const *aut, state_t s, bool all)
awali::dyn::abstract_automaton_t::get_initial_weight
virtual weight_t get_initial_weight(state_t s) const =0
Gets the initial weight of s.
awali::dyn::abstract_automaton_t::add_initial
virtual weight_t add_initial(state_t s, weight_t w)=0
Adds some initial weight of state s to w (useful only for weighted automata).
awali::dyn::abstract_automaton_t::has_state
virtual bool has_state(state_t s) const =0
Returns true if this abstract_automaton_t contains state s.
awali::dyn::abstract_automaton_t::label_of
virtual label_t label_of(transition_t t) const =0
Returns the label of transition t.
awali::dyn::abstract_automaton_t::states
std::vector< state_t > states(options_t opts={}) const
Returns the states of this abstract_automaton_t.
Definition: abstract_automaton.hh:409
awali::dyn::abstract_automaton_t::pre
virtual state_t pre() const =0
Returns the preinitial state.
awali::dyn::abstract_automaton_t::predecessors
virtual std::vector< state_t > predecessors(state_t s) const =0
Returns the sources of all transitions coming in state s.
awali::dyn::abstract_automaton_t::num_transitions
virtual size_t num_transitions() const =0
Returns the number of transitions in this abstract_automaton_t.
awali::dyn::abstract_automaton_t::null_transition
virtual transition_t null_transition() const =0
Returns the phony transition_t, used for instance when transition is found.
typedefs.hh
awali::dyn::abstract_automaton_t::set_initial
virtual void set_initial(state_t s, weight_t w)=0
Sets initial weight of state s to w (useful only for weightset automata).
awali::dyn::abstract_automaton_t::is_eps_allowed
virtual bool is_eps_allowed() const =0
Returns true if epsilon transitions are allowed.
awali::dyn::abstract_automaton_t::incoming
std::vector< transition_t > incoming(state_t s, options_t opts={}) const
Returns the transitions coming in state s.
Definition: abstract_automaton.hh:567
awali::dyn::abstract_automaton_t::set_final
virtual void set_final(state_t s, weight_t w)=0
Sets final weight of state s to w (useful only for weightset automata).
awali::dyn::abstract_automaton_t::del_eps_transition
virtual void del_eps_transition(state_t src, state_t dst)=0
Deletes the epsilon transition going from state src to state dst.
awali::dyn::abstract_automaton_t
Abstract interface listing the services provided by automata at the dynamical layer.
Definition: abstract_automaton.hh:68
awali::dyn::abstract_automaton_t::set_state_names_from_history
virtual void set_state_names_from_history()=0
[experimental] Sets the name of each state based on its history.
awali::dyn::abstract_automaton_t::labels_of
virtual std::list< label_t > labels_of(transition_t t) const =0
Returns the label of all tapes on the transition t (transducers only).
awali::dyn::abstract_automaton_t::get_transition
virtual transition_t get_transition(state_t src, state_t dst, label_t label) const =0
Gets the transition identifier going from state src to state dst and labelled by label.
awali::dyn::abstract_automaton_t::post
virtual state_t post() const =0
Returns the postfinal state.