spot  2.12.2
reachiter.hh
1 // -*- coding: utf-8 -*-
2 // Copyright (C) by the Spot authors, see the AUTHORS file for details.
3 //
4 // This file is part of Spot, a model checking library.
5 //
6 // Spot is free software; you can redistribute it and/or modify it
7 // under the terms of the GNU General Public License as published by
8 // the Free Software Foundation; either version 3 of the License, or
9 // (at your option) any later version.
10 //
11 // Spot is distributed in the hope that it will be useful, but WITHOUT
12 // ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
13 // or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
14 // License for more details.
15 //
16 // You should have received a copy of the GNU General Public License
17 // along with this program. If not, see <http://www.gnu.org/licenses/>.
18 
19 #pragma once
20 
21 #include <spot/misc/hash.hh>
22 #include <spot/twa/twa.hh>
23 #include <stack>
24 #include <deque>
25 
26 namespace spot
27 {
30  class SPOT_API twa_reachable_iterator
31  {
32  public:
33  twa_reachable_iterator(const const_twa_ptr& a);
34  virtual ~twa_reachable_iterator();
35 
41  virtual void run();
42 
50  virtual void add_state(const state* s) = 0;
52  virtual const state* next_state() = 0;
54 
57  virtual bool want_state(const state* s) const;
58 
60  virtual void start();
62  virtual void end();
63 
69  virtual void process_state(const state* s, int n, twa_succ_iterator* si);
82  virtual void process_link(const state* in_s, int in,
83  const state* out_s, int out,
84  const twa_succ_iterator* si);
85 
86  protected:
87  const_twa_ptr aut_;
88 
90  };
91 
97  {
98  public:
99  twa_reachable_iterator_breadth_first(const const_twa_ptr& a);
100 
101  virtual void add_state(const state* s) override;
102  virtual const state* next_state() override;
103 
104  protected:
105  std::deque<const state*> todo;
106  };
107 
111  {
112  public:
113  twa_reachable_iterator_depth_first(const const_twa_ptr& a);
115 
121  virtual void run();
122 
125  virtual bool want_state(const state* s) const;
126 
128  virtual void start();
130  virtual void end();
131 
137  virtual void process_state(const state* s, int n, twa_succ_iterator* si);
150  virtual void process_link(const state* in_s, int in,
151  const state* out_s, int out,
152  const twa_succ_iterator* si);
153 
154  protected:
155  const_twa_ptr aut_;
156 
158  struct stack_item
159  {
160  const state* src;
161  int src_n;
162  twa_succ_iterator* it;
163  };
164  std::deque<stack_item> todo;
165 
167  virtual void push(const state* s, int sn);
169  virtual void pop();
170  };
171 
179  {
180  public:
181  twa_reachable_iterator_depth_first_stack(const const_twa_ptr& a);
186  bool on_stack(int sn) const;
187  protected:
188  virtual void push(const state* s, int sn) override;
189  virtual void pop() override;
190 
191  std::unordered_set<int> stack_;
192  };
193 }
Abstract class for states.
Definition: twa.hh:47
An implementation of spot::twa_reachable_iterator that browses states breadth first.
Definition: reachiter.hh:97
virtual void add_state(const state *s) override
Called by run() to obtain the next state to process.
virtual const state * next_state() override
Called by run() to obtain the next state to process.
std::deque< const state * > todo
A queue of states yet to explore.
Definition: reachiter.hh:105
Iterate over all states of an automaton using a DFS.
Definition: reachiter.hh:179
virtual void pop() override
Pop the DFS stack.
bool on_stack(int sn) const
Whether state sn is on the DFS stack.
virtual void push(const state *s, int sn) override
Push a new state in todo.
Iterate over all states of an automaton using a DFS.
Definition: reachiter.hh:111
virtual void push(const state *s, int sn)
Push a new state in todo.
virtual void pop()
Pop the DFS stack.
virtual void run()
Iterate over all reachable states of a spot::tgba.
virtual void process_state(const state *s, int n, twa_succ_iterator *si)
virtual bool want_state(const state *s) const
virtual void process_link(const state *in_s, int in, const state *out_s, int out, const twa_succ_iterator *si)
virtual void end()
Called by run() once all states have been explored.
const_twa_ptr aut_
The spot::tgba to explore.
Definition: reachiter.hh:155
state_map< int > seen
States already seen.
Definition: reachiter.hh:157
std::deque< stack_item > todo
the DFS stack
Definition: reachiter.hh:164
virtual void start()
Called by run() before starting its iteration.
Iterate over all reachable states of a spot::tgba.
Definition: reachiter.hh:31
state_map< int > seen
States already seen.
Definition: reachiter.hh:89
virtual void process_state(const state *s, int n, twa_succ_iterator *si)
virtual void process_link(const state *in_s, int in, const state *out_s, int out, const twa_succ_iterator *si)
virtual void add_state(const state *s)=0
Called by run() to obtain the next state to process.
virtual void end()
Called by run() once all states have been explored.
virtual void run()
Iterate over all reachable states of a spot::tgba.
virtual void start()
Called by run() before starting its iteration.
virtual bool want_state(const state *s) const
virtual const state * next_state()=0
Called by run() to obtain the next state to process.
const_twa_ptr aut_
The spot::tgba to explore.
Definition: reachiter.hh:87
Iterate over the successors of a state.
Definition: twa.hh:394
Definition: automata.hh:26
std::unordered_map< const state *, val, state_ptr_hash, state_ptr_equal > state_map
Unordered map of abstract states.
Definition: twa.hh:193

Please direct any question, comment, or bug report to the Spot mailing list at spot@lrde.epita.fr.
Generated on Fri Feb 27 2015 10:00:07 for spot by doxygen 1.9.1