Vaucanson  1.4.1
bmig_graph_impl.hxx
1 // boost_graph.hxx: this file is part of the Vaucanson project.
2 //
3 // Vaucanson, a generic library for finite state machines.
4 //
5 // Copyright (C) 2007, 2008 The Vaucanson Group.
6 //
7 // This program is free software; you can redistribute it and/or
8 // modify it under the terms of the GNU General Public License
9 // as published by the Free Software Foundation; either version 2
10 // of the License, or (at your option) any later version.
11 //
12 // The complete GNU General Public Licence Notice can be found as the
13 // `COPYING' file in the root directory.
14 //
15 // The Vaucanson Group consists of people listed in the `AUTHORS' file.
16 //
17 
18 #ifndef VCSN_AUTOMATA_IMPLEMENTATION_BMIG_GRAPH_IMPL_HXX_
19 # define VCSN_AUTOMATA_IMPLEMENTATION_BMIG_GRAPH_IMPL_HXX_
20 
21 # include <vaucanson/automata/implementation/bmig_graph_impl.hh>
22 
23 namespace vcsn
24 {
25  namespace bmig
26  {
27 
28  /*--------------------.
29  | Convenient macros. |
30  `--------------------*/
31 
32 # define BMIGRAPH_TPARAM \
33  template <class Kind, class WordValue, class WeightValue, \
34  class SeriesValue, class Letter, class Tag, class GeometryCoords>
35 
36 # define BMIGRAPH \
37  Graph<Kind, WordValue, WeightValue, SeriesValue, Letter, Tag, GeometryCoords>
38 
39  /*-------------------------.
40  | Graph's implementation. |
41  `-------------------------*/
42 
43  /*---------------.
44  | Constructors. |
45  `---------------*/
46 
47  BMIGRAPH_TPARAM
48  BMIGRAPH::Graph ()
49  : initial_bitset_(0),
50  final_bitset_(0),
51  number_of_epsilon_(0),
52  number_of_state_(0)
53  {
54  }
55 
65  BMIGRAPH_TPARAM
66  BMIGRAPH::Graph (unsigned initial_number_of_states,
67  unsigned)
68  : initial_bitset_(initial_number_of_states),
69  final_bitset_(initial_number_of_states),
70  number_of_epsilon_(0),
71  number_of_state_(initial_number_of_states),
72  states_(initial_number_of_states)
73  {
74  for (unsigned i = 0; i < initial_number_of_states; ++i)
75  {
76  boost::shared_ptr<std::size_t> p(new std::size_t(i));
77  states_[i] = p;
78  }
79  }
80 
81  BMIGRAPH_TPARAM
82  BMIGRAPH::Graph (const self_t& g)
83  {
84  tag_ = g.tag_;
85  initial_bitset_ = g.initial_bitset_;
86  final_bitset_ = g.final_bitset_;
87  number_of_epsilon_ = g.number_of_epsilon_;
88  number_of_state_ = g.number_of_state_;
89  label_container_ = g.label_container_;
90  initial_.clear();
91  final_.clear();
92  states_.resize(g.number_of_state_);
93  for (unsigned i = 0; i < g.number_of_state_; ++i)
94  {
95  boost::shared_ptr<std::size_t> p(new std::size_t(i));
96  states_[i] = p;
97  }
98  graph_.clear();
99  for (typename graph_data_t::const_iterator i = g.graph_.begin();
100  i != g.graph_.end();
101  ++i)
102  graph_.insert(edge_data_t(states_[*i->from_],
103  states_[*i->to_],
104  i->label_));
105 // label_container_.get_hlabel(g.label_container_.get_label(i->label_))));
106  # define VCSN_COPY_I_T(Set) \
107  for (typename Set##t::const_iterator i = g.Set.begin(); \
108  i != g.Set.end(); \
109  ++i) \
110  Set.insert(initial_value_t (states_[*i->first], i->second));
111  VCSN_COPY_I_T(initial_)
112  VCSN_COPY_I_T(final_)
113  # undef VCSN_COPY_I_T
114 
115  # define VCSN_COPY_GEOMETRY(Type) \
116  { \
117  typename geometry_t::Type##_geometry_map_t& map_##Type = geometry_.Type(); \
118  map_##Type.clear(); \
119  for (typename geometry_t::Type##_geometry_map_t::const_iterator i = g.geometry_.Type().begin(); \
120  i != g.geometry_.Type().end(); \
121  ++i) \
122  map_##Type[i->first] = i->second; \
123  }
124  VCSN_COPY_GEOMETRY(states)
125  VCSN_COPY_GEOMETRY(initials)
126  VCSN_COPY_GEOMETRY(finals)
127 # undef VCSN_COPY_GEOMETRY
128  {
129  typename geometry_t::transitions_geometry_map_t& map_transitions = geometry_.transitions();
130  map_transitions.clear();
131  for (typename geometry_t::transitions_geometry_map_t::const_iterator i = g.geometry_.transitions().begin();
132  i != g.geometry_.transitions().end();
133  ++i)
134  {
135  typename graph_data_t::const_iterator tmp = find_edge(states_[*i->first.value()->from_],
136  states_[*i->first.value()->to_],
137  i->first.value()->label_);
138  //label_container_.get_hlabel(g.label_container_.get_label(i->first.value()->label_)));
139  if (tmp != graph_.end())
140  map_transitions[htransition_t(tmp)] = i->second;
141  }
142  }
143  }
144 
145  /*--------------.
146  | Destructors. |
147  `--------------*/
148 
149  BMIGRAPH_TPARAM
150  BMIGRAPH::~Graph ()
151  {
152  }
153 
154  BMIGRAPH_TPARAM
155  typename BMIGRAPH::self_t&
156  BMIGRAPH::operator= (const self_t& g)
157  {
158  if (this == &g)
159  return *this;
160  tag_ = g.tag_;
161  initial_bitset_ = g.initial_bitset_;
162  final_bitset_ = g.final_bitset_;
163  number_of_epsilon_ = g.number_of_epsilon_;
164  number_of_state_ = g.number_of_state_;
165  label_container_ = g.label_container_;
166  initial_.clear();
167  final_.clear();
168  states_.resize(g.number_of_state_);
169  for (unsigned i = 0; i < g.number_of_state_; ++i)
170  {
171  boost::shared_ptr<std::size_t> p(new std::size_t(i));
172  states_[i] = p;
173  }
174  graph_.clear();
175  for (typename graph_data_t::const_iterator i = g.graph_.begin();
176  i != g.graph_.end();
177  ++i)
178  graph_.insert(edge_data_t(states_[*i->from_],
179  states_[*i->to_],
180  i->label_));
181 # define VCSN_COPY_I_T(Set) \
182  for (typename Set##t::const_iterator i = g.Set.begin(); \
183  i != g.Set.end(); \
184  ++i) \
185  Set.insert(initial_value_t (states_[*i->first], i->second));
186  VCSN_COPY_I_T(initial_)
187  VCSN_COPY_I_T(final_)
188 # undef VCSN_COPY_I_T
189 
190 # define VCSN_COPY_GEOMETRY(Type) \
191  { \
192  typename geometry_t::Type##_geometry_map_t& map_##Type = geometry_.Type(); \
193  map_##Type.clear(); \
194  for (typename geometry_t::Type##_geometry_map_t::const_iterator i = g.geometry_.Type().begin(); \
195  i != g.geometry_.Type().end(); \
196  ++i) \
197  map_##Type[i->first] = i->second; \
198  }
199  VCSN_COPY_GEOMETRY(states)
200  VCSN_COPY_GEOMETRY(initials)
201  VCSN_COPY_GEOMETRY(finals)
202 # undef VCSN_COPY_GEOMETRY
203  {
204  typename geometry_t::transitions_geometry_map_t& map_transitions = geometry_.transitions();
205  map_transitions.clear();
206  for (typename geometry_t::transitions_geometry_map_t::const_iterator i = g.geometry_.transitions().begin();
207  i != g.geometry_.transitions().end();
208  ++i)
209  {
210  typename graph_data_t::const_iterator tmp = find_edge(states_[*i->first.value()->from_],
211  states_[*i->first.value()->to_],
212  i->first.value()->label_);
213  //label_container_.get_hlabel(g.label_container_.get_label(i->first.value()->label_)));
214  if (tmp != graph_.end())
215  map_transitions[htransition_t(tmp)] = i->second;
216  }
217  }
218  return *this;
219  }
220 
221  /*------------------.
222  | Basic accessors. |
223  `------------------*/
224 
225  BMIGRAPH_TPARAM
226  typename BMIGRAPH::states_t
227  BMIGRAPH::states() const
228  {
229  return misc::Support<states_data_t>(states_);
230  }
231 
232  BMIGRAPH_TPARAM
233  typename BMIGRAPH::edges_t
234  BMIGRAPH::edges() const
235  {
236  return edges_t(graph_);
237  }
238 
239  BMIGRAPH_TPARAM
240  typename BMIGRAPH::initial_support_t
241  BMIGRAPH::initial () const
242  {
243  return initial_support_t(initial_);
244  }
245 
246  BMIGRAPH_TPARAM
247  typename BMIGRAPH::final_support_t
248  BMIGRAPH::final () const
249  {
250  return final_support_t(final_);
251  }
252 
253 
254  /*----------------------.
255  | State manipulations. |
256  `----------------------*/
257 
258  BMIGRAPH_TPARAM
259  bool
260  BMIGRAPH::has_state (const hstate_t& s) const
261  {
262  // May be we should add a set or a hashtable to have
263  // a searching time better than linear
264  bool b = false;
265  for_all_iterator(states_data_t::const_iterator, i, states_)
266  if (*i == s.value())
267  b = true;
268  return b;
269  }
270 
271  BMIGRAPH_TPARAM
272  typename BMIGRAPH::hstate_t
273  BMIGRAPH::add_state ()
274  {
275  initial_bitset_.append(false);
276  final_bitset_.append(false);
277  boost::shared_ptr<std::size_t> p(new std::size_t(number_of_state_++));
278  state_t h(p);
279  states_.push_back(h);
280  return hstate_t(h);
281  }
282 
283  BMIGRAPH_TPARAM
284  typename BMIGRAPH::hstate_t
285  BMIGRAPH::get_state (unsigned s) const
286  {
287  precondition(s < states_.size());
288  return hstate_t(states_[s]);
289  }
290 
291  BMIGRAPH_TPARAM
292  void
293  BMIGRAPH::del_state (const hstate_t& s)
294  {
295  precondition (has_state(s));
296 
297  // One removes the state h
298  graph_.template get<src>().erase(s.value());
299  graph_.template get<dst>().erase(s.value());
300 
301  if (s != (number_of_state_ - 1) && (number_of_state_ - 1))
302  {
303  state_t lastone = states_.back();
304  states_[s] = lastone;
305  # define VCSN_UPDATE(Set) \
306  if (Set##bitset_[*lastone]) \
307  { \
308  if (Set##bitset_[s]) \
309  Set.erase(s.value()); \
310  else \
311  Set##bitset_[s] = true; \
312  } \
313  else \
314  { \
315  if (Set##bitset_[s]) \
316  { \
317  Set##bitset_[s] = false; \
318  Set.erase(s.value()); \
319  } \
320  }
321 
322  //Updating initial/final states information
323  VCSN_UPDATE(initial_)
324  VCSN_UPDATE(final_)
325  # undef VCSN_UPDATE
326  *lastone = *s.value();
327  }
328  else
329  {
330  initial_.erase(s.value());
331  final_.erase(s.value());
332  }
333 
334  --number_of_state_;
335  states_.pop_back();
336  postcondition(states_.size() == number_of_state_);
337  //delete s.value();
338  initial_bitset_.resize(number_of_state_);
339  final_bitset_.resize(number_of_state_);
340 
341  //Useless postcondition since the states are 'renamed'
342  //postcondition(!has_state(h));
343  }
344 
345  BMIGRAPH_TPARAM
346  void
347  BMIGRAPH::set_initial (const hstate_t& s,
348  const series_set_elt_value_t& v,
349  const series_set_elt_value_t& z)
350  {
351  precondition(has_state(s));
352  if (z == v)
353  {
354  initial_.erase (s.value());
355  initial_bitset_[s] = false;
356  }
357  else if (!initial_bitset_[s])
358  {
359  initial_.insert (initial_value_t (s.value(), v));
360  initial_bitset_[s] = true;
361  }
362  else
363  initial_.modify(initial_.find(s.value()), update_label<initial_value_t>(v));
364  }
365 
366  BMIGRAPH_TPARAM
367  const typename BMIGRAPH::series_set_elt_value_t&
368  BMIGRAPH::get_initial(const hstate_t& s, const series_set_elt_value_t &zero) const
369  {
370  precondition(has_state(s));
371  typename initial_t::const_iterator it = initial_.find(s.value());
372 
373  if (it == initial_.end())
374  return zero;
375  return it->second;
376  }
377 
378  BMIGRAPH_TPARAM
379  bool
380  BMIGRAPH::is_initial(const hstate_t& s, const series_set_elt_value_t&) const
381  {
382  precondition(has_state(s));
383  return initial_bitset_[s];
384  }
385 
386  BMIGRAPH_TPARAM
387  void
388  BMIGRAPH::clear_initial()
389  {
390  initial_.clear();
391  initial_bitset_.reset();
392  }
393 
394  BMIGRAPH_TPARAM
395  void
396  BMIGRAPH::set_final(const hstate_t& s,
397  const series_set_elt_value_t& v,
398  const series_set_elt_value_t& z)
399  {
400  precondition(has_state(s));
401  if (z == v)
402  {
403  final_.erase (s.value());
404  final_bitset_[s] = false;
405  }
406  else if (!final_bitset_[s])
407  {
408  final_.insert (initial_value_t (s.value(), v));
409  final_bitset_[s] = true;
410  }
411  else
412  final_.modify(final_.find(s.value()), update_label<final_value_t>(v));
413  }
414 
415  BMIGRAPH_TPARAM
416  const typename BMIGRAPH::series_set_elt_value_t&
417  BMIGRAPH::get_final(const hstate_t& s, const series_set_elt_value_t &zero) const
418  {
419  precondition(has_state(s));
420  typename final_t::const_iterator it = final_.find(s.value());
421 
422  if (it == final_.end())
423  return zero;
424  return it->second;
425  }
426 
427  BMIGRAPH_TPARAM
428  bool
429  BMIGRAPH::is_final(const hstate_t& s, const series_set_elt_value_t&) const
430  {
431  precondition(has_state(s));
432  return final_bitset_[s];
433  }
434 
435  BMIGRAPH_TPARAM
436  void
437  BMIGRAPH::clear_final()
438  {
439  final_.clear();
440  final_bitset_.reset();
441  }
442 
443  /*---------------------.
444  | Edge manipulations. |
445  `---------------------*/
446 
447  BMIGRAPH_TPARAM
448  bool
449  BMIGRAPH::has_edge (const hedge_t& h) const
450  {
451  succ_range r = graph_.equal_range(boost::make_tuple(h.value()->from_,
452  h.value()->label_));
453  succ_iterator it;
454  state_t to = h.value()->to_;
455  for (it = r.first; it != r.second && it->to_ != to; ++it)
456  /*Nothing*/;
457 
458  return it != r.second;
459  }
460 
461  BMIGRAPH_TPARAM
462  typename BMIGRAPH::hedge_t
463  BMIGRAPH::add_edge (const hstate_t& from, const hstate_t& to, const label_t& l)
464  {
465  //hlabel_t hl = label_container_.insert (l);
466  return hedge_t (graph_.insert (edge_data_t (from.value(), to.value(), l)).first);
467  }
468 
469  BMIGRAPH_TPARAM
470  void
471  BMIGRAPH::del_edge (const hedge_t& h)
472  {
473  precondition (has_edge(h));
474 
475  hlabel_t l = h.value()->label_;
476  graph_.erase(h.value());
477  //label_container_.erase(l);
478 
479  // h points to an invalid edgeValue since it is already destroyed.
480  // We can't check this postcondition anymore!
481  //postcondition(!has_edge(h));
482  }
483 
484  BMIGRAPH_TPARAM
485  typename BMIGRAPH::hstate_t
486  BMIGRAPH::src_of (const hedge_t& h) const
487  {
488  return hstate_t(h.value()->from_);
489  }
490 
491  BMIGRAPH_TPARAM
492  typename BMIGRAPH::hstate_t
493  BMIGRAPH::dst_of (const hedge_t& h) const
494  {
495  return hstate_t(h.value()->to_);
496  }
497 
498  BMIGRAPH_TPARAM
499  const typename BMIGRAPH::label_t&
500  BMIGRAPH::label_of (const hedge_t& h) const
501  {
502  return h.value()->label_;
503 // return label_container_.get_label(h.value()->label_);
504  }
505 
506  BMIGRAPH_TPARAM
507  void
508  BMIGRAPH::update(const hedge_t& h, const label_t& l)
509  {
510  label_container_.update(h->label_, l);
511  graph_.modify(h.value(), update_hlabel<hlabel_t>(h->label_));
512  }
513 
514  BMIGRAPH_TPARAM
515  template <class S>
516  bool
517  BMIGRAPH::exists (const AutomataBase<S>& s) const
518  {
519  typename WordValue::iterator it;
520  typename label_t::const_iterator r;
521  label_t l;
522  WordValue w;
523 
524  for (typename graph_data_t::iterator i = graph_.begin(); i != graph_.end(); ++i)
525  {
526  // Make sure that source and destination of edge are part of the
527  // automaton.
528  if (!has_state(dst_of(hedge_t(i))) ||
529  !has_state(src_of(hedge_t(i))))
530  return false;
531 
532  // Make sure that every letter of the edge is in the alphabet.
533  l = label_of(hedge_t(i));
534  for (r = l.begin(); r != l.end(); ++r)
535  {
536  w = r->first;
537  for (it = w.begin(); it != w.end(); ++it)
538  if (!s.series().monoid().alphabet().contains(*it))
539  return false;
540  }
541  }
542  return true;
543  }
544 
545  BMIGRAPH_TPARAM
546  inline
547  typename BMIGRAPH::tag_t&
548  BMIGRAPH::tag ()
549  {
550  return tag_;
551  }
552 
553  BMIGRAPH_TPARAM
554  inline
555  const typename BMIGRAPH::tag_t&
556  BMIGRAPH::tag () const
557  {
558  return tag_;
559  }
560 
561  BMIGRAPH_TPARAM
562  inline
563  typename BMIGRAPH::geometry_t&
564  BMIGRAPH::geometry ()
565  {
566  return geometry_;
567  }
568 
569  BMIGRAPH_TPARAM
570  inline
571  const typename BMIGRAPH::geometry_t&
572  BMIGRAPH::geometry () const
573  {
574  return geometry_;
575  }
576 
577  template <class Kind, class WordValue, class WeightValue, class SeriesValue,
578  class Letter, class Tag, class GeometryCoords, class I>
579  Tag&
580  op_tag(const AutomataBase<I>&, BMIGRAPH &g)
581  {
582  return g.tag();
583  }
584 
585  template <class Kind, class WordValue, class WeightValue, class SeriesValue,
586  class Letter, class Tag, class GeometryCoords, class I>
587  const Tag&
588  op_tag(const AutomataBase<I>&, BMIGRAPH &g)
589  {
590  return g.tag();
591  }
592 
593  template <class Kind, class WordValue, class WeightValue, class SeriesValue,
594  class Letter, class Tag, class GeometryCoords, class I>
595  typename BMIGRAPH::geometry_t&
596  op_geometry(const AutomataBase<I>&, BMIGRAPH &g)
597  {
598  return g.geometry();
599  }
600 
601  template <class Kind, class WordValue, class WeightValue, class SeriesValue,
602  class Letter, class Tag, class GeometryCoords, class I>
603  const typename BMIGRAPH::geometry_t&
604  op_geometry(const AutomataBase<I>&, const BMIGRAPH &g)
605  {
606  return g.geometry();
607  }
608 
609  BMIGRAPH_TPARAM
610  typename BMIGRAPH::graph_data_t::const_iterator
611  BMIGRAPH::find_edge(const state_t& from, const state_t& to,
612  const hlabel_t& label) const
613  {
614  succ_range r = graph_.equal_range(::boost::make_tuple(from, label));
615  for (succ_iterator i = r.first; i != r.second; ++i)
616  if (i->to_ == to)
617  return i;
618  return graph_.end();
619  }
620 
621  /*------------------.
622  | Delta functions. |
623  `------------------*/
624 
625  # define DEFINE_DELTAI_FUNCTION(DeltaKind) \
626  BMIGRAPH_TPARAM \
627  std::pair<typename BMIGRAPH::DeltaKind##_iterator, \
628  typename BMIGRAPH::DeltaKind##_iterator> \
629  BMIGRAPH::deltai(const hstate_t& s, DeltaKind##_iterator) const \
630  { \
631  assertion(has_state(s)); \
632  return graph_.template get<DeltaKind>().equal_range(s.value()); \
633  }
634 
635  DEFINE_DELTAI_FUNCTION(src);
636  DEFINE_DELTAI_FUNCTION(dst);
637  # undef DEFINE_DELTAI_FUNCTION
638 
639  BMIGRAPH_TPARAM
640  template <typename I>
641  typename BMIGRAPH::htransition_t
642  BMIGRAPH::get_htransition(const I& i) const
643  {
644  return htransition_t(graph_.project<0>(i));
645  }
646 
647  // End of syntactic sugar
648 # undef BMIGRAPH_TPARAM
649 # undef BMIGRAPH
650  } // End of namespace bmig
651 } // End of namespace vcsn
652 
653 #endif // !VCSN_AUTOMATA_IMPLEMENTATION_BMIG_GRAPH_IMPL_HXX_ //
Generated on Sat Jul 14 2012 18:46:39 for Vaucanson by   doxygen 1.8.1.1