Vaucanson  1.4.1
listg_graph_impl.hxx
1 // listg_graph_impl.hxx: this file is part of the Vaucanson project.
2 //
3 // Vaucanson, a generic library for finite state machines.
4 //
5 // Copyright (C) 2005, 2006, 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 #ifndef VCSN_AUTOMATA_IMPLEMENTATION_LISTG_GRAPH_IMPL_HXX
18 # define VCSN_AUTOMATA_IMPLEMENTATION_LISTG_GRAPH_IMPL_HXX
19 
20 # include <fstream>
21 # include <sstream>
22 
23 # include <algorithm>
24 # include <utility>
25 
26 # include <vaucanson/automata/implementation/listg_graph_impl.hh>
27 # include <vaucanson/misc/contract.hh>
28 # include <vaucanson/misc/static.hh>
29 
30 namespace vcsn
31 {
32  namespace listg
33  {
34 
35  /*--------------------.
36  | Convenient macros. |
37  `--------------------*/
38 
39  # define TParam \
40  template <class Kind, class WordValue, class WeightValue, \
41  class SeriesValue, class Letter, class Tag, class GeometryCoords>
42 
43  # define GClass \
44  Graph<Kind, WordValue, WeightValue, SeriesValue, Letter, Tag, GeometryCoords>
45 
46  /*-------------------------.
47  | Graph's implementation. |
48  `-------------------------*/
49 
50  /*---------------.
51  | Constructors. |
52  `---------------*/
53 
54  TParam
55  GClass::Graph()
56  { }
57 
58  TParam
59  GClass::Graph (unsigned initial_number_of_state,
60  unsigned reserve_number_of_edge)
61  {
62  states_.resize(initial_number_of_state);
63  edges_.reserve(reserve_number_of_edge);
64  }
65 
66  /*------------------.
67  | Basic accessors. |
68  `------------------*/
69 
70  TParam
71  typename GClass::states_t
72  GClass::states() const
73  {
74  return states_t(hstate_t(0),
75  hstate_t(states_.size() - 1),
76  removed_states_);
77  }
78 
79  TParam
80  typename GClass::edges_t
81  GClass::edges() const
82  {
83  return edges_t(hedge_t(0),
84  hedge_t(edges_.size() - 1),
85  removed_edges_);
86  }
87 
88  TParam
89  typename GClass::initial_support_t
90  GClass::initial() const
91  {
92  return initial_support_t(initial_);
93  }
94 
95  TParam
96  typename GClass::final_support_t
97  GClass::final() const
98  {
99  return final_support_t(final_);
100  }
101 
102 
103  /*----------------------.
104  | States manipulation. |
105  `----------------------*/
106 
107  TParam
108  bool
109  GClass::has_state(const hstate_t& n) const
110  {
111  bool res = (n.is_valid() &&
112  n < unsigned(states_.size()) &&
113  (removed_states_.find(n) == removed_states_.end()));
114  # ifndef VCSN_NDEBUG
115  if (res == false)
116  for (unsigned i = 0; i < edges_.size(); ++i)
117  if (removed_edges_.find(hedge_t(i)) == removed_edges_.end())
118  postcondition(edges_[i].from != n
119  && edges_[i].to != n);
120  # endif // !VCSN_NDEBUG
121  return res;
122  }
123 
124  TParam
125  typename GClass::hstate_t
126  GClass::get_state(int n) const
127  {
128  precondition(has_state(hstate_t(n)));
129  return hstate_t(n);
130  }
131 
132  TParam
133  typename GClass::hstate_t
134  GClass::add_state()
135  {
136  if (removed_states_.size() == 0)
137  {
138  states_.push_back(state_value_t());
139  return hstate_t(states_.size() - 1);
140  }
141 
142  hstate_t n = *removed_states_.begin();
143  removed_states_.erase(n);
144  assertion(n < states_.size());
145 
146  states_[n].output_edges.clear();
147  states_[n].input_edges.clear();
148 
149  postcondition(has_state(n));
150  return n;
151  }
152 
153  TParam
154  void
155  GClass::del_state(const hstate_t& n)
156  {
157  precondition (has_state(n));
158 
159  const state_value_t& v = states_[n];
160  typename state_value::edges_t::const_iterator e = v.output_edges.begin();
161  typename state_value::edges_t::const_iterator end = v.output_edges.end();
162  typename state_value::edges_t::const_iterator next = e;
163 
164  for (; e != end; e = next)
165  {
166  ++next;
167  this->del_edge(*e);
168  }
169 
170  e = v.input_edges.begin();
171  end = v.input_edges.end();
172  for (next = e; e != end; e = next)
173  {
174  ++next;
175  this->del_edge(*e);
176  }
177 
178  removed_states_.insert(n);
179  initial_.erase(n);
180  final_.erase(n);
181  postcondition(!has_state(n));
182  }
183 
184  TParam
185  void
186  GClass::set_initial(const hstate_t& n, const series_set_elt_value_t& v,
187  const series_set_elt_value_t& z)
188  {
189  precondition (has_state(n));
190  if (z == v)
191  initial_.erase(n);
192  else
193  initial_[n] = v;
194  }
195 
196  TParam
197  const typename GClass::series_set_elt_value_t&
198  GClass::get_initial(const hstate_t& n, const series_set_elt_value_t& z) const
199  {
200  precondition(has_state(n));
201  typename initial_t::const_iterator i = initial_.find(n);
202  if (i == initial_.end())
203  return z;
204  return i->second;
205  }
206 
207  TParam
208  bool
209  GClass::is_initial(const hstate_t& s, const series_set_elt_value_t& z) const
210  {
211  return get_initial(s, z) != z;
212  }
213 
214  TParam
215  void
216  GClass::clear_initial()
217  {
218  return initial_.clear();
219  }
220 
221  TParam
222  void
223  GClass::set_final(const hstate_t& n, const series_set_elt_value_t& v,
224  const series_set_elt_value_t& z)
225  {
226  precondition (has_state(n));
227  if (v == z)
228  final_.erase(n);
229  else
230  final_[n] = v;
231  }
232 
233  TParam
234  const typename GClass::series_set_elt_value_t&
235  GClass::get_final(const hstate_t& n, const series_set_elt_value_t& z) const
236  {
237  precondition (has_state(n));
238  typename final_t::const_iterator i = final_.find(n);
239  if (i == final_.end())
240  return z;
241  return i->second;
242  }
243 
244  TParam
245  bool
246  GClass::is_final(const hstate_t& s, const series_set_elt_value_t& z) const
247  {
248  return get_final(s, z) != z;
249  }
250 
251  TParam
252  void
253  GClass::clear_final()
254  {
255  return final_.clear();
256  }
257 
258 
259  /*---------------------.
260  | Edges manipulation. |
261  `---------------------*/
262 
263  TParam
264  bool
265  GClass::has_edge(const hedge_t& e) const
266  {
267  bool res = (removed_edges_.find(e) == removed_edges_.end()
268  && (e < edges_.size()));
269  # ifndef VCSN_NDEBUG
270  if (res == false)
271  for (unsigned i = 0; i < states_.size(); ++i)
272  if (removed_states_.find(hstate_t(i)) == removed_states_.end())
273  postcondition(states_[i].output_edges.find(e) ==
274  states_[i].output_edges.end());
275  # endif // !VCSN_NDEBUG
276  return res;
277  }
278 
279  TParam
280  typename GClass::hedge_t
281  GClass::add_edge(const hstate_t& n1, const hstate_t& n2,
282  const label_t& v)
283  {
284  precondition(has_state(n1));
285  precondition(has_state(n2));
286  hedge_t e;
287  if (removed_edges_.size() == 0)
288  {
289  edges_.push_back(edge_value_t(n1, n2, v));
290  e = hedge_t(edges_.size() - 1);
291  }
292  else
293  {
294  e = *removed_edges_.begin();
295  removed_edges_.erase(e);
296  assertion(e < edges_.size());
297  edges_[e].from = n1;
298  edges_[e].to = n2;
299  edges_[e].label = v;
300  }
301  states_[n1].output_edges.insert(e);
302  states_[n2].input_edges.insert(e);
303 
304  postcondition(has_edge(e));
305  return e;
306  }
307 
308  TParam
309  void
310  GClass::del_edge(const hedge_t& e)
311  {
312  precondition (has_edge(e));
313 
314  const edge_value_t& ev = edges_[e];
315  states_[ev.from].output_edges.erase(e);
316  states_[ev.to].input_edges.erase(e);
317  removed_edges_.insert(e);
318 
319  postcondition(!has_edge(e));
320  }
321 
322 
323  TParam
324  typename GClass::hstate_t
325  GClass::src_of(const hedge_t& e1) const
326  {
327  precondition(has_edge(e1));
328  return edges_[e1].from;
329  }
330 
331  TParam
332  typename GClass::hstate_t
333  GClass::dst_of(const hedge_t& e2) const
334  {
335  precondition(has_edge(e2));
336  return edges_[e2].to;
337  }
338 
339  TParam
340  const typename GClass::label_t&
341  GClass::label_of(const hedge_t& n) const
342  {
343  precondition(has_edge(n));
344  return edges_[n];
345  }
346 
347  TParam
348  void
349  GClass::update(const hedge_t& e, label_t l)
350  {
351  precondition(has_edge(e));
352  edges_[e].label = l;
353  }
354 
355 
357  TParam
358  template <class S>
359  bool
360  GClass::exists(const AutomataBase<S>& s) const
361  {
362  typename WordValue::iterator it;
363  typename label_t::const_iterator r;
364  label_t l;
365  WordValue w;
366 
367  for (unsigned i = 0; i < edges_.size(); ++i)
368  {
369  if (removed_edges_.find(hedge_t(i)) != removed_edges_.end())
370  continue;
371  // Make sure that source and destination of edge are part of the
372  // automaton.
373  if (!has_state(dst_of(hedge_t(i)))
374  || !has_state(src_of(hedge_t(i))))
375  return false;
376 
377  // Make sure that every letter of the edge is in the alphabet.
378  l = label_of(hedge_t(i));
379  for (r = l.begin(); r != l.end(); ++r)
380  {
381  w = r->first;
382  for (it = w.begin(); it != w.end(); ++it)
383  if (!s.series().monoid().alphabet().contains(*it))
384  return false;
385  }
386  }
387  return true;
388  }
389 
390  /*------.
391  | Tag. |
392  `------*/
393 
394  TParam
395  inline
396  Tag& GClass::tag()
397  {
398  return tag_;
399  }
400 
401  TParam
402  const Tag& GClass::tag() const
403  {
404  return tag_;
405  }
406 
407  template <class Kind, class WordValue, class WeightValue, class SerieValue,
408  class Letter, class Tag, class GeometryCoords, class I>
409  Tag& op_tag(const AutomataBase<I>&,
410  Graph<Kind, WordValue, WeightValue,
411  SerieValue ,Letter, Tag, GeometryCoords>& v)
412  {
413  return v.tag();
414  }
415 
416  template <class Kind, class WordValue, class WeightValue, class SerieValue,
417  class Letter, class Tag, class GeometryCoords, class I>
418  const Tag& op_tag(const AutomataBase<I>&,
419  const Graph<Kind, WordValue, WeightValue,
420  SerieValue ,Letter, Tag, GeometryCoords>& v)
421  {
422  return v.tag();
423  }
424 
425 
426  /*-----------.
427  | Geometry. |
428  `-----------*/
429 
430  template <class Kind, class WordValue, class WeightValue, class SeriesValue,
431  class Letter, class Tag, class GeometryCoords, class I>
432  typename GClass::geometry_t&
433  op_geometry(const AutomataBase<I>&,
434  Graph<Kind, WordValue, WeightValue,
435  SeriesValue, Letter, Tag, GeometryCoords>& v)
436  {
437  return v.geometry();
438  }
439 
440  template <class Kind, class WordValue, class WeightValue, class SeriesValue,
441  class Letter, class Tag, class GeometryCoords, class I>
442  const typename GClass::geometry_t&
443  op_geometry(const AutomataBase<I>&,
444  const Graph<Kind, WordValue, WeightValue,
445  SeriesValue, Letter, Tag, GeometryCoords>& v)
446  {
447  return v.geometry();
448  }
449 
450 
451  TParam
452  const typename GClass::geometry_t&
453  GClass::geometry() const
454  {
455  return geometry_;
456  }
457 
458  TParam
459  typename GClass::geometry_t&
460  GClass::geometry()
461  {
462  return geometry_;
463  }
464 
465 
466  // Remove macros to avoid name clashes.
467 # undef TParam
468 # undef GClass
469  }
470 }
471 
472 #endif // ! VCSN_AUTOMATA_IMPLEMENTATION_LISTG_GRAPH_IMPL_HXX
Generated on Sat Jul 14 2012 18:46:40 for Vaucanson by   doxygen 1.8.1.1