Vcsn  2.4
Be Rational
is-acyclic.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <unordered_map>
4 
5 #include <boost/optional.hpp>
6 
7 #include <vcsn/ctx/traits.hh>
9 #include <vcsn/misc/builtins.hh>
10 #include <vcsn/dyn/automaton.hh>
11 #include <vcsn/core/fwd.hh>
12 
13 namespace vcsn
14 {
15  namespace detail
16  {
17 
19  template <Automaton Aut>
21  {
22  public:
23  using automaton_t = std::remove_cv_t<Aut>;
26 
28  boost::optional<label_t> label = {})
29  : aut_(aut)
30  , one_(label)
31  {}
32 
34  bool operator()()
35  {
36  for (auto s : aut_->states())
37  if (has_circuit_(s))
38  return false;
39  return true;
40  }
41 
42  private:
45  {
46  auto it = tag_.find(s);
47  if (it == tag_.end())
48  {
49  tag_[s] = unknown;
50  // Code duplication because `out(aut_, s, *one)` and
51  // `out(aut_, s)` have different return types.
52  if (one_)
53  {
54  for (auto t : out(aut_, s, *one_))
55  if ((aut_->dst_of(t) == s && aut_->label_of(t) == *one_)
56  || has_circuit_(aut_->dst_of(t)))
57  {
58  tag_[s] = circuit;
59  return true;
60  }
61  }
62  else
63  {
64  for (auto t : out(aut_, s))
65  if (aut_->dst_of(t) == s || has_circuit_(aut_->dst_of(t)))
66  {
67  tag_[s] = circuit;
68  return true;
69  }
70  }
71  tag_[s] = ok;
72  return false;
73  }
74 
75  // Switch with respect to tag_[s].
76  switch (it->second)
77  {
78  case unknown:
79  // s is reached while we are exploring successors of s:
80  // there is a circuit.
81  tag_[s] = circuit;
82  return true;
83  case ok:
84  // Otherwise the graph reachable from s has already been explored.
85  return false;
86  case circuit:
87  return true;
88  }
90  }
91 
92  enum status
93  {
97  ok,
100  };
101 
102  // States not in the map have not been reached yet.
103  std::unordered_map<state_t, status> tag_;
104 
106  boost::optional<label_t> one_;
107  };
108  }
109 
113  template <Automaton Aut>
114  ATTRIBUTE_CONST
115  std::enable_if_t<context_t_of<Aut>::has_one(), bool>
116  is_eps_acyclic(const Aut& aut)
117  {
118  auto is_acyclic = detail::is_acyclic_impl<Aut>{aut, aut->labelset()->one()};
119  return is_acyclic();
120  }
121 
122  template <Automaton Aut>
123  ATTRIBUTE_CONST
124  std::enable_if_t<!context_t_of<Aut>::has_one(), bool>
125  is_eps_acyclic(const Aut&)
126  {
127  return true;
128  }
129 
130  template <Automaton Aut>
131  ATTRIBUTE_CONST
132  bool
133  is_acyclic(const Aut& aut)
134  {
136  return is_acyclic();
137  }
138 
139  namespace dyn
140  {
141  namespace detail
142  {
144  template <Automaton Aut>
145  bool is_eps_acyclic(const automaton& aut)
146  {
147  return is_eps_acyclic(aut->as<Aut>());
148  }
149  }
150  }
151 } // namespace vcsn
std::unordered_map< state_t, status > tag_
Definition: is-acyclic.hh:103
bool is_eps_acyclic(const automaton &aut)
Bridge.
Definition: is-acyclic.hh:145
is_acyclic_impl(const automaton_t &aut, boost::optional< label_t > label={})
Definition: is-acyclic.hh:27
typename detail::label_t_of_impl< base_t< ValueSet >>::type label_t_of
Definition: traits.hh:62
ATTRIBUTE_CONST std::enable_if_t< context_t_of< Aut >::has_one(), bool > is_eps_acyclic(const Aut &aut)
Detect epsilon-circuits.
Definition: is-acyclic.hh:116
There is no circuit accessible from s.
Definition: is-acyclic.hh:97
Definition: a-star.hh:8
auto out(const Aut &aut, state_t_of< Aut > s)
Indexes of visible transitions leaving state s.
Definition: automaton.hh:85
bool has_circuit_(state_t s)
Return true if an circuit is accessible from s.
Definition: is-acyclic.hh:44
std::remove_cv_t< Aut > automaton_t
Definition: is-acyclic.hh:23
label_t_of< automaton_t > label_t
Definition: is-acyclic.hh:25
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
Definition: traits.hh:64
A dyn automaton.
Definition: automaton.hh:17
#define BUILTIN_UNREACHABLE()
Definition: builtins.hh:13
The graph reachable from s is under exploration.
Definition: is-acyclic.hh:95
There is an circuit accessible from s.
Definition: is-acyclic.hh:99
value_impl< detail::label_tag > label
Definition: fwd.hh:26
bool operator()()
Whether the automaton is acyclic.
Definition: is-acyclic.hh:34
auto & as()
Extract wrapped typed automaton.
Definition: automaton.hh:37
state_t_of< automaton_t > state_t
Definition: is-acyclic.hh:24
boost::optional< label_t > one_
Definition: is-acyclic.hh:106
ATTRIBUTE_CONST bool is_acyclic(const Aut &aut)
Definition: is-acyclic.hh:133