22 #include <spot/misc/common.hh>
24 #include <type_traits>
30 #include <type_traits>
34 template <
typename State_Data,
typename Edge_Data,
bool Alternating = false>
40 template <
typename Of,
typename ...Args>
43 static const bool value =
false;
46 template <
typename Of,
typename Arg1,
typename ...Args>
49 static const bool value =
50 std::is_base_of<Of, typename std::decay<Arg1>::type>::value;
60 template <typename Data, bool boxed = !std::is_class<Data>::value>
67 template <
typename... Args,
68 typename =
typename std::enable_if<
70 boxed_label(Args&&... args)
71 noexcept(std::is_nothrow_constructible<Data, Args...>::value)
72 : label{std::forward<Args>(args)...}
79 explicit boxed_label()
80 noexcept(std::is_nothrow_constructible<Data>::value)
89 const Data& data()
const
94 bool operator<(
const boxed_label& other)
const
96 return label < other.label;
103 typedef std::tuple<> data_t;
109 const std::tuple<>& data()
const
116 template <
typename Data>
122 template <
typename... Args,
123 typename =
typename std::enable_if<
125 boxed_label(Args&&... args)
126 noexcept(std::is_nothrow_constructible<Data, Args...>::value)
127 : Data{std::forward<Args>(args)...}
134 explicit boxed_label()
135 noexcept(std::is_nothrow_constructible<Data>::value)
144 const Data& data()
const
157 template <
typename Edge,
typename State_Data>
164 template <
typename... Args,
165 typename =
typename std::enable_if<
167 distate_storage(Args&&... args)
168 noexcept(std::is_nothrow_constructible<State_Data, Args...>::value)
169 : State_Data{std::forward<Args>(args)...}
181 template <
typename StateIn,
182 typename StateOut,
typename Edge,
typename Edge_Data>
193 noexcept(std::is_nothrow_constructible<Edge_Data>::value)
199 template <
typename... Args>
201 StateIn src, Args&&... args)
202 noexcept(std::is_nothrow_constructible<Edge_Data, Args...>::value
203 && std::is_nothrow_constructible<StateOut, StateOut>::value
204 && std::is_nothrow_constructible<Edge, Edge>::value)
205 : Edge_Data{std::forward<Args>(args)...},
206 dst(dst), next_succ(next_succ), src(src)
222 return this->data() < other.data();
227 return src == other.src &&
229 this->data() == other.data();
241 template <
typename Graph>
243 std::iterator<std::forward_iterator_tag,
245 std::conditional<std::is_const<Graph>::value,
246 const typename Graph::edge_storage_t,
247 typename Graph::edge_storage_t>::type>
250 std::iterator<std::forward_iterator_tag,
252 std::conditional<std::is_const<Graph>::value,
253 const typename Graph::edge_storage_t,
254 typename Graph::edge_storage_t>::type>
257 typedef typename Graph::edge edge;
279 typename super::reference
282 return g_->edge_storage(t_);
285 const typename super::reference
288 return g_->edge_storage(t_);
291 typename super::pointer
294 return &g_->edge_storage(t_);
297 const typename super::pointer
300 return &g_->edge_storage(t_);
305 t_ = operator*().next_succ;
312 t_ = operator*().next_succ;
316 operator bool()
const
331 template <
typename Graph>
336 typedef typename Graph::state_storage_t state_storage_t;
337 typedef typename Graph::edge edge;
340 : super(g, t), src_(src), prev_(0)
347 this->t_ = this->operator*().next_succ;
361 edge next = this->operator*().next_succ;
366 this->g_->edge_storage(prev_).next_succ = next;
370 if (src_.succ == this->t_)
373 if (src_.succ_tail == this->t_)
375 src_.succ_tail = prev_;
380 this->operator*().next_succ = this->t_;
385 ++this->g_->killed_edge_;
389 state_storage_t& src_;
400 template <
typename Graph>
404 typedef typename Graph::edge edge;
434 template <
typename Graph>
436 std::iterator<std::forward_iterator_tag,
438 std::conditional<std::is_const<Graph>::value,
439 const typename Graph::edge_storage_t,
440 typename Graph::edge_storage_t>::type>
443 std::iterator<std::forward_iterator_tag,
445 std::conditional<std::is_const<Graph>::value,
446 const typename Graph::edge_storage_t,
447 typename Graph::edge_storage_t>::type>
450 typedef typename std::conditional<std::is_const<Graph>::value,
451 const typename Graph::edge_vector_t,
452 typename Graph::edge_vector_t>::type
460 unsigned s = tv_.size();
463 while (t_ < s && tv_[t_].next_succ == t_);
474 : t_(tv.size()), tv_(tv)
501 typename super::reference
507 const typename super::reference
513 const typename super::pointer
519 typename super::pointer
527 template <
typename Graph>
531 typedef typename std::conditional<std::is_const<Graph>::value,
532 const typename Graph::edge_vector_t,
533 typename Graph::edge_vector_t>::type
564 template <
typename State_Data,
typename Edge_Data,
bool Alternating>
582 typedef State_Data state_data_t;
583 typedef Edge_Data edge_data_t;
587 typedef unsigned state;
588 typedef unsigned edge;
592 typedef typename std::conditional<Alternating,
594 state>::type out_state;
602 typedef std::vector<state_storage_t> state_vector;
603 typedef std::vector<edge_storage_t> edge_vector_t;
605 state_vector states_;
606 edge_vector_t edges_;
608 unsigned killed_edge_;
616 digraph(
unsigned max_states = 10,
unsigned max_trans = 0)
619 states_.reserve(max_states);
621 max_trans = max_states * 2;
622 edges_.reserve(max_trans + 1);
627 edges_[0].next_succ = 0;
633 return states_.size();
641 return edges_.size() - killed_edge_ - 1;
649 template <
typename... Args>
652 state s = states_.size();
653 states_.emplace_back(std::forward<Args>(args)...);
663 template <
typename... Args>
666 state s = states_.size();
667 states_.reserve(s + n);
669 states_.emplace_back(std::forward<Args>(args)...);
681 assert(s < states_.size());
685 const state_storage_t&
688 assert(s < states_.size());
698 typename state_storage_t::data_t&
701 assert(s < states_.size());
702 return states_[s].data();
705 const typename state_storage_t::data_t&
708 assert(s < states_.size());
709 return states_[s].data();
721 assert(s < edges_.size());
725 const edge_storage_t&
728 assert(s < edges_.size());
738 typename edge_storage_t::data_t&
741 assert(s < edges_.size());
742 return edges_[s].data();
745 const typename edge_storage_t::data_t&
748 assert(s < edges_.size());
749 return edges_[s].data();
758 template <
typename... Args>
762 assert(src < states_.size());
764 edge t = edges_.size();
765 edges_.emplace_back(dst, 0, src, std::forward<Args>(args)...);
767 edge st = states_[src].succ_tail;
768 assert(st < t || !st);
770 states_[src].succ = t;
772 edges_[st].next_succ = t;
773 states_[src].succ_tail = t;
780 assert(!states_.empty());
781 return &ss - &states_.front();
787 assert(!edges_.empty());
788 return &tt - &edges_.front();
796 return {
this, states_[src].succ};
802 return out(index_of_state(src));
808 return {
this, states_[src].succ};
812 out(state_storage_t& src)
const
814 return out(index_of_state(src));
825 return {
this, src.succ, src};
831 return out_iteraser(state_storage(src));
893 return (t < edges_.size() &&
894 edges_[t].next_succ != t);
903 return edges_[t].next_succ == t;
908 return t.next_succ == index_of_edge(t);
916 unsigned tend = edges_.size();
917 for (
unsigned t = 1; t < tend; ++t)
919 o <<
't' << t <<
": (s"
920 << edges_[t].src <<
", s"
921 << edges_[t].dst <<
") t"
922 << edges_[t].next_succ <<
'\n';
924 unsigned send = states_.size();
925 for (
unsigned s = 0; s < send; ++s)
927 o <<
's' << s <<
": t"
928 << states_[s].succ <<
" t"
929 << states_[s].succ_tail <<
'\n';
940 if (killed_edge_ == 0)
942 auto i = std::remove_if(edges_.begin() + 1, edges_.end(),
943 [
this](
const edge_storage_t& t) {
944 return this->is_dead_edge(t);
946 edges_.erase(i, edges_.end());
955 template<
class Predicate = std::less<edge_storage_t>>
960 std::stable_sort(edges_.begin() + 1, edges_.end(), p);
969 state last_src = -1
U;
970 edge tend = edges_.size();
971 for (edge t = 1; t < tend; ++t)
973 state src = edges_[t].src;
976 states_[src].succ = t;
979 states_[last_src].succ_tail = t - 1;
980 edges_[t - 1].next_succ = 0;
982 while (++last_src != src)
984 states_[last_src].succ = 0;
985 states_[last_src].succ_tail = 0;
990 edges_[t - 1].next_succ = t;
995 states_[last_src].succ_tail = tend - 1;
996 edges_[tend - 1].next_succ = 0;
998 unsigned send = states_.size();
999 while (++last_src != send)
1001 states_[last_src].succ = 0;
1002 states_[last_src].succ_tail = 0;
1015 assert(newst.size() == states_.size());
1016 unsigned tend = edges_.size();
1017 for (
unsigned t = 1; t < tend; t++)
1019 edges_[t].dst = newst[edges_[t].dst];
1020 edges_[t].src = newst[edges_[t].src];
1031 assert(newst.size() == states_.size());
1032 assert(used_states > 0);
1038 unsigned send = states_.size();
1039 for (state s = 0; s < send; ++s)
1041 state dst = newst[s];
1049 auto t = states_[s].succ;
1051 std::swap(t, edges_[t].next_succ);
1054 states_[dst] = std::move(states_[s]);
1056 states_.resize(used_states);
1061 unsigned tend = edges_.size();
1062 std::vector<edge> newidx(tend);
1064 for (edge t = 1; t < tend; ++t)
1066 if (is_dead_edge(t))
1069 edges_[dest] = std::move(edges_[t]);
1073 edges_.resize(dest);
1077 for (edge t = 1; t < dest; ++t)
1079 auto& tr = edges_[t];
1080 tr.next_succ = newidx[tr.next_succ];
1081 tr.dst = newst[tr.dst];
1082 tr.src = newst[tr.src];
1083 assert(tr.dst != -1
U);
1087 for (
auto& s: states_)
1089 s.succ = newidx[s.succ];
1090 s.succ_tail = newidx[s.succ_tail];
const edge_storage_t::data_t & edge_data(edge s) const
return the Edgeg_Data of an edge.
Definition: graph.hh:746
unsigned num_edges() const
The number of edges in the automaton.
Definition: graph.hh:639
bool is_dead_edge(const edge_storage_t &t) const
Tests whether an edge has been erased.
Definition: graph.hh:906
edge_storage_t & edge_storage(edge s)
return a reference to the storage of an edge
Definition: graph.hh:719
edge_storage_t::data_t & edge_data(edge s)
return the Edgeg_Data of an edge.
Definition: graph.hh:739
state new_state(Args &&...args)
Create a new states.
Definition: graph.hh:650
unsigned num_states() const
The number of states in the automaton.
Definition: graph.hh:631
void remove_dead_edges_()
Remove all dead edges.
Definition: graph.hh:938
const state_storage_t & state_storage(state s) const
return a reference to the storage of a state
Definition: graph.hh:686
internal::state_out< const digraph > out(state_storage_t &src) const
Return a fake container with all edges leaving src.
Definition: graph.hh:812
internal::state_out< digraph > out(state src)
Return a fake container with all edges leaving src.
Definition: graph.hh:794
void chain_edges_()
Reconstruct the chain of outgoing edges.
Definition: graph.hh:967
Abstract class for states.
Definition: twa.hh:43
const state_vector & states() const
Return the vector of states.
Definition: graph.hh:838
bool is_dead_edge(unsigned t) const
Tests whether an edge has been erased.
Definition: graph.hh:901
internal::state_out< digraph > out(state_storage_t &src)
Return a fake container with all edges leaving src.
Definition: graph.hh:800
state index_of_state(const state_storage_t &ss) const
Convert a storage reference into a state number.
Definition: graph.hh:778
internal::state_out< const digraph > out(state src) const
Return a fake container with all edges leaving src.
Definition: graph.hh:806
const edge_vector_t & edge_vector() const
Return the vector of all edges.
Definition: graph.hh:872
edge index_of_edge(const edge_storage_t &tt) const
Conveart a storage reference into an edge number.
Definition: graph.hh:785
state_vector & states()
Return the vector of states.
Definition: graph.hh:843
internal::all_trans< digraph > edges()
Return a fake container with all edges (exluding erased edges)
Definition: graph.hh:858
state new_states(unsigned n, Args &&...args)
Create n new states.
Definition: graph.hh:664
void defrag_states(std::vector< unsigned > &&newst, unsigned used_states)
Rename and remove states.
Definition: graph.hh:1029
internal::all_trans< const digraph > edges() const
Return a fake container with all edges (exluding erased edges)
Definition: graph.hh:853
static constexpr bool alternating()
Whether the automaton is alternating.
Definition: graph.hh:576
edge_vector_t & edge_vector()
Return the vector of all edges.
Definition: graph.hh:877
bool is_valid_edge(edge t) const
Test whether the given edge is valid.
Definition: graph.hh:889
const state_storage_t::data_t & state_data(state s) const
return the State_Data associated to a state
Definition: graph.hh:706
edge new_edge(state src, out_state dst, Args &&...args)
Create a new edge.
Definition: graph.hh:760
digraph(unsigned max_states=10, unsigned max_trans=0)
Construct an empty graph.
Definition: graph.hh:616
A directed graph.
Definition: graph.hh:35
internal::killer_edge_iterator< digraph > out_iteraser(state src)
Return a fake container with all edges leaving src, allowing erasure.
Definition: graph.hh:829
state_storage_t & state_storage(state s)
return a reference to the storage of a state
Definition: graph.hh:679
void sort_edges_(Predicate p=Predicate())
Sort all edge according to a predicate.
Definition: graph.hh:956
void rename_states_(const std::vector< unsigned > &newst)
Rename all the states in the edge vector.
Definition: graph.hh:1013
internal::killer_edge_iterator< digraph > out_iteraser(state_storage_t &src)
Return a fake container with all edges leaving src, allowing erasure.
Definition: graph.hh:823
void dump_storage(std::ostream &o) const
Dump the state and edge storage for debugging.
Definition: graph.hh:914
state_storage_t::data_t & state_data(state s)
return the State_Data associated to a state
Definition: graph.hh:699
const edge_storage_t & edge_storage(edge s) const
return a reference to the storage of an edge
Definition: graph.hh:726