Vcsn  2.4
Be Rational
scc.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <iterator> // std::rbegin
4 #include <limits>
5 #include <stack>
6 
7 #include <boost/range/rbegin.hpp>
8 #include <boost/range/rend.hpp>
9 
10 #include <vcsn/algos/copy.hh> // make_fresh_automaton
11 #include <vcsn/algos/filter.hh>
12 #include <vcsn/algos/tags.hh>
13 #include <vcsn/algos/transpose.hh>
15 #include <vcsn/dyn/automaton.hh>
16 #include <vcsn/dyn/fwd.hh>
17 #include <vcsn/misc/builtins.hh>
18 #include <vcsn/misc/getargs.hh>
21 #include <vcsn/misc/vector.hh> // has
22 
23 namespace vcsn
24 {
25  namespace detail
26  {
27 
28  /*--------------------------------.
29  | strongly connected component. |
30  `--------------------------------*/
31 
40  template <Automaton Aut>
41  using component_t = std::unordered_set<state_t_of<Aut>>;
42 
44  template <Automaton Aut>
45  using components_t = std::vector<component_t<Aut>>;
46 
47 
48  /*---------------------.
49  | reverse_postorder. |
50  `---------------------*/
51 
53  template <Automaton Aut>
55  {
56  public:
58 
59  reverse_postorder_impl(const Aut& aut)
60  : aut_{aut}
61  {
62  rvp_.reserve(aut->num_all_states());
63  for (auto s : aut->states())
64  if (!has(marked_, s))
65  dfs(s);
66  }
67 
68  std::vector<state_t>& reverse_post()
69  {
70  return rvp_;
71  }
72 
73  private:
74  void dfs(state_t s)
75  {
76  marked_.emplace(s);
77  for (auto t : out(aut_, s))
78  {
79  auto dst = aut_->dst_of(t);
80  if (!has(marked_, dst))
81  dfs(dst);
82  }
83  rvp_.emplace_back(s);
84  }
85 
87  Aut aut_;
89  std::vector<state_t> rvp_;
91  std::unordered_set<state_t> marked_;
92  };
93  }
94 
96  template <Automaton Aut>
97  std::vector<state_t_of<Aut>>
98  reverse_postorder(const Aut& aut)
99  {
101  return dv.reverse_post();
102  }
103 
104 
105  namespace detail
106  {
111  template <Automaton Aut, typename Tag = auto_tag>
112  class scc_impl;
113 
114  /*------------.
115  | dijkstra. |
116  `------------*/
117 
122  template <Automaton Aut>
123  class scc_impl<Aut, dijkstra_tag>
124  {
125  public:
129 
130  scc_impl(const Aut& aut)
131  : aut_{aut}
132  {}
133 
135  {
136  for (auto s : aut_->states())
137  if (!has(component_, s))
138  dfs(s);
139  return components_;
140  }
141 
142  private:
143  void dfs(state_t s)
144  {
145  preorder_[s] = count_;
146  ++count_;
147  unassigned_.push(s);
148  uncertain_.push(s);
149  for (auto t: out(aut_, s))
150  {
151  state_t dst = aut_->dst_of(t);
152  if (!has(preorder_, dst))
153  dfs(dst);
154  else if (!has(component_, dst))
155  {
156  size_t dstpo = preorder_[dst];
157  while (dstpo < preorder_[uncertain_.top()])
158  uncertain_.pop();
159  }
160  }
161  if (s == uncertain_.top())
162  {
163  uncertain_.pop();
164  auto scc_num = components_.size();
165  components_.emplace_back();
166  component_t& scc = components_.back();
167  for (state_t r = unassigned_.top();
168  !unassigned_.empty();
169  unassigned_.pop(), r = unassigned_.top())
170  {
171  component_[r] = scc_num;
172  scc.insert(r);
173  if (r == s)
174  break;
175  }
176  }
177  }
178 
180  Aut aut_;
184  std::stack<state_t> unassigned_;
188  std::stack<state_t> uncertain_;
190  std::size_t count_ = 0;
191 
193  std::unordered_map<state_t, size_t> component_;
194 
195  std::unordered_map<state_t, size_t> preorder_;
198  };
199  }
200 
201  /*------------.
202  | kosaraju. |
203  `------------*/
204 
206  struct kosaraju_tag {};
207 
208  namespace detail
209  {
212  template <Automaton Aut>
213  class scc_impl<Aut, kosaraju_tag>
214  {
215  public:
219 
220  scc_impl(const Aut& aut)
221  : aut_{aut}
222  {
223  auto trans = ::vcsn::transpose(aut);
224  auto todo = ::vcsn::reverse_postorder(trans);
225  while (!todo.empty())
226  {
227  auto s = todo.back();
228  todo.pop_back();
229  if (!has(marked_, s))
230  {
231  dfs(s);
232  ++num_;
233  }
234  }
235  }
236 
237  const components_t& components() const
238  {
239  return components_;
240  }
241 
242  private:
243  void dfs(state_t s)
244  {
245  marked_.emplace(s);
246  if (num_ == components_.size())
247  components_.emplace_back(component_t{s});
248  else
249  components_[num_].emplace(s);
250 
251  for (auto t : out(aut_, s))
252  {
253  auto dst = aut_->dst_of(t);
254  if (!has(marked_, dst))
255  dfs(dst);
256  }
257  }
258 
260  Aut aut_;
262  std::size_t num_ = 0;
265  std::unordered_set<state_t> marked_;
266  };
267  }
268 
269  /*---------------------.
270  | tarjan, iterative. |
271  `---------------------*/
272 
276 
277  namespace detail
278  {
284  template <Automaton Aut>
286  {
287  public:
290 
293 
294  scc_impl(const Aut& aut)
295  : aut_{aut}
296  {
297  for (auto s : aut_->states())
298  if (!has(number_, s))
299  dfs(s);
300  }
301 
302  const components_t& components() const
303  {
304  return components_;
305  }
306 
307  private:
308  void dfs(state_t s)
309  {
310  number_[s] = low_[s] = curr_state_num_++;
311  dfs_stack_.emplace_back(s, out(aut_, s).begin(), out(aut_, s).end());
312  stack_.push_back(s);
313  while (!dfs_stack_.empty())
314  {
315  auto& st = dfs_stack_.back();
316  auto src = st.state;
317  if (st.pos != st.end)
318  {
319  auto dst = aut_->dst_of(*st.pos);
320  ++st.pos;
321  if (!has(number_, dst))
322  {
323  number_[dst] = low_[dst] = curr_state_num_++;
324  const auto& ts = out(aut_, dst);
325  dfs_stack_.emplace_back(dst, ts.begin(), ts.end());
326  stack_.push_back(dst);
327  }
328  else if (low_[dst] < low_[src])
329  low_[src] = low_[dst];
330  }
331  else
332  {
333  if (low_[src] == number_[src])
334  {
335  components_.emplace_back();
336  auto& com = components_.back();
337  state_t w;
338  do
339  {
340  w = stack_.back();
341  stack_.pop_back();
342  com.emplace(w);
343  low_[w] = low_max_;
344  }
345  while (w != src);
346  }
347  dfs_stack_.pop_back();
348  if (!dfs_stack_.empty())
349  {
350  auto& parent = dfs_stack_.back();
351  if (low_[src] < low_[parent.state])
352  low_[parent.state] = low_[src];
353  }
354  }
355  }
356  }
357 
359  Aut aut_;
360 
362  struct step_t;
363  std::vector<step_t> dfs_stack_;
364 
366  std::size_t curr_state_num_ = 0;
368  std::unordered_map<state_t, std::size_t> number_;
370  std::unordered_map<state_t, std::size_t> low_;
372  std::size_t low_max_ = std::numeric_limits<unsigned int>::max();
373 
375  std::vector<state_t> stack_;
378 
380  using iterator_t = decltype(out(aut_, state_t{}).begin());
381 
384  struct step_t
385  {
387  : state{s}, pos{p}, end{e} {}
391  };
392  };
393  }
394 
395  /*--------------------.
396  | tarjan_recursive. |
397  `--------------------*/
398 
402 
403  namespace detail
404  {
410  template <Automaton Aut>
412  {
413  public:
417 
418  scc_impl(const Aut& aut)
419  : aut_{aut}
420  {
421  for (auto s : aut_->states())
422  if (!has(marked_, s))
423  dfs(s);
424  }
425 
426  const components_t& components() const
427  {
428  return components_;
429  }
430 
431  private:
432  void dfs(state_t s)
433  {
434  std::size_t min = curr_state_num_++;
435  low_.emplace(s, min);
436  marked_.emplace(s);
437  stack_.push_back(s);
438 
439  for (auto t : out(aut_, s))
440  {
441  auto dst = aut_->dst_of(t);
442  if (!has(marked_, dst))
443  dfs(dst);
444  if (low_[dst] < min)
445  min = low_[dst];
446  }
447  if (min < low_[s])
448  {
449  low_[s] = min;
450  return;
451  }
452 
453  components_.emplace_back();
454  auto& com = components_.back();
455  state_t w;
456  do
457  {
458  w = stack_.back();
459  stack_.pop_back();
460  com.emplace(w);
461  // This state belong only one component
462  // so remove it by update low value to max size.
463  low_[w] = std::numeric_limits<size_t>::max();
464  }
465  while (w != s);
466  }
467 
469  Aut aut_;
472  std::size_t curr_state_num_ = 0;
476  std::unordered_set<state_t> marked_;
479  std::unordered_map<state_t, std::size_t> low_;
481  std::vector<state_t> stack_;
482  };
483  }
484 
485  /*--------.
486  | auto. |
487  `--------*/
488 
489  namespace detail
490  {
492  template <Automaton Aut>
493  class scc_impl<Aut, auto_tag>
494  : public scc_impl<Aut, tarjan_iterative_tag>
495  {
497  using super_t::super_t;
498  };
499  }
500 
501 
502  /*-------.
503  | scc. |
504  `-------*/
505 
506  enum class scc_algo_t
507  {
508  auto_,
509  dijkstra,
512  kosaraju
513  };
514 
515  inline scc_algo_t scc_algo(const std::string& algo)
516  {
517  static const auto map = getarg<scc_algo_t>
518  {
519  "strongly connected components algorithm",
520  {
521  {"auto", scc_algo_t::auto_},
522  {"dijkstra", scc_algo_t::dijkstra},
523  {"kosaraju", scc_algo_t::kosaraju},
524  {"tarjan", "tarjan,iterative"},
525  {"tarjan,iterative", scc_algo_t::tarjan_iterative},
526  {"tarjan,recursive", scc_algo_t::tarjan_recursive},
527  {"tarjan_iterative", "tarjan,iterative"},
528  {"tarjan_recursive", "tarjan,recursive"},
529  }
530  };
531  return map[algo];
532  }
533 
538  template <Automaton Aut, typename Tag = auto_tag>
539  const detail::components_t<Aut>
540  strong_components(const Aut& aut, Tag = {})
541  {
542  return detail::scc_impl<Aut, Tag>{aut}.components();
543  }
544 
549  template <Automaton Aut>
550  const detail::components_t<Aut>
551  strong_components(const Aut& aut,
553  {
554  switch (algo)
555  {
556  case scc_algo_t::auto_:
557  return strong_components(aut, auto_tag{});
559  return strong_components(aut, dijkstra_tag{});
561  return strong_components(aut, kosaraju_tag{});
566  }
568  }
569 
571  template <Automaton Aut>
572  fresh_automaton_t_of<Aut>
573  aut_of_component(const detail::component_t<Aut>& com, const Aut& aut)
574  {
575  auto res = make_fresh_automaton(aut);
576  using res_t = decltype(res);
577  auto map = std::unordered_map<state_t_of<Aut>, state_t_of<res_t>>{};
578  auto s0 = *com.begin();
579  map[s0] = res->new_state();
580  res->set_initial(map[s0]);
581  for (auto s : com)
582  {
583  if (!has(map, s))
584  map[s] = res->new_state();
585  for (auto t : out(aut, s))
586  {
587  auto dst = aut->dst_of(t);
588  if (!has(com, dst))
589  continue;
590  if (!has(map, dst))
591  map[dst] = res->new_state();
592  res->new_transition(map[s], map[dst], aut->label_of(t));
593  }
594  }
595  return res;
596  }
597 
598  /*-----------------.
599  | scc_automaton. |
600  `-----------------*/
601 
602  namespace detail
603  {
605  template <Automaton Aut>
607  : public automaton_decorator<Aut>
608  {
609  public:
610  using automaton_t = Aut;
615 
617  : super_t(input)
618  {
619  // Components are numbered by ordered of discovery. Reverse
620  // this, so that components are roughly numbered as the
621  // condensation state numbers would be (0 as an initial
622  // state).
623  const auto& cs = vcsn::strong_components(aut_, algo);
624  // FIXME: std::rbegin/rend does not work with libstdc++.
625  components_.assign(boost::rbegin(cs), boost::rend(cs));
626  size_t num_sccs = components_.size();
627  for (size_t i = 0; i < num_sccs; ++i)
628  for (auto s : components_[i])
629  component_[s] = i;
630  }
631 
633  static symbol sname()
634  {
635  static auto res = symbol{"scc_automaton<"
637  return res;
638  }
639 
640  std::ostream& print_set(std::ostream& o, format fmt = {}) const
641  {
642  o << "scc_automaton<";
643  aut_->print_set(o, fmt);
644  return o << '>';
645  }
646 
647  bool state_has_name(state_t) const
648  {
649  return true;
650  }
651 
652  std::ostream& print_state_name(state_t s, std::ostream& o,
653  format fmt = {},
654  bool = false) const
655  {
656  o << component_.at(s) << '.';
657  aut_->print_state_name(s, o, fmt, true);
658  return o;
659  }
660 
661  const component_t& component(unsigned num) const
662  {
663  VCSN_REQUIRE(num < components_.size(),
664  "component: invalid component number: ",
665  num, ": there are ", components_.size(), " components");
666  return components_[num];
667  }
668 
669  const components_t& components() const
670  {
671  return components_;
672  }
673 
674  size_t num_components() const
675  {
676  return components_.size();
677  }
678 
679  private:
680  using super_t::aut_;
682  std::map<state_t, size_t> component_;
683  components_t components_;
684  };
685  }
686 
687  template <Automaton Aut>
688  using scc_automaton = std::shared_ptr<detail::scc_automaton_impl<Aut>>;
689 
691  template <Automaton Aut>
692  scc_automaton<Aut>
693  scc(const Aut& aut, const std::string& algo = "auto")
694  {
695  return make_shared_ptr<scc_automaton<Aut>>(aut, scc_algo(algo));
696  }
697 
698  namespace dyn
699  {
700  namespace detail
701  {
703  template <Automaton Aut, typename String>
704  automaton scc(const automaton& aut, const std::string& algo)
705  {
706  const auto& a = aut->as<Aut>();
707  return ::vcsn::scc(a, algo);
708  }
709  }
710  }
711 
712  /*----------------.
713  | num_components. |
714  `----------------*/
715 
717  template <Automaton Aut>
718  std::size_t num_components(const scc_automaton<Aut>& aut)
719  {
720  return aut->num_components();
721  }
722 
723  template <Automaton Aut>
724  std::size_t num_components(const Aut&)
725  {
726  raise("num_components: requires an scc_automaton");
727  }
728 
729  namespace dyn
730  {
731  namespace detail
732  {
734  template <Automaton Aut>
735  std::size_t num_components(const automaton& aut)
736  {
737  const auto& a = aut->as<Aut>();
738  return ::vcsn::num_components(a);
739  }
740  }
741  }
742 
743 
744  /*-----------.
745  | component. |
746  `-----------*/
747 
751  template <Automaton Aut>
752  filter_automaton<scc_automaton<Aut>>
753  component(const scc_automaton<Aut>& aut, unsigned num)
754  {
755  return vcsn::filter(aut, aut->component(num));
756  }
757 
758  template <Automaton Aut>
759  void
760  component(const Aut&, unsigned)
761  {
762  raise("component: requires an scc_automaton");
763  }
764 
765  namespace dyn
766  {
767  namespace detail
768  {
770  template <Automaton Aut, typename Unsigned>
771  automaton component(const automaton& aut, unsigned num)
772  {
773  const auto& a = aut->as<Aut>();
774  return ::vcsn::component(a, num);
775  }
776  }
777  }
778 
779 
780  /*----------.
781  | condense. |
782  `----------*/
783 
786  template <Automaton Aut>
787  partition_automaton<scc_automaton<Aut>>
788  condense(const scc_automaton<Aut>& aut)
789  {
790  auto res = make_shared_ptr<partition_automaton<scc_automaton<Aut>>>(aut);
791  using state_t = state_t_of<Aut>;
792 
793  // State of aut -> state(component) of new automaton.
794  auto map = std::unordered_map<state_t, state_t>
795  {
796  {aut->pre(), res->pre()},
797  {aut->post(), res->post()},
798  };
799 
800  // Add states to new automaton.
801  for (const auto& com : aut->components())
802  {
803  state_t new_state = res->new_state(com);
804  for (auto s : com)
805  map[s] = new_state;
806  }
807 
808  // Add transitions to new automaton.
809  for (auto t: all_transitions(aut))
810  {
811  auto s = map[aut->src_of(t)];
812  auto d = map[aut->dst_of(t)];
813  if (s != d)
814  res->add_transition(s, d, aut->label_of(t), aut->weight_of(t));
815  }
816  return res;
817  }
818 
819  template <Automaton Aut>
820  partition_automaton<Aut>
821  condense(const Aut&)
822  {
823  raise("condense: requires an scc_automaton");
824  }
825 
826  namespace dyn
827  {
828  namespace detail
829  {
831  template <Automaton Aut>
832  automaton condense(const automaton& aut)
833  {
834  const auto& a = aut->as<Aut>();
835  return ::vcsn::condense(a);
836  }
837  }
838  }
839 }
std::unordered_map< state_t, size_t > preorder_
Definition: scc.hh:195
detail::components_t< Aut > components_t
Definition: scc.hh:613
std::vector< state_t_of< Aut > > reverse_postorder(const Aut &aut)
Get all states in reverse postorder.
Definition: scc.hh:98
Request the Tarjan's algorithm to compute the SCCs, implemented with explicit stack handling...
Definition: scc.hh:275
detail::components_t< Aut > components_t
Definition: scc.hh:416
std::vector< state_t > & reverse_post()
Definition: scc.hh:68
Get all states in reverse postorder using depth first search.
Definition: scc.hh:54
return res
Definition: multiply.hh:398
std::unordered_set< state_t > marked_
Visited states.
Definition: scc.hh:476
std::vector< component_t< Aut >> components_t
A set of strongly-connected components.
Definition: scc.hh:45
fresh_automaton_t_of< Aut > aut_of_component(const detail::component_t< Aut > &com, const Aut &aut)
Generate a subautomaton corresponding to an SCC.
Definition: scc.hh:573
scc_automaton_impl(const automaton_t &input, scc_algo_t algo)
Definition: scc.hh:616
std::vector< state_t > stack_
List of states in the same the component.
Definition: scc.hh:481
Aggregate an automaton, and forward calls to it.
detail::component_t< Aut > component_t
Definition: scc.hh:614
An input/output format for valuesets.
Definition: format.hh:13
std::unordered_map< state_t, std::size_t > number_
Store the visit order of each state.
Definition: scc.hh:368
weightset_mixin< detail::r_impl > r
Definition: fwd.hh:54
detail::component_t< Aut > component_t
Definition: scc.hh:217
const components_t & components() const
Definition: scc.hh:237
Dijkstra implementation.
Definition: tags.hh:144
Provide a variadic mul on top of a binary mul(), and one().
Definition: fwd.hh:46
components_t components_
All components.
Definition: scc.hh:377
state_t_of< Aut > state_t
Definition: scc.hh:612
Tag to request the most appropriate version of an algorithm.
Definition: tags.hh:16
components_t components_
All the components.
Definition: scc.hh:197
std::vector< state_t > stack_
List of states in the same the component.
Definition: scc.hh:375
static symbol sname()
Static name.
Definition: scc.hh:633
boost::flyweight< std::string, boost::flyweights::no_tracking, boost::flyweights::intermodule_holder > symbol
An internalized string.
Definition: symbol.hh:23
std::vector< state_t > rvp_
Revert postorder of dfs.
Definition: scc.hh:89
Tarjan's algorithm to find all strongly connected components: iterative implementation.
Definition: scc.hh:285
detail::components_t< Aut > components_t
Definition: scc.hh:218
std::stack< state_t > uncertain_
Stack P contains vertices that have not yet been determined to belong to different strongly connected...
Definition: scc.hh:188
decltype(out(aut_, state_t{}).begin()) iterator_t
Iterator on outgoing transitions.
Definition: scc.hh:380
std::unordered_set< state_t > marked_
Definition: scc.hh:265
components_t components_
All components.
Definition: scc.hh:474
state_t_of< Aut > state_t
Definition: scc.hh:57
return exp min
Definition: multiply.hh:361
Definition: a-star.hh:8
std::unordered_set< state_t_of< Aut >> component_t
A strongly-connected component: set of states.
Definition: scc.hh:41
Request the Kosaraju's algorithm to compute the SCCs.
Definition: scc.hh:206
auto out(const Aut &aut, state_t_of< Aut > s)
Indexes of visible transitions leaving state s.
Definition: automaton.hh:85
scc_algo_t scc_algo(const std::string &algo)
Definition: scc.hh:515
Class template for strongly-connected-components computations.
Definition: scc.hh:112
std::map< state_t, size_t > component_
For each state, its component number.
Definition: scc.hh:682
scc_automaton< Aut > scc(const Aut &aut, const std::string &algo="auto")
Get scc_automaton from aut.
Definition: scc.hh:693
AutOut make_fresh_automaton(const AutIn &model)
Create an empty, mutable, automaton, based on another one.
Definition: copy.hh:91
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
Definition: traits.hh:64
detail::component_t< Aut > component_t
Definition: scc.hh:127
step_t(state_t s, iterator_t p, iterator_t e)
Definition: scc.hh:386
detail::component_t< Aut > component_t
Definition: scc.hh:291
#define BUILTIN_UNREACHABLE()
Definition: builtins.hh:13
const components_t & components()
Definition: scc.hh:134
std::unordered_set< state_t > marked_
Store the visited states.
Definition: scc.hh:91
detail::components_t< Aut > components_t
Definition: scc.hh:128
const components_t & components() const
Definition: scc.hh:302
detail::components_t< Aut > components_t
Definition: scc.hh:292
typename detail::transition_t_of_impl< base_t< ValueSet >>::type transition_t_of
Definition: traits.hh:65
Request the Tarjan's algorithm to compute the SCCs, implemented with recursion.
Definition: scc.hh:401
std::unordered_map< state_t, std::size_t > low_
low_[s] is minimum of low_{X}, with X is all states on output transitions of s.
Definition: scc.hh:479
symbol sname()
Definition: name.hh:65
detail::component_t< Aut > component_t
Definition: scc.hh:415
std::unordered_map< state_t, std::size_t > low_
low_[s] is minimum of state that it can go.
Definition: scc.hh:370
components_t components_
All components.
Definition: scc.hh:264
std::unordered_map< state_t, size_t > component_
For each state, its component number.
Definition: scc.hh:193
const components_t & components() const
Definition: scc.hh:426
A mapping from strings to Values.
Definition: getargs.hh:33
ATTRIBUTE_PURE bool has(const boost::container::flat_set< Key, Compare, Allocator > &s, const Key &e)
Whether e is member of s.
Definition: setalpha.hh:25
An automaton decorator that maps states to their scc-number.
Definition: scc.hh:606
Aut aut_
Input automaton.
Definition: scc.hh:87
std::ostream & print_set(std::ostream &o, format fmt={}) const
Definition: scc.hh:640
std::stack< state_t > unassigned_
Stack S contains all the vertices that have not yet been assigned to a strongly connected component...
Definition: scc.hh:184
scc_algo_t
Definition: scc.hh:506
Aut transpose(const transpose_automaton< Aut > &aut)
The transpose of a transpose automaton is the original automaton.
Definition: transpose.hh:253
reverse_postorder_impl(const Aut &aut)
Definition: scc.hh:59
const detail::components_t< Aut > strong_components(const Aut &aut, Tag={})
Find all strongly connected components of aut.
Definition: scc.hh:540