|
Vaucanson 1.4
|
00001 // boost_graph.hxx: this file is part of the Vaucanson project. 00002 // 00003 // Vaucanson, a generic library for finite state machines. 00004 // 00005 // Copyright (C) 2007, 2008 The Vaucanson Group. 00006 // 00007 // This program is free software; you can redistribute it and/or 00008 // modify it under the terms of the GNU General Public License 00009 // as published by the Free Software Foundation; either version 2 00010 // of the License, or (at your option) any later version. 00011 // 00012 // The complete GNU General Public Licence Notice can be found as the 00013 // `COPYING' file in the root directory. 00014 // 00015 // The Vaucanson Group consists of people listed in the `AUTHORS' file. 00016 // 00017 00018 #ifndef VCSN_AUTOMATA_IMPLEMENTATION_BMIG_GRAPH_IMPL_HXX_ 00019 # define VCSN_AUTOMATA_IMPLEMENTATION_BMIG_GRAPH_IMPL_HXX_ 00020 00021 # include <vaucanson/automata/implementation/bmig_graph_impl.hh> 00022 00023 namespace vcsn 00024 { 00025 namespace bmig 00026 { 00027 00028 /*--------------------. 00029 | Convenient macros. | 00030 `--------------------*/ 00031 00032 # define BMIGRAPH_TPARAM \ 00033 template <class Kind, class WordValue, class WeightValue, \ 00034 class SeriesValue, class Letter, class Tag, class GeometryCoords> 00035 00036 # define BMIGRAPH \ 00037 Graph<Kind, WordValue, WeightValue, SeriesValue, Letter, Tag, GeometryCoords> 00038 00039 /*-------------------------. 00040 | Graph's implementation. | 00041 `-------------------------*/ 00042 00043 /*---------------. 00044 | Constructors. | 00045 `---------------*/ 00046 00047 BMIGRAPH_TPARAM 00048 BMIGRAPH::Graph () 00049 : initial_bitset_(0), 00050 final_bitset_(0), 00051 number_of_epsilon_(0), 00052 number_of_state_(0) 00053 { 00054 } 00055 00065 BMIGRAPH_TPARAM 00066 BMIGRAPH::Graph (unsigned initial_number_of_states, 00067 unsigned) 00068 : initial_bitset_(initial_number_of_states), 00069 final_bitset_(initial_number_of_states), 00070 number_of_epsilon_(0), 00071 number_of_state_(initial_number_of_states), 00072 states_(initial_number_of_states) 00073 { 00074 for (unsigned i = 0; i < initial_number_of_states; ++i) 00075 { 00076 boost::shared_ptr<std::size_t> p(new std::size_t(i)); 00077 states_[i] = p; 00078 } 00079 } 00080 00081 BMIGRAPH_TPARAM 00082 BMIGRAPH::Graph (const self_t& g) 00083 { 00084 tag_ = g.tag_; 00085 initial_bitset_ = g.initial_bitset_; 00086 final_bitset_ = g.final_bitset_; 00087 number_of_epsilon_ = g.number_of_epsilon_; 00088 number_of_state_ = g.number_of_state_; 00089 label_container_ = g.label_container_; 00090 initial_.clear(); 00091 final_.clear(); 00092 states_.resize(g.number_of_state_); 00093 for (unsigned i = 0; i < g.number_of_state_; ++i) 00094 { 00095 boost::shared_ptr<std::size_t> p(new std::size_t(i)); 00096 states_[i] = p; 00097 } 00098 graph_.clear(); 00099 for (typename graph_data_t::const_iterator i = g.graph_.begin(); 00100 i != g.graph_.end(); 00101 ++i) 00102 graph_.insert(edge_data_t(states_[*i->from_], 00103 states_[*i->to_], 00104 i->label_)); 00105 // label_container_.get_hlabel(g.label_container_.get_label(i->label_)))); 00106 # define VCSN_COPY_I_T(Set) \ 00107 for (typename Set##t::const_iterator i = g.Set.begin(); \ 00108 i != g.Set.end(); \ 00109 ++i) \ 00110 Set.insert(initial_value_t (states_[*i->first], i->second)); 00111 VCSN_COPY_I_T(initial_) 00112 VCSN_COPY_I_T(final_) 00113 # undef VCSN_COPY_I_T 00114 00115 # define VCSN_COPY_GEOMETRY(Type) \ 00116 { \ 00117 typename geometry_t::Type##_geometry_map_t& map_##Type = geometry_.Type(); \ 00118 map_##Type.clear(); \ 00119 for (typename geometry_t::Type##_geometry_map_t::const_iterator i = g.geometry_.Type().begin(); \ 00120 i != g.geometry_.Type().end(); \ 00121 ++i) \ 00122 map_##Type[i->first] = i->second; \ 00123 } 00124 VCSN_COPY_GEOMETRY(states) 00125 VCSN_COPY_GEOMETRY(initials) 00126 VCSN_COPY_GEOMETRY(finals) 00127 # undef VCSN_COPY_GEOMETRY 00128 { 00129 typename geometry_t::transitions_geometry_map_t& map_transitions = geometry_.transitions(); 00130 map_transitions.clear(); 00131 for (typename geometry_t::transitions_geometry_map_t::const_iterator i = g.geometry_.transitions().begin(); 00132 i != g.geometry_.transitions().end(); 00133 ++i) 00134 { 00135 typename graph_data_t::const_iterator tmp = find_edge(states_[*i->first.value()->from_], 00136 states_[*i->first.value()->to_], 00137 i->first.value()->label_); 00138 //label_container_.get_hlabel(g.label_container_.get_label(i->first.value()->label_))); 00139 if (tmp != graph_.end()) 00140 map_transitions[htransition_t(tmp)] = i->second; 00141 } 00142 } 00143 } 00144 00145 /*--------------. 00146 | Destructors. | 00147 `--------------*/ 00148 00149 BMIGRAPH_TPARAM 00150 BMIGRAPH::~Graph () 00151 { 00152 } 00153 00154 BMIGRAPH_TPARAM 00155 typename BMIGRAPH::self_t& 00156 BMIGRAPH::operator= (const self_t& g) 00157 { 00158 if (this == &g) 00159 return *this; 00160 tag_ = g.tag_; 00161 initial_bitset_ = g.initial_bitset_; 00162 final_bitset_ = g.final_bitset_; 00163 number_of_epsilon_ = g.number_of_epsilon_; 00164 number_of_state_ = g.number_of_state_; 00165 label_container_ = g.label_container_; 00166 initial_.clear(); 00167 final_.clear(); 00168 states_.resize(g.number_of_state_); 00169 for (unsigned i = 0; i < g.number_of_state_; ++i) 00170 { 00171 boost::shared_ptr<std::size_t> p(new std::size_t(i)); 00172 states_[i] = p; 00173 } 00174 graph_.clear(); 00175 for (typename graph_data_t::const_iterator i = g.graph_.begin(); 00176 i != g.graph_.end(); 00177 ++i) 00178 graph_.insert(edge_data_t(states_[*i->from_], 00179 states_[*i->to_], 00180 i->label_)); 00181 # define VCSN_COPY_I_T(Set) \ 00182 for (typename Set##t::const_iterator i = g.Set.begin(); \ 00183 i != g.Set.end(); \ 00184 ++i) \ 00185 Set.insert(initial_value_t (states_[*i->first], i->second)); 00186 VCSN_COPY_I_T(initial_) 00187 VCSN_COPY_I_T(final_) 00188 # undef VCSN_COPY_I_T 00189 00190 # define VCSN_COPY_GEOMETRY(Type) \ 00191 { \ 00192 typename geometry_t::Type##_geometry_map_t& map_##Type = geometry_.Type(); \ 00193 map_##Type.clear(); \ 00194 for (typename geometry_t::Type##_geometry_map_t::const_iterator i = g.geometry_.Type().begin(); \ 00195 i != g.geometry_.Type().end(); \ 00196 ++i) \ 00197 map_##Type[i->first] = i->second; \ 00198 } 00199 VCSN_COPY_GEOMETRY(states) 00200 VCSN_COPY_GEOMETRY(initials) 00201 VCSN_COPY_GEOMETRY(finals) 00202 # undef VCSN_COPY_GEOMETRY 00203 { 00204 typename geometry_t::transitions_geometry_map_t& map_transitions = geometry_.transitions(); 00205 map_transitions.clear(); 00206 for (typename geometry_t::transitions_geometry_map_t::const_iterator i = g.geometry_.transitions().begin(); 00207 i != g.geometry_.transitions().end(); 00208 ++i) 00209 { 00210 typename graph_data_t::const_iterator tmp = find_edge(states_[*i->first.value()->from_], 00211 states_[*i->first.value()->to_], 00212 i->first.value()->label_); 00213 //label_container_.get_hlabel(g.label_container_.get_label(i->first.value()->label_))); 00214 if (tmp != graph_.end()) 00215 map_transitions[htransition_t(tmp)] = i->second; 00216 } 00217 } 00218 return *this; 00219 } 00220 00221 /*------------------. 00222 | Basic accessors. | 00223 `------------------*/ 00224 00225 BMIGRAPH_TPARAM 00226 typename BMIGRAPH::states_t 00227 BMIGRAPH::states() const 00228 { 00229 return misc::Support<states_data_t>(states_); 00230 } 00231 00232 BMIGRAPH_TPARAM 00233 typename BMIGRAPH::edges_t 00234 BMIGRAPH::edges() const 00235 { 00236 return edges_t(graph_); 00237 } 00238 00239 BMIGRAPH_TPARAM 00240 typename BMIGRAPH::initial_support_t 00241 BMIGRAPH::initial () const 00242 { 00243 return initial_support_t(initial_); 00244 } 00245 00246 BMIGRAPH_TPARAM 00247 typename BMIGRAPH::final_support_t 00248 BMIGRAPH::final () const 00249 { 00250 return final_support_t(final_); 00251 } 00252 00253 00254 /*----------------------. 00255 | State manipulations. | 00256 `----------------------*/ 00257 00258 BMIGRAPH_TPARAM 00259 bool 00260 BMIGRAPH::has_state (const hstate_t& s) const 00261 { 00262 // May be we should add a set or a hashtable to have 00263 // a searching time better than linear 00264 bool b = false; 00265 for_all_iterator(states_data_t::const_iterator, i, states_) 00266 if (*i == s.value()) 00267 b = true; 00268 return b; 00269 } 00270 00271 BMIGRAPH_TPARAM 00272 typename BMIGRAPH::hstate_t 00273 BMIGRAPH::add_state () 00274 { 00275 initial_bitset_.append(false); 00276 final_bitset_.append(false); 00277 boost::shared_ptr<std::size_t> p(new std::size_t(number_of_state_++)); 00278 state_t h(p); 00279 states_.push_back(h); 00280 return hstate_t(h); 00281 } 00282 00283 BMIGRAPH_TPARAM 00284 typename BMIGRAPH::hstate_t 00285 BMIGRAPH::get_state (unsigned s) const 00286 { 00287 precondition(s < states_.size()); 00288 return hstate_t(states_[s]); 00289 } 00290 00291 BMIGRAPH_TPARAM 00292 void 00293 BMIGRAPH::del_state (const hstate_t& s) 00294 { 00295 precondition (has_state(s)); 00296 00297 // One removes the state h 00298 graph_.template get<src>().erase(s.value()); 00299 graph_.template get<dst>().erase(s.value()); 00300 00301 if (s != (number_of_state_ - 1) && (number_of_state_ - 1)) 00302 { 00303 state_t lastone = states_.back(); 00304 states_[s] = lastone; 00305 # define VCSN_UPDATE(Set) \ 00306 if (Set##bitset_[*lastone]) \ 00307 { \ 00308 if (Set##bitset_[s]) \ 00309 Set.erase(s.value()); \ 00310 else \ 00311 Set##bitset_[s] = true; \ 00312 } \ 00313 else \ 00314 { \ 00315 if (Set##bitset_[s]) \ 00316 { \ 00317 Set##bitset_[s] = false; \ 00318 Set.erase(s.value()); \ 00319 } \ 00320 } 00321 00322 //Updating initial/final states information 00323 VCSN_UPDATE(initial_) 00324 VCSN_UPDATE(final_) 00325 # undef VCSN_UPDATE 00326 *lastone = *s.value(); 00327 } 00328 else 00329 { 00330 initial_.erase(s.value()); 00331 final_.erase(s.value()); 00332 } 00333 00334 --number_of_state_; 00335 states_.pop_back(); 00336 postcondition(states_.size() == number_of_state_); 00337 //delete s.value(); 00338 initial_bitset_.resize(number_of_state_); 00339 final_bitset_.resize(number_of_state_); 00340 00341 //Useless postcondition since the states are 'renamed' 00342 //postcondition(!has_state(h)); 00343 } 00344 00345 BMIGRAPH_TPARAM 00346 void 00347 BMIGRAPH::set_initial (const hstate_t& s, 00348 const series_set_elt_value_t& v, 00349 const series_set_elt_value_t& z) 00350 { 00351 precondition(has_state(s)); 00352 if (z == v) 00353 { 00354 initial_.erase (s.value()); 00355 initial_bitset_[s] = false; 00356 } 00357 else if (!initial_bitset_[s]) 00358 { 00359 initial_.insert (initial_value_t (s.value(), v)); 00360 initial_bitset_[s] = true; 00361 } 00362 else 00363 initial_.modify(initial_.find(s.value()), update_label<initial_value_t>(v)); 00364 } 00365 00366 BMIGRAPH_TPARAM 00367 const typename BMIGRAPH::series_set_elt_value_t& 00368 BMIGRAPH::get_initial(const hstate_t& s, const series_set_elt_value_t &zero) const 00369 { 00370 precondition(has_state(s)); 00371 typename initial_t::const_iterator it = initial_.find(s.value()); 00372 00373 if (it == initial_.end()) 00374 return zero; 00375 return it->second; 00376 } 00377 00378 BMIGRAPH_TPARAM 00379 bool 00380 BMIGRAPH::is_initial(const hstate_t& s, const series_set_elt_value_t&) const 00381 { 00382 precondition(has_state(s)); 00383 return initial_bitset_[s]; 00384 } 00385 00386 BMIGRAPH_TPARAM 00387 void 00388 BMIGRAPH::clear_initial() 00389 { 00390 initial_.clear(); 00391 initial_bitset_.reset(); 00392 } 00393 00394 BMIGRAPH_TPARAM 00395 void 00396 BMIGRAPH::set_final(const hstate_t& s, 00397 const series_set_elt_value_t& v, 00398 const series_set_elt_value_t& z) 00399 { 00400 precondition(has_state(s)); 00401 if (z == v) 00402 { 00403 final_.erase (s.value()); 00404 final_bitset_[s] = false; 00405 } 00406 else if (!final_bitset_[s]) 00407 { 00408 final_.insert (initial_value_t (s.value(), v)); 00409 final_bitset_[s] = true; 00410 } 00411 else 00412 final_.modify(final_.find(s.value()), update_label<final_value_t>(v)); 00413 } 00414 00415 BMIGRAPH_TPARAM 00416 const typename BMIGRAPH::series_set_elt_value_t& 00417 BMIGRAPH::get_final(const hstate_t& s, const series_set_elt_value_t &zero) const 00418 { 00419 precondition(has_state(s)); 00420 typename final_t::const_iterator it = final_.find(s.value()); 00421 00422 if (it == final_.end()) 00423 return zero; 00424 return it->second; 00425 } 00426 00427 BMIGRAPH_TPARAM 00428 bool 00429 BMIGRAPH::is_final(const hstate_t& s, const series_set_elt_value_t&) const 00430 { 00431 precondition(has_state(s)); 00432 return final_bitset_[s]; 00433 } 00434 00435 BMIGRAPH_TPARAM 00436 void 00437 BMIGRAPH::clear_final() 00438 { 00439 final_.clear(); 00440 final_bitset_.reset(); 00441 } 00442 00443 /*---------------------. 00444 | Edge manipulations. | 00445 `---------------------*/ 00446 00447 BMIGRAPH_TPARAM 00448 bool 00449 BMIGRAPH::has_edge (const hedge_t& h) const 00450 { 00451 succ_range r = graph_.equal_range(boost::make_tuple(h.value()->from_, 00452 h.value()->label_)); 00453 succ_iterator it; 00454 state_t to = h.value()->to_; 00455 for (it = r.first; it != r.second && it->to_ != to; ++it) 00456 /*Nothing*/; 00457 00458 return it != r.second; 00459 } 00460 00461 BMIGRAPH_TPARAM 00462 typename BMIGRAPH::hedge_t 00463 BMIGRAPH::add_edge (const hstate_t& from, const hstate_t& to, const label_t& l) 00464 { 00465 //hlabel_t hl = label_container_.insert (l); 00466 return hedge_t (graph_.insert (edge_data_t (from.value(), to.value(), l)).first); 00467 } 00468 00469 BMIGRAPH_TPARAM 00470 void 00471 BMIGRAPH::del_edge (const hedge_t& h) 00472 { 00473 precondition (has_edge(h)); 00474 00475 hlabel_t l = h.value()->label_; 00476 graph_.erase(h.value()); 00477 //label_container_.erase(l); 00478 00479 // h points to an invalid edgeValue since it is already destroyed. 00480 // We can't check this postcondition anymore! 00481 //postcondition(!has_edge(h)); 00482 } 00483 00484 BMIGRAPH_TPARAM 00485 typename BMIGRAPH::hstate_t 00486 BMIGRAPH::src_of (const hedge_t& h) const 00487 { 00488 return hstate_t(h.value()->from_); 00489 } 00490 00491 BMIGRAPH_TPARAM 00492 typename BMIGRAPH::hstate_t 00493 BMIGRAPH::dst_of (const hedge_t& h) const 00494 { 00495 return hstate_t(h.value()->to_); 00496 } 00497 00498 BMIGRAPH_TPARAM 00499 const typename BMIGRAPH::label_t& 00500 BMIGRAPH::label_of (const hedge_t& h) const 00501 { 00502 return h.value()->label_; 00503 // return label_container_.get_label(h.value()->label_); 00504 } 00505 00506 BMIGRAPH_TPARAM 00507 void 00508 BMIGRAPH::update(const hedge_t& h, const label_t& l) 00509 { 00510 label_container_.update(h->label_, l); 00511 graph_.modify(h.value(), update_hlabel<hlabel_t>(h->label_)); 00512 } 00513 00514 BMIGRAPH_TPARAM 00515 template <class S> 00516 bool 00517 BMIGRAPH::exists (const AutomataBase<S>& s) const 00518 { 00519 typename WordValue::iterator it; 00520 typename label_t::const_iterator r; 00521 label_t l; 00522 WordValue w; 00523 00524 for (typename graph_data_t::iterator i = graph_.begin(); i != graph_.end(); ++i) 00525 { 00526 // Make sure that source and destination of edge are part of the 00527 // automaton. 00528 if (!has_state(dst_of(hedge_t(i))) || 00529 !has_state(src_of(hedge_t(i)))) 00530 return false; 00531 00532 // Make sure that every letter of the edge is in the alphabet. 00533 l = label_of(hedge_t(i)); 00534 for (r = l.begin(); r != l.end(); ++r) 00535 { 00536 w = r->first; 00537 for (it = w.begin(); it != w.end(); ++it) 00538 if (!s.series().monoid().alphabet().contains(*it)) 00539 return false; 00540 } 00541 } 00542 return true; 00543 } 00544 00545 BMIGRAPH_TPARAM 00546 inline 00547 typename BMIGRAPH::tag_t& 00548 BMIGRAPH::tag () 00549 { 00550 return tag_; 00551 } 00552 00553 BMIGRAPH_TPARAM 00554 inline 00555 const typename BMIGRAPH::tag_t& 00556 BMIGRAPH::tag () const 00557 { 00558 return tag_; 00559 } 00560 00561 BMIGRAPH_TPARAM 00562 inline 00563 typename BMIGRAPH::geometry_t& 00564 BMIGRAPH::geometry () 00565 { 00566 return geometry_; 00567 } 00568 00569 BMIGRAPH_TPARAM 00570 inline 00571 const typename BMIGRAPH::geometry_t& 00572 BMIGRAPH::geometry () const 00573 { 00574 return geometry_; 00575 } 00576 00577 template <class Kind, class WordValue, class WeightValue, class SeriesValue, 00578 class Letter, class Tag, class GeometryCoords, class I> 00579 Tag& 00580 op_tag(const AutomataBase<I>&, BMIGRAPH &g) 00581 { 00582 return g.tag(); 00583 } 00584 00585 template <class Kind, class WordValue, class WeightValue, class SeriesValue, 00586 class Letter, class Tag, class GeometryCoords, class I> 00587 const Tag& 00588 op_tag(const AutomataBase<I>&, BMIGRAPH &g) 00589 { 00590 return g.tag(); 00591 } 00592 00593 template <class Kind, class WordValue, class WeightValue, class SeriesValue, 00594 class Letter, class Tag, class GeometryCoords, class I> 00595 typename BMIGRAPH::geometry_t& 00596 op_geometry(const AutomataBase<I>&, BMIGRAPH &g) 00597 { 00598 return g.geometry(); 00599 } 00600 00601 template <class Kind, class WordValue, class WeightValue, class SeriesValue, 00602 class Letter, class Tag, class GeometryCoords, class I> 00603 const typename BMIGRAPH::geometry_t& 00604 op_geometry(const AutomataBase<I>&, const BMIGRAPH &g) 00605 { 00606 return g.geometry(); 00607 } 00608 00609 BMIGRAPH_TPARAM 00610 typename BMIGRAPH::graph_data_t::const_iterator 00611 BMIGRAPH::find_edge(const state_t& from, const state_t& to, 00612 const hlabel_t& label) const 00613 { 00614 succ_range r = graph_.equal_range(::boost::make_tuple(from, label)); 00615 for (succ_iterator i = r.first; i != r.second; ++i) 00616 if (i->to_ == to) 00617 return i; 00618 return graph_.end(); 00619 } 00620 00621 /*------------------. 00622 | Delta functions. | 00623 `------------------*/ 00624 00625 # define DEFINE_DELTAI_FUNCTION(DeltaKind) \ 00626 BMIGRAPH_TPARAM \ 00627 std::pair<typename BMIGRAPH::DeltaKind##_iterator, \ 00628 typename BMIGRAPH::DeltaKind##_iterator> \ 00629 BMIGRAPH::deltai(const hstate_t& s, DeltaKind##_iterator) const \ 00630 { \ 00631 assertion(has_state(s)); \ 00632 return graph_.template get<DeltaKind>().equal_range(s.value()); \ 00633 } 00634 00635 DEFINE_DELTAI_FUNCTION(src); 00636 DEFINE_DELTAI_FUNCTION(dst); 00637 # undef DEFINE_DELTAI_FUNCTION 00638 00639 BMIGRAPH_TPARAM 00640 template <typename I> 00641 typename BMIGRAPH::htransition_t 00642 BMIGRAPH::get_htransition(const I& i) const 00643 { 00644 return htransition_t(graph_.project<0>(i)); 00645 } 00646 00647 // End of syntactic sugar 00648 # undef BMIGRAPH_TPARAM 00649 # undef BMIGRAPH 00650 } // End of namespace bmig 00651 } // End of namespace vcsn 00652 00653 #endif // !VCSN_AUTOMATA_IMPLEMENTATION_BMIG_GRAPH_IMPL_HXX_ //
1.7.4