00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00030 #ifndef __VGTL_DAG_H_
00031 #define __VGTL_DAG_H_
00032
00033 #include <vector>
00034 #include <map>
00035 #include <list>
00036 #include <algorithm>
00037 #include <iterator>
00038 #include <string>
00039 #include <utility>
00040
00041 #include <vgtl_helpers.h>
00042 #include <vgtl_intadapt.h>
00043
00044 #include <vgtl_dagbase.h>
00045
00046 __VGTL_BEGIN_NAMESPACE
00047
00048
00049 template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator>
00050 class _DG_iterator;
00051
00053
00058 template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator>
00059 class _DG_walker
00060 {
00061 public:
00062 typedef _DG_walker<_Tp,_Tp&,_Tp*,_Ctr,_Iterator> walker;
00063 typedef _DG_walker<_Tp,const _Tp&,const _Tp*,_Ctr,_Iterator> const_walker;
00064
00065 private:
00066 typedef _DG_walker<_Tp,_Ref,_Ptr,_Ctr,_Iterator> _Self;
00067 typedef _DG_iterator<_Tp,_Ref,_Ptr,_Ctr,_Iterator> _Itr;
00068
00069 public:
00071
00072 typedef _Tp value_type;
00073 typedef _Ptr pointer;
00074 typedef _Ref reference;
00076
00077 private:
00078 typedef _DG_node<_Tp,_Ctr,_Iterator> _Node;
00079 typedef _Iterator _Ctr_iterator;
00080
00081 public:
00083
00084 typedef _Ctr_iterator children_iterator;
00085 typedef _Ctr_iterator parents_iterator;
00086 typedef _Node node_type;
00087
00088 typedef size_t size_type;
00089 typedef ptrdiff_t difference_type;
00091
00092 public:
00094 _Node* _C_w_cur;
00095
00096 public:
00098 _DG_walker() {}
00099
00100 public:
00102 _DG_walker(_Node* __x) : _C_w_cur(__x) { }
00103
00105 _DG_walker(const walker& __x) : _C_w_cur(__x._C_w_cur) {}
00106
00108 reference operator*() const { return (*_C_w_cur)._C_data; }
00109
00110 #ifndef __SGI_STL_NO_ARROW_OPERATOR
00111
00112 pointer operator->() const { return &(operator*()); }
00113 #endif
00114
00115 public:
00117 const _Node* node() { return _C_w_cur; }
00118
00120 size_type n_children() const { return (*_C_w_cur)._C_children.size(); }
00122 size_type n_parents() const { return (*_C_w_cur)._C_parents.size(); }
00123
00125 bool is_root() const
00126 { if(n_parents() != 1)
00127 return false;
00128 else
00129 {
00130 _Node* __help = (_Node*)*((*_C_w_cur)._C_parents.begin());
00131 return (*__help)._C_parents.empty();
00132 }
00133 }
00135 bool is_leaf() const
00136 { if(n_children() != 1)
00137 return false;
00138 else
00139 {
00140 _Node* __help = (_Node*)*((*_C_w_cur)._C_children.begin());
00141 return (*__help)._C_children.empty();
00142 }
00143 }
00144
00146 bool is_ground() const { return (*_C_w_cur)._C_parents.empty(); }
00148 bool is_sky() const { return (*_C_w_cur)._C_children.empty(); }
00149
00151 children_iterator child_begin() { return (*_C_w_cur)._C_children.begin(); }
00153 children_iterator child_end() { return (*_C_w_cur)._C_children.end(); }
00154
00156 parents_iterator parent_begin() { return (*_C_w_cur)._C_parents.begin(); }
00158 parents_iterator parent_end() { return (*_C_w_cur)._C_parents.end(); }
00159
00161 template <class _Function>
00162 _Function for_each_child(_Function __f)
00163 {
00164 return for_each(child_begin(), child_end(), __f);
00165 }
00167 template <class _Function>
00168 _Function for_each_parent(_Function __f)
00169 {
00170 return for_each(parent_begin(), parent_end(), __f);
00171 }
00172
00173 public:
00175
00176 bool operator==(const _Self& __x) const
00177 { return _C_w_cur == __x._C_w_cur; }
00178 bool operator!=(const _Self& __x) const
00179 { return _C_w_cur != __x._C_w_cur; }
00181
00183 _Self operator<<(parents_iterator __i) {
00184 _Self __tmp = *this;
00185 __tmp._C_w_cur = (_Node*) *__i;
00186 return __tmp;
00187 }
00188
00190 _Self operator>>(children_iterator __i) {
00191 _Self __tmp = *this;
00192 __tmp._C_w_cur = (_Node*) *__i;
00193 return __tmp;
00194 }
00195
00197 _Self& operator<<=(parents_iterator __i) {
00198 _C_w_cur = (_Node*) *__i;
00199 return *this;
00200 }
00201
00203 _Self& operator>>=(children_iterator __i) {
00204 _C_w_cur = (_Node*) *__i;
00205 return *this;
00206 }
00207
00209 _Self& operator=(const _Itr& __x) {
00210 _C_w_cur = __x._C_i_cur;
00211 return *this;
00212 }
00213
00215 _Self& operator=(const _Self& __x) {
00216 _C_w_cur = __x._C_w_cur;
00217 return *this;
00218 }
00219
00221 _Self& operator=(const _Node& __n) {
00222 _C_w_cur = &__n;
00223 return *this;
00224 }
00225 };
00226
00228
00234 template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator>
00235 class _DG_iterator
00236 {
00237 public:
00238 typedef _DG_iterator<_Tp,_Tp&,_Tp*,_Ctr,_Iterator> iterator;
00239 typedef _DG_iterator<_Tp,const _Tp&,const _Tp*,_Ctr,_Iterator> const_iterator;
00240 typedef _DG_iterator<_Tp,_Ref,_Ptr,_Ctr,_Iterator> _Self;
00241 typedef _DG_walker<_Tp,_Ref,_Ptr,_Ctr,_Iterator> _Walk;
00242
00244
00245 typedef std::bidirectional_iterator_tag iterator_category;
00246 typedef _Tp value_type;
00247 typedef _Ptr pointer;
00248 typedef _Ref reference;
00249 typedef _DG_node<_Tp,_Ctr,_Iterator> _Node;
00250 typedef size_t size_type;
00251 typedef ptrdiff_t difference_type;
00253 typedef _Iterator _Ctr_iterator;
00254
00255 protected:
00257 _Node* _C_i_cur;
00259 std::vector<_Ctr_iterator> _C_i_cur_it;
00260
00261 public:
00263 _DG_iterator() : _C_i_cur_it() {_C_i_cur_it.reserve(32);}
00265 _DG_iterator(const iterator& __x) : _C_i_cur(__x._C_i_cur),
00266 _C_i_cur_it(__x._C_i_cur_it) {}
00267
00269
00270 bool operator==(const _Self& __x) const
00271 { return (_C_i_cur->_C_parents.empty() &&
00272 __x._C_i_cur->_C_parents.empty()) ||
00273 (_C_i_cur->_C_children.empty() &&
00274 __x._C_i_cur->_C_children.empty()) ||
00275 ( _C_i_cur == __x._C_i_cur &&
00276 _C_i_cur_it == __x._C_i_cur_it);
00277 }
00278 bool operator!=(const _Self& __x) const
00279 { return (!_C_i_cur->_C_parents.empty() ||
00280 !__x._C_i_cur->_C_parents.empty()) &&
00281 (!_C_i_cur->_C_children.empty() ||
00282 !__x._C_i_cur->_C_children.empty()) &&
00283 ( _C_i_cur != __x._C_i_cur ||
00284 _C_i_cur_it != __x._C_i_cur_it);
00285 }
00287
00288 reference operator*() const { return (*_C_i_cur)._C_data; }
00289
00290 #ifndef __SGI_STL_NO_ARROW_OPERATOR
00291
00292 pointer operator->() const { return &(operator*()); }
00293 #endif
00294
00295 private:
00297 void find_start_node();
00299 void find_next_node();
00301 void find_prev_node();
00302
00303 public:
00305 _Self& operator=(const _Walk& __x) {
00306 _C_i_cur = __x._C_w_cur;
00307 _C_i_cur_it.erase(_C_i_cur_it.begin(), _C_i_cur_it.end());
00308
00309
00310 find_start_node();
00311 return *this;
00312 }
00313
00315
00316 _Self& operator++() {
00317 find_next_node();
00318 return *this;
00319 }
00320 _Self operator++(int) {
00321 _Self __tmp = *this;
00322 ++*this;
00323 return __tmp;
00324 }
00325
00326 _Self& operator--() {
00327 find_prev_node();
00328 return *this;
00329 }
00330 _Self operator--(int) {
00331 _Self __tmp = *this;
00332 --*this;
00333 return __tmp;
00334 }
00336 };
00337
00338 #ifndef __VGTL_CLASS_PARTIAL_SPECIALIZATION // Specifies the iterator to be bi-directional.
00339 template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator>
00340 inline bidirectional_iterator_tag
00341 iterator_category(const _DG_iterator<_Tp,_Ref,_Ptr,_Ctr,_Iterator>&)
00342 {
00343 return bidirectional_iterator_tag();
00344 }
00345
00346 template <class _Tp, class _Ref, class _Ptr, class _Ct, class _Iterator>
00347 inline _Tp*
00348 value_type(const _DG_iterator<_Tp,_Ref,_Ptr,_Ctr,_Iterator>&)
00349 {
00350 return 0;
00351 }
00352
00353
00354
00355
00356
00357 template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator>
00358 inline ptrdiff_t*
00359 distance_type(const _DG_iterator<_Tp,_Ref,_Ptr,_Ctr,_Iterator>&)
00360 {
00361 return 0;
00362 }
00363
00364 #endif
00365
00366
00367
00368
00369
00370 template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator>
00371 void
00372 _DG_iterator<_Tp,_Ref,_Ptr,_Ctr,_Iterator>::find_start_node()
00373 {
00374 _Node* __s = _C_i_cur;
00375 _Ctr_iterator __help;
00376
00377 while(!__s->_C_parents.empty())
00378 {
00379 __help = ((_Node*)*__s->_C_parents.begin());
00380 _C_i_cur_it.insert(_C_i_cur_it.begin(),
00381 __help->get_entry_iterator((void*)__s));
00382 __s = __help;
00383 }
00384 while(!_C_i_cur->_C_children.empty())
00385 {
00386
00387 for(__help = _C_i_cur->_C_children.begin();
00388 __help != _C_i_cur->_C_children.end(); ++__help)
00389 {
00390 __s = (_Node*)*__help;
00391 if(*(__s->_C_parents.begin()) == (void*)_C_i_cur)
00392 break;
00393 }
00394 if(__help == _C_i_cur->_C_children.end())
00395 break;
00396 _C_i_cur = __s;
00397 _C_i_cur_it.push_back(__help);
00398 }
00399 if(_C_i_cur->_C_children.empty())
00400 {
00401 __help = _C_i_cur_it.back();
00402 _C_i_cur_it.pop_back();
00403 _C_i_cur = (_Node*)*__help;
00404 }
00405 }
00406
00407
00408
00409
00410
00411 template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator>
00412 void
00413 _DG_iterator<_Tp,_Ref,_Ptr,_Ctr,_Iterator>::find_next_node()
00414 {
00415 if(!_C_i_cur->_C_parents.empty())
00416 {
00417 _Ctr_iterator __help(_C_i_cur_it.back());
00418 _Node* __par;
00419
00420 _C_i_cur_it.pop_back();
00421 __par = (_Node*)*(_C_i_cur->_C_parents.begin());
00422
00423 for(++__help; __help != __par->_C_children.end(); ++__help)
00424 {
00425 _Node* __s = (_Node*)*__help;
00426 if(*(__s->_C_parents.begin()) == (void*)_C_i_cur)
00427 {
00428 _C_i_cur_it.push_back(__help);
00429 _C_i_cur = __s;
00430 while(!_C_i_cur->_C_children.empty());
00431 {
00432 for(__help = _C_i_cur->_C_children.begin();
00433 __help != _C_i_cur->_C_children.end(); ++__help)
00434 {
00435 __s = (_Node*)*__help;
00436 if(*(__s->_C_parents.begin()) == (void*)_C_i_cur)
00437 break;
00438 }
00439 if(__help == _C_i_cur->_C_children.end())
00440 break;
00441 _C_i_cur = __s;
00442 _C_i_cur_it.push_back(__help);
00443 }
00444 break;
00445 }
00446 }
00447 if(__help == __par->_C_children.end())
00448 {
00449 _C_i_cur = __par;
00450 }
00451 else if(_C_i_cur->_C_children.empty())
00452 {
00453 __help = _C_i_cur_it.back();
00454 _C_i_cur_it.pop_back();
00455 _C_i_cur = (_Node*)*__help;
00456 }
00457 }
00458 }
00459
00460
00461
00462
00463 template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator>
00464 void
00465 _DG_iterator<_Tp,_Ref,_Ptr,_Ctr,_Iterator>::find_prev_node()
00466 {
00467 #if 0
00468
00469 _Ctr_iterator help;
00470
00471 if(_C_i_cur->_C_children.empty())
00472 {
00473 while(1)
00474 {
00475 if(_C_i_cur->_C_parent == NULL)
00476 break;
00477 help = _C_i_cur_it.back();
00478 _C_i_cur_it.pop_back();
00479 _C_i_cur = (_Node*)_C_i_cur->_C_parent;
00480 if(help != _C_i_cur->_C_children.begin())
00481 {
00482 --help;
00483 _C_i_cur_it.push_back(help);
00484 _C_i_cur = (_Node*)*help;
00485 break;
00486 }
00487 }
00488 }
00489 else
00490 {
00491 help = _C_i_cur->_C_children.end();
00492 --help;
00493 _C_i_cur_it.push_back(help);
00494 _C_i_cur = (_Node*)*help;
00495 }
00496 #endif
00497 }
00498
00500
00505 template <class _Tp, class _Ctr, class _Iterator, class _Inserter, class _Alloc>
00506 class __DG : public _DG_base<_Tp, _Ctr, _Iterator, _Alloc>
00507 {
00508 public:
00509 typedef _Ctr container_type;
00510 typedef _Iterator children_iterator;
00511 typedef _Iterator parents_iterator;
00512 typedef _Inserter container_insert_arg;
00513
00514 protected:
00515 typedef void* _Void_pointer;
00516 typedef _DG_base<_Tp, container_type, children_iterator, _Alloc> _Base;
00517 typedef _DG_node<_Tp, container_type, children_iterator> _Node;
00518 typedef __DG<_Tp,_Ctr,_Iterator,_Inserter,_Alloc> _Self;
00519 typedef std::pair<_Node*,_Node*> _RV_DG;
00520 typedef _Iterator container_iterator;
00521
00522 public:
00524
00525 typedef _Tp value_type;
00526 typedef _Node node_type;
00527 typedef value_type* pointer;
00528 typedef const value_type* const_pointer;
00529 typedef value_type& reference;
00530 typedef const value_type& const_reference;
00531 typedef size_t size_type;
00532 typedef ptrdiff_t difference_type;
00534
00535 typedef typename _Base::allocator_type allocator_type;
00537 allocator_type get_allocator() const { return _Base::get_allocator(); }
00538
00539 public:
00541 typedef _DG_iterator<_Tp,_Tp&,_Tp*,container_type,children_iterator> iterator;
00543 typedef _DG_iterator<_Tp,const _Tp&,const _Tp*,container_type,children_iterator> const_iterator;
00544
00545 #ifdef __VGTL_CLASS_PARTIAL_SPECIALIZATION
00546
00547 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
00549 typedef std::reverse_iterator<iterator> reverse_iterator;
00550 #else
00551
00552 typedef std::reverse_bidirectional_iterator<const_iterator,value_type,
00553 const_reference,difference_type>
00554 const_reverse_iterator;
00556 typedef std::reverse_bidirectional_iterator<iterator,value_type,reference,
00557 difference_type>
00558 reverse_iterator;
00559 #endif
00560
00562 typedef _DG_walker<_Tp,_Tp&,_Tp*,container_type,children_iterator> walker;
00564 typedef _DG_walker<_Tp,const _Tp&,const _Tp*,container_type,children_iterator> const_walker;
00565
00567 typedef std::pair<walker,walker> edge;
00569 typedef std::pair<edge,bool> enhanced_edge;
00570
00571 protected:
00573 typedef std::pair<_RV_DG, std::vector<enhanced_edge> > erased_part;
00574
00575 protected:
00576 #ifdef __VGTL_HAS_NAMESPACES
00577 using _Base::_C_ground;
00578 using _Base::_C_sky;
00579 using _Base::_C_mark;
00580 using _Base::_C_put_node;
00581 using _Base::_C_get_node;
00582 #endif
00583
00584 protected:
00586 _Node* _C_create_node(const _Tp& __x)
00587 {
00588 _Node* __p = _C_get_node();
00589 __p->_C_visited = 0;
00590 __VGTL_TRY {
00591 std::_Construct(&__p->_C_data, __x);
00592 std::_Construct(&__p->_C_children);
00593 std::_Construct(&__p->_C_parents);
00594 }
00595 __VGTL_UNWIND(_C_put_node(__p));
00596 return __p;
00597 }
00598
00600 _Node* _C_create_node()
00601 {
00602 _Node* __p = _C_get_node();
00603 __p->_C_visited = 0;
00604 __VGTL_TRY {
00605 std::_Construct(&__p->_C_data);
00606 std::_Construct(&__p->_C_children);
00607 std::_Construct(&__p->_C_parents);
00608 }
00609 __VGTL_UNWIND(_C_put_node(__p));
00610 return __p;
00611 }
00612
00613 public:
00615 explicit __DG(const allocator_type& __a = allocator_type()) : _Base(__a) {}
00616
00618 walker ground()
00619 { walker __help(_C_ground);
00620 return __help; }
00621
00623 walker sky()
00624 { walker __help(_C_sky);
00625 return __help; }
00626
00628 const_walker ground() const
00629 { const_walker __help(_C_ground);
00630 return __help; }
00631
00633 const_walker sky() const
00634 { const_walker __help(_C_sky);
00635 return __help; }
00636
00638 children_iterator root_begin()
00639 { return _C_ground->_C_children.begin(); }
00641 children_iterator root_end()
00642 { return _C_ground->_C_children.end(); }
00643
00645 parents_iterator leaf_begin()
00646 { return _C_sky->_C_parents.begin(); }
00648 parents_iterator leaf_end()
00649 { return _C_sky->_C_parents.end(); }
00650
00651 iterator begin() {}
00652 const_iterator begin() const {}
00653
00654 iterator end() {}
00655 const_iterator end() const {}
00656
00657 reverse_iterator rbegin()
00658 { return reverse_iterator(end()); }
00659 reverse_iterator rend()
00660 { return reverse_iterator(begin()); }
00661
00662 const_reverse_iterator rbegin() const
00663 { return const_reverse_iterator(end()); }
00664 const_reverse_iterator rend() const
00665 { return const_reverse_iterator(begin()); }
00666
00668 bool empty() const
00669 { return *((*_C_ground)._C_children.begin()) == (void*)_C_sky; }
00670
00672 size_type size() const {
00673 size_type __result = 0;
00674 distance(begin(), end(), __result);
00675 return __result;
00676 }
00677
00679 size_type max_size() const { return size_type(-1); }
00680
00682 void swap(_Self& __x)
00683 { __STD::swap(_C_ground, __x._C_ground);
00684 __STD::swap(_C_sky, __x._C_sky);
00685 __STD::swap(_C_mark, __x._C_mark); }
00686
00692 walker insert_node_in_graph(_Node* __n, const walker& __parent,
00693 const walker& __child,
00694 const container_insert_arg& __Itc,
00695 const container_insert_arg& __Itp)
00696 { __parent._C_w_cur->_C_children.insert(__Itc, (void*)__n);
00697 __child._C_w_cur->_C_parents.insert(__Itp, (void*)__n);
00698 __n->_C_children.push_back((void*)__child._C_w_cur);
00699 __n->_C_parents.push_back((void*)__parent._C_w_cur);
00700 return walker(__n);
00701 }
00702
00708 walker insert_in_graph(const _Tp& __x, const walker& __parent,
00709 const walker& __child,
00710 const container_insert_arg& __Itc,
00711 const container_insert_arg& __Itp)
00712 {
00713 _Node* __tmp = _C_create_node(__x);
00714 return insert_node_in_graph(__tmp, __parent, __child, __Itc, __Itp);
00715 }
00716
00722 walker insert_in_graph(const walker& __parent,
00723 const walker& __child,
00724 const container_insert_arg& __Itc,
00725 const container_insert_arg& __Itp)
00726 { return insert_in_graph(_Tp(), __parent, __child, __Itc, __Itp); }
00727
00733 void insert_subgraph(_Self& __subgraph,
00734 const walker& __parent,
00735 const walker& __child,
00736 const container_insert_arg& __Itc,
00737 const container_insert_arg& __Itp)
00738 {
00739 __subgraph.add_all_children(inserter(__parent._C_w_cur->_C_children,
00740 __Itc), __parent._C_w_cur);
00741 __subgraph.add_all_parents(inserter(__child._C_w_cur->_C_parents,
00742 __Itp), __child._C_w_cur);
00743 __subgraph.clear_children();
00744 __subgraph.clear_parents();
00745 }
00746
00747 #ifdef __VGTL_MEMBER_TEMPLATES
00748
00752 template <template <class __Tp, class __AllocTp> class __SequenceCtr1,
00753 template <class __Tp, class __AllocTp> class __SequenceCtr2,
00754 class _Allocator1, class _Allocator2>
00755 walker insert_node_in_graph(_Node* __node,
00756 const __SequenceCtr1<walker,_Allocator1>& __parents,
00757 const __SequenceCtr2<walker,_Allocator2>& __children)
00758 {
00759 typedef typename __SequenceCtr1<walker,_Allocator1>::const_iterator
00760 _Sequ_itp;
00761 typedef typename __SequenceCtr2<walker,_Allocator2>::const_iterator
00762 _Sequ_itc;
00763
00764 for(_Sequ_itp __b = __parents.begin(); __b != __parents.end(); ++__b)
00765 {
00766 __n->_C_parents.insert(__n->_C_parents.end(), (void*)(*__b).node());
00767 (*__b)._C_w_cur->_C_children.insert((*__b)._C_w_cur->_C_children.end(),
00768 (void*)__node);
00769 }
00770 for(_Sequ_itc __b = __children.begin(); __b != __children.end(); ++__b)
00771 {
00772 __n->_C_children.insert(__n->_C_children.end(), (void*)(*__b).node());
00773 (*__b)._C_w_cur->_C_parents.insert((*__b)._C_w_cur->_C_parents.end(),
00774 (void*)__node);
00775 }
00776 return walker(__node);
00777 }
00778
00783 template <template <class __Tp, class __AllocTp> class __SequenceCtr1,
00784 template <class __Tp, class __AllocTp> class __SequenceCtr2,
00785 class _Allocator1, class _Allocator2>
00786 walker insert_in_graph(const _Tp& __x,
00787 const __SequenceCtr1<walker,_Allocator1>& __parents,
00788 const __SequenceCtr2<walker,_Allocator2>& __children)
00789 {
00790 _Node* __tmp = _C_create_node(__x);
00791 return insert_node_in_graph(__tmp, __parents, __children);
00792 }
00793
00798 template <template <class __Tp, class __AllocTp> class __SequenceCtr1,
00799 template <class __Tp, class __AllocTp> class __SequenceCtr2,
00800 class _Allocator1, class _Allocator2>
00801 walker insert_in_graph(const __SequenceCtr1<walker,_Allocator1>& __parents,
00802 const __SequenceCtr2<walker,_Allocator2>& __children)
00803 {
00804 _Node* __tmp = _C_create_node();
00805 return insert_node_in_graph(__tmp, __parents, __children);
00806 }
00807
00812 template <template <class __Tp, class __AllocTp> class __SequenceCtr,
00813 class _Allocator>
00814 walker insert_node_in_graph(_Node* __node, const walker& __parent,
00815 const container_insert_arg& __pref,
00816 const __SequenceCtr<walker,_Allocator>& __children)
00817 {
00818 typedef typename __SequenceCtr<walker,_Allocator>::const_iterator _Sequ_it;
00819 _Sequ_it __b;
00820
00821 __node->_C_parents.insert(__node->_C_parents.end(), (void*)__parent._C_w_cur);
00822 __parent._C_w_cur->_C_children.insert(__pref, (void*)__node);
00823 for(__b = __children.begin(); __b != __children.end(); ++__b)
00824 {
00825 __node->_C_children.insert(__node->_C_children.end(),
00826 (void*)(*__b)._C_w_cur);
00827 (*__b)._C_w_cur->_C_parents.insert((*__b)._C_w_cur->_C_parents.end(),
00828 (void*)__node);
00829 }
00830 return walker(__node);
00831 }
00832
00837 template <template <class __Tp, class __AllocTp> class __SequenceCtr,
00838 class _Allocator>
00839 walker insert_in_graph(const _Tp& __x, const walker& __parent,
00840 const container_insert_arg& __pref,
00841 const __SequenceCtr<walker,_Allocator>& __children)
00842 {
00843 _Node* __tmp = _C_create_node(__x);
00844 return insert_node_in_graph(__tmp, __parent, __pref, __children);
00845 }
00846
00851 template <template <class __Tp, class __AllocTp> class __SequenceCtr,
00852 class _Allocator>
00853 walker insert_in_graph(const walker& __parent,
00854 const container_insert_arg& __pref,
00855 const __SequenceCtr<walker,_Allocator>& __children)
00856 {
00857 _Node* __tmp = _C_create_node();
00858 return insert_node_in_graph(__tmp, __parent, __pref, __children);
00859 }
00860
00865 template <template <class __Tp, class __AllocTp> class __SequenceCtr,
00866 class _Allocator>
00867 walker insert_node_in_graph(_Node* __node,
00868 const __SequenceCtr<walker,_Allocator>& __parents,
00869 const walker& __child,
00870 const container_insert_arg& __cref)
00871 {
00872 typedef typename __SequenceCtr<walker,_Allocator>::const_iterator _Sequ_it;
00873 _Sequ_it __b;
00874
00875 __n->_C_children.insert(__n->_C_children.end(), (void*)__child.node());
00876 __child._C_w_cur->_C_parents.insert(__cref, (void*)__node);
00877 for(__b = __parents.begin(); __b != __parents.end(); ++__b)
00878 {
00879 __n->_C_parents.insert(__n->_C_parents.end(), (void*)(*__b).node());
00880 (*__b)._C_w_cur->_C_children.insert((*__b)._C_w_cur->_C_children.end(),
00881 (void*)__node);
00882 }
00883 return walker(__node);
00884 }
00885
00890 template <template <class __Tp, class __AllocTp> class __SequenceCtr,
00891 class _Allocator>
00892 walker insert_in_graph(const _Tp& __x,
00893 const __SequenceCtr<walker,_Allocator>& __parents,
00894 const walker& __child,
00895 const container_insert_arg& __cref)
00896 {
00897 _Node* __tmp = _C_create_node(__x);
00898 return insert_node_in_graph(__tmp, __parents, __child, __cref);
00899 }
00900
00905 template <template <class __Tp, class __AllocTp> class __SequenceCtr,
00906 class _Allocator>
00907 walker insert_in_graph(const __SequenceCtr<walker,_Allocator>& __parents,
00908 const walker& __child,
00909 const container_insert_arg& __cref)
00910 {
00911 _Node* __tmp = _C_create_node();
00912 return insert_node_in_graph(__tmp, __parents, __child, __cref);
00913 }
00914
00918 template <template <class __Tp, class __AllocTp> class __SequenceCtr1,
00919 template <class __Tp, class __AllocTp> class __SequenceCtr2,
00920 class _Allocator1, class _Allocator2>
00921 void insert_subgraph(_Self& __subgraph,
00922 const __SequenceCtr1<walker,_Allocator1>& __parents,
00923 const __SequenceCtr2<walker,_Allocator2>& __children)
00924 {
00925 typedef typename __SequenceCtr1<walker,_Allocator1>::const_iterator
00926 _Sequ_itp;
00927 typedef typename __SequenceCtr2<walker,_Allocator2>::const_iterator
00928 _Sequ_itc;
00929 _Sequ_itp __sitp;
00930 _Sequ_itc __sitc;
00931 children_iterator __b;
00932 walker __wb;
00933 _Node* __n;
00934
00935 __sitp = __parents.begin();
00936 for(__b = __subgraph._C_ground->_C_children.begin();
00937 __b != __subgraph._C_ground->_C_children.end();
00938 ++__b)
00939 {
00940 if(__sitp == __parents.end())
00941 __wb = (*this)._C_ground;
00942 else
00943 __wb = *__sitp++;
00944 __n = __wb.node();
00945 __n->_C_children.insert(__n->_C_children.end(), *__b);
00946 ((_Node*)*__b)->_C_parents.insert(((_Node*)*__b)->_C_parents.end(),
00947 (void*)__n);
00948 }
00949 __sitc = __children.begin();
00950 for(__b = __subgraph._C_sky->_C_parents.begin();
00951 __b != __subgraph._C_sky->_C_parents.end();
00952 ++__b)
00953 {
00954 if(__sitc == __children.end())
00955 __wb = (*this)._C_sky;
00956 else
00957 __wb = *__sitc++;
00958 __n = __wb.node();
00959 __n->_C_parents.insert(__n->_C_parents.end(), *__b);
00960 ((_Node*)*__b)->_C_children.insert(((_Node*)*__b)->_C_children.end(),
00961 (void*)__n);
00962 }
00963 __subgraph.clear_children();
00964 __subgraph.clear_parents();
00965 }
00966 #endif
00967
00971 void add_edge(const edge& __edge,
00972 const container_insert_arg& __Itc,
00973 const container_insert_arg& __Itp)
00974 { add_edge(__edge.first, __edge.second, __Itc, __Itp); }
00975
00980 void add_edge(const walker& __parent, const walker& __child,
00981 const container_insert_arg& __Itc,
00982 const container_insert_arg& __Itp)
00983 {
00984 int do_remove(0);
00985 if(__parent._C_w_cur->_C_children.size() == 1)
00986 {
00987 container_iterator __it;
00988 __it = __parent._C_w_cur->_C_children.begin();
00989 if(*__it == (void*)_C_sky)
00990 do_remove += 1;
00991 }
00992 if(__child._C_w_cur->_C_parents.size() == 1)
00993 {
00994 container_iterator __it;
00995 __it = __child._C_w_cur->_C_parents.begin();
00996 if(*__it == (void*)_C_ground)
00997 do_remove += 2;
00998 }
00999 __parent._C_w_cur->_C_children.insert(__Itc, (void*)__child._C_w_cur);
01000 __child._C_w_cur->_C_parents.insert(__Itp, (void*)__parent._C_w_cur);
01001 if(do_remove & 1)
01002 {
01003 container_iterator __it;
01004 __it = __parent._C_w_cur->get_childentry_iterator((void*)_C_sky);
01005 __parent._C_w_cur->_C_children.erase(__it);
01006 __it = _C_sky->get_parententry_iterator((void*)__parent._C_w_cur);
01007 _C_sky->_C_parents.erase(__it);
01008 }
01009 if(do_remove & 2)
01010 {
01011 container_iterator __it;
01012 __it = __child._C_w_cur->get_parententry_iterator((void*)_C_ground);
01013 __child._C_w_cur->_C_parents.erase(__it);
01014 __it = _C_ground->get_childentry_iterator((void*)__child._C_w_cur);
01015 _C_ground->_C_children.erase(__it);
01016 }
01017 }
01018
01023 void replace_edge_to_child(const walker& __parent, const walker& __child_old,
01024 const walker& __child_new)
01025 { container_iterator __it;
01026 __it = __parent._C_w_cur->get_childentry_iterator((void*) __child_old._C_w_cur);
01027 if(__it == __parent._C_w_cur->_C_children.end())
01028 return;
01029 (*__it) = (void*) __child_new._C_w_cur;
01030 __it = __child_old._C_w_cur->get_parententry_iterator((void*) __parent._C_w_cur);
01031 if(__it == __child_old._C_w_cur->_C_parents.end())
01032 return;
01033 __child_old._C_w_cur->_C_parents.erase(__it);
01034 if(__child_old._C_w_cur->_C_parents.size() == 0)
01035 {
01036 __child_old._C_w_cur->_C_parents.insert(
01037 __child_old._C_w_cur->_C_parents.end(), (void*)_C_ground);
01038 _C_ground->_C_children.insert(_C_ground->_C_children.end(),
01039 (void*)__child_old._C_w_cur);
01040 }
01041 if(__child_new._C_w_cur->_C_parents.size() == 1)
01042 {
01043 if(*__child_new._C_w_cur->_C_parents.begin() == (void*)_C_ground)
01044 {
01045 __it = _C_ground->get_childentry_iterator((void*) __child_new._C_w_cur);
01046 if(__it != _C_ground->_C_children.end())
01047 _C_ground->_C_children.erase(__it);
01048 __child_new._C_w_cur->_C_parents.erase(__child_new._C_w_cur->
01049 _C_parents.begin());
01050 }
01051 }
01052 __child_new._C_w_cur->_C_parents.insert(
01053 __child_new._C_w_cur->_C_parents.end(), (void*)__parent._C_w_cur);
01054 }
01055
01060 void replace_edge_to_parent(const walker& __parent_old,
01061 const walker& __parent_new, const walker& __child)
01062 { container_iterator __it;
01063 __it = __child._C_w_cur->get_parententry_iterator((void*) __parent_old._C_w_cur);
01064 if(__it == __child._C_w_cur->_C_parents.end())
01065 return;
01066 (*__it) = (void*) __parent_new._C_w_cur;
01067 __it = __parent_old._C_w_cur->get_childentry_iterator((void*) __child._C_w_cur);
01068 if(__it == __parent_old._C_w_cur->_C_children.end())
01069 return;
01070 __parent_old._C_w_cur->_C_children.erase(__it);
01071 if(__parent_old._C_w_cur->_C_children.size() == 0)
01072 {
01073 __parent_old._C_w_cur->_C_children.insert(
01074 __parent_old._C_w_cur->_C_children.end(), (void*)_C_sky);
01075 _C_sky->_C_parents.insert(_C_sky->_C_parents.end(),
01076 (void*)__parent_old._C_w_cur);
01077 }
01078 if(__parent_new._C_w_cur->_C_children.size() == 1)
01079 {
01080 if(*__parent_new._C_w_cur->_C_children.begin() == (void*)_C_sky)
01081 {
01082 __it = _C_sky->get_parententry_iterator((void*) __parent_new._C_w_cur);
01083 if(__it != _C_sky->_C_parents.end())
01084 _C_sky->_C_parents.erase(__it);
01085 __parent_new._C_w_cur->_C_children.erase(__parent_new._C_w_cur->
01086 _C_children.begin());
01087 }
01088 }
01089 __parent_new._C_w_cur->_C_children.insert(
01090 __parent_new._C_w_cur->_C_children.end(), (void*)__child._C_w_cur);
01091 }
01092
01094 void remove_edge(const edge& __edge)
01095 { remove_edge(__edge.first, __edge.second); }
01096
01098 void remove_edge_and_deattach(const walker& __parent, const walker& __child)
01099 { container_iterator __it;
01100 __it = __parent._C_w_cur->get_childentry_iterator((void*) __child._C_w_cur);
01101 if(__it == __parent._C_w_cur->_C_children.end())
01102 return;
01103 __parent._C_w_cur->_C_children.erase(__it);
01104 __it = __child._C_w_cur->get_parententry_iterator((void*) __parent._C_w_cur);
01105 if(__it == __child._C_w_cur->_C_parents.end())
01106 return;
01107 __child._C_w_cur->_C_parents.erase(__it);
01108 }
01109
01111 void remove_edge(const walker& __parent, const walker& __child)
01112 {
01113 remove_edge_and_deattach(__parent, __child);
01114
01115
01116
01117 if(__parent._C_w_cur->_C_children.size() == 0)
01118 {
01119 __parent._C_w_cur->_C_children.insert(
01120 __parent._C_w_cur->_C_children.end(), (void*)_C_sky);
01121 _C_sky->_C_parents.insert(_C_sky->_C_parents.end(),
01122 (void*)__parent._C_w_cur);
01123 }
01124 if(__child._C_w_cur->_C_parents.size() == 0)
01125 {
01126 __child._C_w_cur->_C_parents.insert(
01127 __child._C_w_cur->_C_parents.end(), (void*)_C_ground);
01128 _C_ground->_C_children.insert(_C_ground->_C_children.end(),
01129 (void*)__child._C_w_cur);
01130 }
01131 }
01132
01134 template <class Compare>
01135 void sort_child_edges(walker __position, children_iterator first,
01136 children_iterator last, Compare comp)
01137 { (*__position._C_w_cur).sort_child_edges(first, last, comp); }
01138
01140 template <class Compare>
01141 void sort_parent_edges(walker __position, parents_iterator first,
01142 parents_iterator last, Compare comp)
01143 { (*__position._C_w_cur).sort_parent_edges(first, last, comp); }
01144
01146 template <class Compare>
01147 void sort_child_edges(walker __position, Compare comp)
01148 { (*__position._C_w_cur).sort_child_edges(__position.child_begin(),
01149 __position.child_end(), comp); }
01150
01152 template <class Compare>
01153 void sort_parent_edges(walker __position, Compare comp)
01154 { (*__position._C_w_cur).sort_parent_edges(__position.parent_begin(),
01155 __position.parent_end(), comp); }
01156
01158 walker insert_node(_Node* _node, const walker& __position,
01159 const container_insert_arg& __It)
01160 { if(__position.sky())
01161 return;
01162 __position._C_w_cur->add_all_children(
01163 inserter(_node->_C_children, __It), _node);
01164 __position._C_w_cur->clear_children();
01165 __position._C_w_cur->_C_children.insert(
01166 __position._C_w_cur->_C_children.end(), _node);
01167 _node->_C_parents.insert(_node->_C_parents.end(),__position._C_w_cur);
01168 return walker(_node);
01169 }
01170
01172 walker insert_node(const _Tp& __x, const walker& __position,
01173 const container_insert_arg& __It)
01174 { return insert_node(_C_create_node(__x), __position, __It); }
01175
01176
01178 walker insert_node(const walker& __position,
01179 const container_insert_arg& __It)
01180 { return insert_node(_Tp(), __position, __It); }
01181
01183 walker insert_node_before(_Node* _node, const walker& __position,
01184 const container_insert_arg& __It)
01185 { if(__position.ground())
01186 return;
01187 __position._C_w_cur->add_all_parents(
01188 back_inserter(_node->_C_parents), _node);
01189 __position._C_w_cur->clear_parents();
01190 __position._C_w_cur->_C_parents.insert(
01191 __position._C_w_cur->_C_parents.end(), _node);
01192 _node->_C_children.push_back(__position.C_w_cur);
01193 return walker(_node);
01194 }
01195
01197 void insert_node_before(const _Tp& __x, const walker& __position,
01198 const container_insert_arg& __It)
01199 { return insert_node_before(_C_create_node(__x), __position, __It); }
01200
01202 void insert_node_before(const walker& __position,
01203 const container_insert_arg& __It)
01204 { return insert_node_before(_Tp(), __position, __It); }
01205
01206
01208 void merge(const walker& __position, const walker& __second,
01209 bool merge_parent_edges = true, bool merge_child_edges = true)
01210 { _Node* __tp = __position._C_w_cur;
01211 _Node* __ts = __second._C_w_cur;
01212 _Node* __p;
01213
01214 if(__position.is_sky() || __position.is_ground() ||
01215 __second.is_sky() || __second.is_ground() ||
01216 __position == __second)
01217
01218 return;
01219
01220 container_iterator __i, __j;
01221 bool mrg_it;
01222 bool __is_root = __position.is_root();
01223 bool __is_leaf = __position.is_leaf();
01224
01225 for(__i = __ts->_C_children.begin();
01226 __i != __ts->_C_children.end(); ++__i)
01227 {
01228 mrg_it = 0;
01229 __p = (_Node*)*__i;
01230 if(merge_child_edges)
01231 {
01232 for(__j = __tp->_C_children.begin();
01233 __j != __tp->_C_children.end(); ++__j)
01234 {
01235 if(*__i == *__j)
01236 {
01237 mrg_it = 1;
01238 break;
01239 }
01240 }
01241 }
01242 __j = __p->get_parententry_iterator(__ts);
01243 if(__p == _C_sky || mrg_it)
01244 __p->_C_parents.erase(__j);
01245 else
01246 *__j = (void *)__tp;
01247 if(!mrg_it && __p != _C_sky)
01248 __tp->_C_children.insert(__tp->_C_children.end(), (void*)__p);
01249 }
01250 if(__is_leaf && __tp->_C_children.size() > 1)
01251 {
01252 __j = _C_sky->get_parententry_iterator(__tp);
01253 _C_sky->_C_parents.erase(__j);
01254 __j = __tp->get_childentry_iterator(_C_sky);
01255 __tp->_C_children.erase(__j);
01256 }
01257 for(__i = __ts->_C_parents.begin();
01258 __i != __ts->_C_parents.end(); ++__i)
01259 {
01260 mrg_it = 0;
01261 __p = (_Node*)*__i;
01262 if(merge_parent_edges)
01263 {
01264 for(__j = __tp->_C_parents.begin();
01265 __j != __tp->_C_parents.end(); ++__j)
01266 {
01267 if(*__i == *__j)
01268 {
01269 mrg_it = 1;
01270 break;
01271 }
01272 }
01273 }
01274 __j = __p->get_childentry_iterator(__ts);
01275 if(__p == _C_ground || mrg_it)
01276 __p->_C_children.erase(__j);
01277 else
01278 *__j = (void *)__tp;
01279 if(!mrg_it && __p != _C_ground)
01280 __tp->_C_parents.insert(__tp->_C_parents.end(), (void*)__p);
01281 }
01282 if(__is_root && __tp->_C_parents.size() > 1)
01283 {
01284 __j = _C_ground->get_childentry_iterator(__tp);
01285 _C_ground->_C_children.erase(__j);
01286 __j = __tp->get_parententry_iterator(_C_ground);
01287 __tp->_C_parents.erase(__j);
01288 }
01289
01290 (__tp->_C_data).merge(__ts->_C_data);
01291 __ts->clear_children();
01292 __ts->clear_parents();
01293 _C_put_node(__ts);
01294 }
01295
01297 void erase(const walker& __position)
01298 { _Node* __tmp = __position._C_w_cur;
01299
01300 if(!__tmp->_C_children.empty() && !__tmp->_C_parents.empty())
01301 {
01302 container_iterator __ip, __ic;
01303 _Node* __p;
01304 bool do_it;
01305
01306 do_it = !__position.is_leaf();
01307 for(__ip = __tmp->_C_parents.begin();
01308 __ip != __tmp->_C_parents.end(); ++__ip)
01309 {
01310 __p = (_Node*)*__ip;
01311 __ic = __p->get_childentry_iterator(__tmp);
01312 ++__ic;
01313 if(__position.is_root())
01314 {
01315 for(container_iterator __icc = __tmp->_C_children.begin();
01316 __icc != __tmp->_C_children.end(); ++__icc)
01317 {
01318 _Node* __c = (_Node*)*__icc;
01319 if(__c->_C_parents.size() == 1)
01320 {
01321 __c->_C_parents.insert(__c->_C_parents.end(), (void*)__p);
01322 __p->_C_children.insert(__ic, (void*)__c);
01323 ++__ic;
01324 }
01325 }
01326 }
01327 else if(do_it || __p->_C_children.size() == 1)
01328 __tmp->add_all_children(inserter(__p->_C_children, __ic), __p);
01329
01330
01331
01332
01333 __ic = __p->get_childentry_iterator(__tmp);
01334 __p->_C_children.erase(__ic);
01335 if(__p->_C_children.size() == 0)
01336 __p->_C_children.insert(__p->_C_children.end(),
01337 (void*) _C_sky);
01338 }
01339 for(__ic = __tmp->_C_children.begin();
01340 __ic != __tmp->_C_children.end(); ++__ic)
01341 {
01342 __p = (_Node*)*__ic;
01343 __ip = __p->get_parententry_iterator(__tmp);
01344 __p->_C_parents.erase(__ip);
01345 if(__p->_C_parents.size() == 0)
01346 __p->_C_parents.insert(__p->_C_parents.end(),
01347 (void*) _C_ground);
01348 }
01349 __tmp->clear_parents();
01350 __tmp->clear_children();
01351 _C_put_node(__tmp);
01352 }
01353 }
01354
01355
01356 private:
01358 void cut_excess_edges(const walker& __position, _Node* __ngrd, _Node* __nsky,
01359 bool maximal, bool upwards, std::vector<enhanced_edge>& __ev)
01360 {
01361 std::vector<walker> __v(1);
01362 __v[0] = __position;
01363 cut_excess_edges(__v, __ngrd, __nsky, maximal, upwards, __ev);
01364 }
01365
01367 bool parents_are_marked(int __mark, const walker& __pson)
01368 {
01369 parents_iterator _pit;
01370 const_walker __pr;
01371 walker __position(__pson);
01372
01373 for(_pit = __position.parent_begin(); _pit != __position.parent_end();
01374 ++_pit)
01375 {
01376 __pr = __position << _pit;
01377 if(__pr.node()->_C_visited < __mark && !__pr.is_ground())
01378 return false;
01379 }
01380 return true;
01381 }
01382
01384 bool children_are_marked(int __mark, const walker& __pson)
01385 {
01386 children_iterator _cit;
01387 const_walker __ch;
01388 walker __position(__pson);
01389
01390 for(_cit = __position.child_begin(); _cit != __position.child_end();
01391 ++_cit)
01392 {
01393 __ch = __position >> _cit;
01394 if(__ch.node()->_C_visited < __mark && !__ch.is_sky())
01395 return false;
01396 }
01397 return true;
01398 }
01399
01401 void dnrecursive_mark_node(int __mark, const walker& __pson,
01402 bool maximal)
01403 {
01404 children_iterator _cit;
01405 walker __position(__pson);
01406
01407 if(__position._C_w_cur->_C_visited == __mark ||
01408 __position.is_ground() || __position.is_sky())
01409 return;
01410 if(!maximal && !parents_are_marked(__mark, __position))
01411
01412
01413 return;
01414 __position._C_w_cur->_C_visited = __mark;
01415 for(_cit = __position.child_begin();
01416 _cit != __position.child_end(); ++_cit)
01417 dnrecursive_mark_node(__mark, __position>>_cit, maximal);
01418 }
01419
01421 void uprecursive_mark_node(int __mark, const walker& __pson,
01422 bool maximal)
01423 {
01424 walker __position(__pson);
01425 parents_iterator _pit;
01426
01427 if(__position._C_w_cur->_C_visited == __mark ||
01428 __position.is_ground() || __position.is_sky())
01429 return;
01430 if(!maximal && !children_are_marked(__mark, __position))
01431
01432
01433 return;
01434 __position._C_w_cur->_C_visited = __mark;
01435 for(_pit = __position.parent_begin();
01436 _pit != __position.parent_end(); ++_pit)
01437 dnrecursive_mark_node(__mark, __position<<_pit, maximal);
01438 }
01439
01441 void recursive_cut_edges(int __mark, const walker& __pson,
01442 _Node* __ngrd, _Node* __nsky, std::vector<enhanced_edge>& __ev)
01443
01444
01445 {
01446 children_iterator _cit;
01447 _Node* _h;
01448 walker _w;
01449 walker __position(__pson);
01450 edge _e;
01451 bool _rcf;
01452 std::list<children_iterator> _er_cit;
01453
01454 for(_cit = __position.child_begin(); _cit != __position.child_end(); ++_cit)
01455 {
01456 _h = (_Node*)(*_cit);
01457 _w = __position >> _cit;
01458 if((__position._C_w_cur->_C_visited == __mark && _h->_C_visited < __mark)
01459 ||(__position._C_w_cur->_C_visited < __mark && _h->_C_visited == __mark))
01460
01461
01462 {
01463 container_iterator __it;
01464
01465
01466 _e = make_pair(__position, _w);
01467
01468 _er_cit.push_back(_cit);
01469
01470 __it = _h->get_parententry_iterator((void*)__position._C_w_cur);
01471 if(__it != _h->_C_parents.end())
01472 _h->_C_parents.erase(__it);
01473 if(__position._C_w_cur->_C_visited == __mark)
01474
01475 {
01476
01477
01478
01479 if(_h->_C_parents.size() == 0)
01480 {
01481 _h->_C_parents.insert(_h->_C_parents.end(), (void*)_C_ground);
01482 _C_ground->_C_children.insert(_C_ground->_C_children.end(),
01483 (void*)_h);
01484 _rcf = true;
01485 }
01486 else
01487 _rcf = false;
01488 }
01489 else
01490
01491 {
01492 if(_h->_C_parents.size() == 0)
01493 {
01494 _h->_C_parents.insert(_h->_C_parents.end(), (void*)__ngrd);
01495 __ngrd->_C_children.insert(__ngrd->_C_children.end(), (void*)_h);
01496 }
01497 }
01498 __ev.push_back(make_pair(_e, _rcf));
01499 }
01500 recursive_cut_edges(__mark, _w, __ngrd, __nsky, __ev);
01501 }
01502 if(!_er_cit.empty())
01503 {
01504
01505
01506
01507
01508
01509 children_iterator _hit, _eit;
01510 typename std::list<children_iterator>::iterator _erc;
01511
01512 _erc = _er_cit.begin();;
01513 _eit = __position._C_w_cur->_C_children.end();
01514 for(_hit = _cit = __position._C_w_cur->_C_children.begin();
01515 _cit != _eit; ++_cit)
01516 {
01517 if(_cit == *_erc)
01518 ++_erc;
01519 else
01520 {
01521 if(_cit != _hit)
01522 *_hit = *_cit;
01523 ++_hit;
01524 }
01525 }
01526 __position._C_w_cur->_C_children.erase(_hit, _eit);
01527
01528 if(__position._C_w_cur->_C_visited == __mark)
01529 {
01530
01531 if(__position._C_w_cur->_C_children.size() == 0)
01532 {
01533 __position._C_w_cur->_C_children.insert(
01534 __position._C_w_cur->_C_children.end(), (void*)__nsky);
01535 __nsky->_C_parents.insert(__nsky->_C_parents.end(),
01536 (void*)__position._C_w_cur);
01537 }
01538 }
01539 else
01540 {
01541
01542
01543
01544 if(__position._C_w_cur->_C_children.size() == 0)
01545 {
01546 __position._C_w_cur->_C_children.insert(
01547 __position._C_w_cur->_C_children.end(), (void*)_C_sky);
01548 _C_sky->_C_parents.insert(_C_sky->_C_parents.end(),
01549 (void*)__position._C_w_cur);
01550 }
01551 }
01552 }
01553 }
01554
01555 #ifdef __VGTL_MEMBER_TEMPLATES
01556
01557 template <template <class __Tp, class __AllocTp> class __SequenceCtr,
01558 class _Allocator>
01559 void cut_excess_edges(const __SequenceCtr<walker,_Allocator>& __positions,
01560 _Node* __ngrd, _Node* __nsky, bool maximal,
01561 bool upwards, std::vector<enhanced_edge>& __ev)
01562 {
01563 int _actmark = _C_mark++;
01564 typename __SequenceCtr<walker,_Allocator>::const_iterator _pit;
01565 walker _w;
01566
01567 for(_pit = __positions.begin(); _pit != __positions.end(); ++_pit)
01568 {
01569 _w = *_pit;
01570 if(upwards)
01571 uprecursive_mark_node(_actmark, _w, maximal);
01572 else
01573 dnrecursive_mark_node(_actmark, _w, maximal);
01574 }
01575 recursive_cut_edges(_actmark, ground(), __ngrd, __nsky, __ev);
01576 }
01577 #endif
01578
01579
01580 public:
01582 void clear_erased_part(erased_part& _ep)
01583 {
01584 clear_graph(_ep.first.first);
01585 }
01586
01593 erased_part erase_maximal_subgraph(const walker& __position)
01594 { _RV_DG __rv(_C_create_node(),_C_create_node());
01595 std::vector<enhanced_edge> __ev;
01596
01597 cut_excess_edges(__position, __rv.first, __rv.second, true, false,
01598 __ev);
01599 return make_pair(__rv,__ev);
01600 }
01601
01609 erased_part erase_minimal_subgraph(const walker& __position)
01610 { _RV_DG __rv(_C_create_node(),_C_create_node());
01611 std::vector<enhanced_edge> __ev;
01612
01613 cut_excess_edges(__position, __rv.first, __rv.second, false, false,
01614 __ev);
01615 return make_pair(__rv,__ev);
01616 }
01617
01618 #ifdef __VGTL_MEMBER_TEMPLATES
01619
01625 template <template <class __Tp, class __AllocTp> class __SequenceCtr,
01626 class _Allocator>
01627 erased_part erase_maximal_subgraph(
01628 const __SequenceCtr<walker,_Allocator>& __positions)
01629 { _RV_DG __rv(_C_create_node(),_C_create_node());
01630 std::vector<enhanced_edge> __ev;
01631
01632 cut_excess_edges(__positions, __rv.first, __rv.second, true, false,
01633 __ev);
01634 return make_pair(__rv,__ev);
01635 }
01636
01645 template <template <class __Tp, class __AllocTp> class __SequenceCtr,
01646 class _Allocator>
01647 erased_part erase_minimal_subgraph(
01648 const __SequenceCtr<walker,_Allocator>& __positions)
01649 { _RV_DG __rv(_C_create_node(),_C_create_node());
01650 std::vector<enhanced_edge> __ev;
01651
01652 cut_excess_edges(__positions, __rv.first, __rv.second, false, false,
01653 __ev);
01654 return make_pair(__rv,__ev);
01655 }
01656 #endif
01657
01664 erased_part erase_maximal_pregraph(const walker& __position)
01665 { _RV_DG __rv(_C_create_node(),_C_create_node());
01666 std::vector<enhanced_edge> __ev;
01667
01668 cut_excess_edges(__position, __rv.first, __rv.second, true, true,
01669 __ev);
01670 return make_pair(__rv,__ev);
01671 }
01672
01680 erased_part erase_minimal_pregraph(const walker& __position)
01681 { _RV_DG __rv(_C_create_node(),_C_create_node());
01682 std::vector<enhanced_edge> __ev;
01683
01684 cut_excess_edges(__position, __rv.first, __rv.second, false, true,
01685 __ev);
01686 return make_pair(__rv,__ev);
01687 }
01688
01689 #ifdef __VGTL_MEMBER_TEMPLATES
01690
01696 template <template <class __Tp, class __AllocTp> class __SequenceCtr,
01697 class _Allocator>
01698 erased_part erase_maximal_pregraph(
01699 const __SequenceCtr<walker,_Allocator>& __positions)
01700 { _RV_DG __rv(_C_create_node(),_C_create_node());
01701 std::vector<enhanced_edge> __ev;
01702
01703 cut_excess_edges(__positions, __rv.first, __rv.second, true, true,
01704 __ev);
01705 return make_pair(__rv,__ev);
01706 }
01707
01716 template <template <class __Tp, class __AllocTp> class __SequenceCtr,
01717 class _Allocator>
01718 erased_part erase_minimal_pregraph(
01719 const __SequenceCtr<walker,_Allocator>& __positions)
01720 { _RV_DG __rv(_C_create_node(),_C_create_node());
01721 std::vector<enhanced_edge> __ev;
01722
01723 cut_excess_edges(__positions, __rv.first, __rv.second, false, true,
01724 __ev);
01725 return make_pair(__rv,__ev);
01726 }
01727 #endif
01728
01734 bool erase_child(const walker& __position,
01735 const children_iterator& __It)
01736 {
01737 _Node* __chld = (_Node*)*__It;
01738
01739 if(__chld->_C_children.size() != 1 || __chld->_C_parents.size() != 1)
01740 { return false; }
01741 else
01742 {
01743 _Node* __c2;
01744 parents_iterator __pit;
01745
01746 __c2 = (_Node*)*__chld->_C_children.begin();
01747 __pit = __c2->get_parententry_iterator((void*)__chld);
01748 *__pit = (void*)__position->_C_w_cur;
01749 *__It = (void*)__c2;
01750 _C_put_node(__chld);
01751 return true;
01752 }
01753 }
01754
01760 bool erase_parent(const walker& __position,
01761 const parents_iterator& __It)
01762 {
01763 _Node* __prnt = (_Node*)*__It;
01764
01765 if(__prnt->_C_children.size() != 1 || __prnt->_C_parents.size() != 1)
01766 { return false; }
01767 else
01768 {
01769 _Node* __p2;
01770 children_iterator __cit;
01771
01772 __p2 = (_Node*)*__prnt->_C_parents.begin();
01773 __cit = __c2->get_childentry_iterator((void*)__prnt);
01774 *__cit = (void*)__position->_C_w_cur;
01775 *__It = (void*)__p2;
01776 _C_put_node(__prnt);
01777 return true;
01778 }
01779 }
01780
01782 void clear() { _Base::clear(); }
01783
01784 private:
01789 _Node* copy_subgraph(_Node* __x, _Node* __par, std::map<_Node*,_Node*>& __nconn)
01790 { children_iterator cit;
01791 typedef typename std::map<_Node*,_Node*>::iterator map_it;
01792 std::pair<map_it,bool> _rv;
01793 _Node* __h = _C_create_node();
01794 _Node* __cs;
01795 map_it __cdit;
01796
01797 std::_Construct(&__h->_C_data, __x->_C_data);
01798 __h->_C_parents.insert(__h->_C_parents.end(), (void*)__par);
01799 __h->_C_visited = 0;
01800 if(__x->_C_parents.size() > 1)
01801 _rv = __nconn.insert(make_pair(__x,__h));
01802 for(cit = __x->_C_children.begin(); cit != __x->_C_children.end(); ++cit)
01803 {
01804 __cs = (_Node*)*cit;
01805 __cdit = __nconn.find(__cs);
01806 if(__cdit == __nconn.end())
01807 __h->_C_children.insert(__h->_C_children.end(),
01808 copy_subgraph(__cs, __h, __nconn));
01809 else
01810 {
01811 (*__cdit).second->_C_parents.insert(
01812 (*__cdit).second->_C_parents.end(), __h);
01813 __h->_C_children.insert(__h->_C_children.end(),
01814 (void*)(*__cdit).second);
01815 }
01816 }
01817 return __h;
01818 }
01819
01820 public:
01822 __DG(const _Self& __x) : _Base(__x.get_allocator())
01823 { children_iterator cit;
01824 std::map<_Node*,_Node*> __nconn;
01825 __nconn.insert(make_pair(__x._C_sky, this->_C_sky));
01826 this->_C_mark = 0;
01827 this->_C_ground->clear_children();
01828 this->_C_sky->clear_parents();
01829 for(cit = __x._C_ground->_C_children.begin();
01830 cit != __x._C_ground->_C_children.end(); ++cit)
01831 {
01832 if((_Node*)*cit != __x._C_sky)
01833 this->_C_ground->_C_children.insert(this->_C_ground->_C_children.end(),
01834 copy_subgraph((_Node*)*cit, this->_C_ground, __nconn));
01835 }
01836 }
01837
01839 ~__DG() {}
01840
01842 _Self& operator=(const _Self& __x);
01843
01845 _Self& operator=(const _RV_DG& __rl)
01846 {
01847 this->_C_ground = __rl.first;
01848 this->_C_sky = __rl.second;
01849 return *this;
01850 }
01851
01853 _Self& operator=(const erased_part& __ep)
01854 {
01855 this->_C_ground = __ep.first.first;
01856 this->_C_sky = __ep.first.second;
01857 return *this;
01858 }
01859
01861 friend bool operator== __VGTL_NULL_TMPL_ARGS (
01862 const __DG& __x, const __DG& __y);
01863 };
01864
01865
01866 template <class _Tp, class _Ctr, class _Iterator, class _Inserter, class _Alloc>
01867 inline bool operator==(const __DG<_Tp,_Ctr,_Iterator,_Inserter,_Alloc>& __x,
01868 const __DG<_Tp,_Ctr,_Iterator,_Inserter,_Alloc>& __y)
01869 {
01870 typedef typename __DG<_Tp,_Ctr,_Iterator,_Inserter,_Alloc>::const_walker const_walker;
01871 const_walker __w1 = __x.begin(cw_pre);
01872 const_walker __w2 = __y.begin(cw_pre);
01873 const_walker __e1 = __x.end(cw_pre);
01874 const_walker __e2 = __y.end(cw_pre);
01875
01876
01877 for(; __w1 != __e1 && __w2 != __e2 ; ++__w1, ++__w2)
01878 if(__w1.in_preorder() != __w2.in_preorder() ||
01879 (__w1.in_preorder() && *__w1 != *__w2))
01880 return false;
01881 return __w1 == __e1 && __w2 == __e2;
01882 }
01883
01884 template <class _Tp, class _Ctr, class _Iterator, class _Inserter, class _Alloc>
01885 __DG<_Tp, _Ctr, _Iterator, _Inserter, _Alloc>&
01886 __DG<_Tp, _Ctr, _Iterator, _Inserter, _Alloc>::operator=(const __DG<_Tp, _Ctr, _Iterator, _Inserter, _Alloc>& __x)
01887 {
01888 if (this != &__x)
01889 {
01890 children_iterator cit;
01891 std::map<_Node*,_Node*> __nconn;
01892
01893 clear();
01894 __nconn.insert(make_pair(__x._C_sky, this->_C_sky));
01895 this->_C_mark = 0;
01896 for(cit = __x._C_ground->_C_children.begin();
01897 cit != __x._C_ground->_C_children.end(); ++cit)
01898 {
01899 if((_Node*)*cit != __x._C_sky)
01900 this->_C_ground->_C_children.insert(this->_C_ground->_C_children.end(),
01901 copy_subgraph((_Node*)*cit, this->_C_ground, __nconn));
01902 }
01903 }
01904 return *this;
01905 }
01906
01908
01914 template <class _Tp,
01915 template <class __Ty, class __AllocT> class _SequenceCtr = std::vector,
01916 class _PtrAlloc = __VGTL_DEFAULT_ALLOCATOR(void *),
01917 class _Alloc = __VGTL_DEFAULT_ALLOCATOR(_Tp) >
01918 class dgraph : public __DG<_Tp, _SequenceCtr<void*, _PtrAlloc>,
01919 typename _SequenceCtr<void*, _PtrAlloc>::iterator,
01920 typename _SequenceCtr<void*, _PtrAlloc>::iterator,
01921 _Alloc>
01922 {
01923 private:
01924 typedef typename _SequenceCtr<void*, _PtrAlloc>::iterator ___cit;
01925 typedef __DG<_Tp,_SequenceCtr<void*, _PtrAlloc>,
01926 typename _SequenceCtr<void*, _PtrAlloc>::iterator,
01927 typename _SequenceCtr<void*, _PtrAlloc>::iterator,
01928 _Alloc> _Base;
01929 protected:
01930 typedef dgraph<_Tp,_SequenceCtr,_PtrAlloc,_Alloc> _Self;
01931 typedef typename _Base::allocator_type allocator_type;
01932 typedef typename _Base::_RV_DG _RV_DG;
01933 typedef typename _Base::_Node _Node;
01934
01935 typedef typename _Base::container_iterator container_iterator;
01936
01937 typedef typename _Base::erased_part erased_part;
01938
01939 public:
01941 typedef typename _Base::walker walker;
01943 typedef typename _Base::const_walker const_walker;
01945 typedef typename _Base::children_iterator children_iterator;
01947 typedef typename _Base::parents_iterator parents_iterator;
01948
01949 public:
01951 explicit dgraph(const allocator_type& __a = allocator_type()) : _Base(__a) {}
01952
01954 dgraph(const _Self& __dg) : _Base(__dg) {}
01955
01957 dgraph(const erased_part& __ep, const allocator_type& __a = allocator_type())
01958 : _Base(__a)
01959 {
01960 _C_ground = __ep.first.first;
01961 _C_sky = __ep.first.second;
01962 }
01963
01964
01965
01967 void clear() { _Base::clear(); }
01968
01974 walker between(const walker& __parent, const children_iterator& __cit,
01975 const walker& __child, const parents_iterator& __pit,
01976 const _Tp& __x)
01977 {
01978 return insert_in_graph(__x, __parent, __child, __cit, __pit);
01979 }
01980
01981
01987 walker split(const walker& __parent, const children_iterator& __ch_it,
01988 const walker& __child, const parents_iterator& __pa_it,
01989 const _Tp& __x)
01990 {
01991 container_iterator __cit;
01992
01993 walker __rv = between(__parent, __ch_it, __child, __pa_it, __x);
01994
01995 __cit = __parent._C_w_cur->get_childentry_iterator((void*)__child._C_w_cur);
01996 if(__cit != __parent._C_w_cur->_C_children.end())
01997 __parent._C_w_cur->_C_children.erase(__cit);
01998 __cit = __child._C_w_cur->get_parententry_iterator((void*)__parent._C_w_cur);
01999 if(__cit != __child._C_w_cur->_C_parents.end())
02000 __child._C_w_cur->_C_parents.erase(__cit);
02001 return __rv;
02002 }
02003
02004
02009 walker between_back(const walker& __parent, const walker& __child,
02010 const _Tp& __x)
02011 {
02012 return insert_in_graph(__x, __parent, __child,
02013 __parent._C_w_cur->_C_children.end(),
02014 __child._C_w_cur->_C_parents.end());
02015 }
02016
02017
02022 walker split_back(const walker& __parent,
02023 const walker& __child, const _Tp& __x)
02024 {
02025 container_iterator __cit;
02026
02027 __cit = __parent._C_w_cur->get_childentry_iterator((void*)__child._C_w_cur);
02028 if(__cit != __parent._C_w_cur->_C_children.end())
02029 __parent._C_w_cur->_C_children.erase(__cit);
02030 __cit = __child._C_w_cur->get_parententry_iterator((void*)__parent._C_w_cur);
02031 if(__cit != __child._C_w_cur->_C_parents.end())
02032 __child._C_w_cur->_C_parents.erase(__cit);
02033 return between_back(__parent, __child, __x);
02034 }
02035
02040 walker between_front(const walker& __parent, const walker& __child,
02041 const _Tp& __x)
02042 {
02043 return insert_in_graph(__x, __parent, __child,
02044 __parent._C_w_cur->_C_children.begin(),
02045 __child._C_w_cur->_C_parents.begin());
02046 }
02047
02048
02053 walker split_front(const walker& __parent,
02054 const walker& __child, const _Tp& __x)
02055 {
02056 container_iterator __cit;
02057
02058 __cit = __parent._C_w_cur->get_childentry_iterator((void*)__child._C_w_cur);
02059 if(__cit != __parent._C_w_cur->_C_children.end())
02060 __parent._C_w_cur->_C_children.erase(__cit);
02061 __cit = __child._C_w_cur->get_parententry_iterator((void*)__parent._C_w_cur);
02062 if(__cit != __child._C_w_cur->_C_parents.end())
02063 __child._C_w_cur->_C_parents.erase(__cit);
02064 return between_front(__parent, __child, __x);
02065 }
02066
02067
02072 #ifdef __VGTL_MEMBER_TEMPLATES
02073 template <template <class __Tp, class __AllocTp> class __SequenceCtr1,
02074 template <class __Tp, class __AllocTp> class __SequenceCtr2,
02075 class _Allocator1, class _Allocator2>
02076 walker between(const __SequenceCtr1<walker,_Allocator1>& __parents,
02077 const __SequenceCtr2<walker,_Allocator2>& __children,
02078 const _Tp& __x)
02079 {
02080 typename __SequenceCtr1<walker,_Allocator1>::iterator __wpit;
02081 typename __SequenceCtr2<walker,_Allocator2>::iterator __wcit;
02082 _Node* __tmp = _C_create_node(__x);
02083 walker __help(__tmp);
02084
02085 if(__parents.size() == 0 || __children.size() == 0)
02086 return;
02087 __wpit = __parents.begin();
02088 __wcit = __children.begin();
02089 insert_node_in_graph(__tmp, *__wpit, *__wcit,
02090 (*__wpit)._C_w_cur->_C_children.end(),
02091 (*__wcit)._C_w_cur->_C_parents.end());
02092 for(++__wpit; __wpit != __parents.end(); ++__wpit)
02093 add_edge(*__wpit, __help, (*__wpit)._C_w_cur->_C_children.end(),
02094 __tmp->_C_parents.end());
02095 for(++__wcit; __wcit != __children.end(); ++__wcit)
02096 add_edge(__help, *__wcit, __tmp->_C_children.end(),
02097 (*__wcit)._C_w_cur->_C_parents.end());
02098 return __help;
02099 }
02100
02105 template <template <class __Tp, class __AllocTp> class __SequenceCtr1,
02106 template <class __Tp, class __AllocTp> class __SequenceCtr2,
02107 class _Allocator1, class _Allocator2>
02108 void split(const __SequenceCtr1<walker,_Allocator1>& __parents,
02109 const __SequenceCtr2<walker,_Allocator2>& __children,
02110 const _Tp& __x)
02111 {
02112 container_iterator __cit;
02113 typename __SequenceCtr1<walker,_Allocator1>::const_iterator __pnt;
02114 typename __SequenceCtr2<walker,_Allocator2>::const_iterator __cld;
02115
02116 for(__cld = __children.begin(); __cld != __children.end(); ++__cld)
02117 for(__pnt = __parents.begin(); __pnt != __parents.end(); ++__pnt)
02118 {
02119 __cit = (*__pnt)._C_w_cur->get_childentry_iterator((void*)(*__cld)._C_w_cur);
02120 if(__cit != (*__pnt)._C_w_cur->_C_children.end())
02121 (*__pnt)._C_w_cur->_C_children.erase(__cit);
02122 __cit = (*__cld)._C_w_cur->get_parententry_iterator((void*)(*__pnt)._C_w_cur);
02123 if(__cit != (*__cld)._C_w_cur->_C_parents.end())
02124 (*__cld)._C_w_cur->_C_parents.erase(__cit);
02125 }
02126 between(__parents, __children, __x);
02127 }
02128 #endif
02129
02134 void insert_subgraph(_Self& __subgraph, const walker& __parent,
02135 const children_iterator& __ch_it, const walker& __child,
02136 const parents_iterator& __pa_it)
02137 {
02138 insert_subgraph(__subgraph, __parent, __child, __ch_it, __pa_it);
02139 }
02140
02145 void insert_back_subgraph(_Self& __subgraph, const walker& __parent,
02146 const walker& __child)
02147 {
02148 insert_subgraph(__subgraph, __parent, __child,
02149 __parent._C_w_cur->_C_children.end(),
02150 __child._C_w_cur->_C_parents.end());
02151 }
02152
02153
02158 void insert_front_subgraph(_Self& __subgraph, const walker& __parent,
02159 const walker& __child)
02160 {
02161 insert_subgraph(__subgraph, __parent, __child,
02162 __parent._C_w_cur->_C_children.begin(),
02163 __child._C_w_cur->_C_parents.begin());
02164 }
02165
02166
02167 #ifdef __VGTL_MEMBER_TEMPLATES
02168
02169 #if 0
02170 template <template <class __Tp, class __AllocTp> class __SequenceCtr1,
02171 template <class __Tp, class __AllocTp> class __SequenceCtr2,
02172 class _Allocator1, class _Allocator2>
02173 void insert_subgraph(_Self& __subgraph,
02174 const __SequenceCtr1<walker,_Allocator1>& __parents,
02175 const __SequenceCtr2<walker,_Allocator2>& __children)
02176 {
02177 insert_subgraph(__subgraph, __parents, __children);
02178 }
02179 #endif // 0
02180 #endif
02181
02186 void add_edge(const walker& __parent, const children_iterator& __ch_it,
02187 const walker& __child, const parents_iterator& __pa_it)
02188 {
02189 _Base::add_edge(__parent, __child, __ch_it, __pa_it);
02190 }
02191
02196 void add_edge_back(const walker& __parent, const walker& __child)
02197 {
02198 add_edge(__parent, __parent._C_w_cur->_C_children.end(), __child,
02199 __child._C_w_cur->_C_parents.end());
02200 }
02201
02206 void add_edge_front(const walker& __parent, const walker& __child)
02207 {
02208 add_edge(__parent, __parent._C_w_cur->_C_children.begin(), __child,
02209 __child._C_w_cur->_C_parents.begin());
02210 }
02211
02212
02213
02214 #ifdef __VGTL_MEMBER_TEMPLATES
02215
02216
02220 template <template <class __Tp, class __AllocTp> class __SequenceCtr,
02221 class _Allocator>
02222 walker between(const walker& __parent, const children_iterator& __cit,
02223 const __SequenceCtr<walker,_Allocator>& __children,
02224 const _Tp& __x)
02225 {
02226 return insert_in_graph(__x, __parent, __cit, __children);
02227 }
02228
02233 template <template <class __Tp, class __AllocTp> class __SequenceCtr,
02234 class _Allocator>
02235 walker split(const walker& __parent, const children_iterator& __ch_it,
02236 const __SequenceCtr<walker,_Allocator>& __children,
02237 const _Tp& __x)
02238 {
02239 container_iterator __cit;
02240 typename __SequenceCtr<walker,_Allocator>::const_iterator __cld;
02241 walker __rv = between(__parent, __ch_it, __children, __x);
02242
02243 for(__cld = __children.begin(); __cld != __children.end(); ++__cld)
02244 {
02245 __cit = __parent._C_w_cur->get_childentry_iterator((void*)(*__cld)._C_w_cur);
02246 if(__cit != __parent._C_w_cur->_C_children.end())
02247 __parent._C_w_cur->_C_children.erase(__cit);
02248 __cit = (*__cld)._C_w_cur->get_parententry_iterator((void*)__parent._C_w_cur);
02249 if(__cit != (*__cld)._C_w_cur->_C_parents.end())
02250 (*__cld)._C_w_cur->_C_parents.erase(__cit);
02251 }
02252 return __rv;
02253 }
02254
02260 template <template <class __Tp, class __AllocTp> class __SequenceCtr,
02261 class _Allocator>
02262 walker split_back(const walker& __parent,
02263 const __SequenceCtr<walker, _Allocator>& __children,
02264 const _Tp& __x)
02265 {
02266 return split(__parent, __parent._C_w_cur->_C_children.end(), __children,
02267 __x);
02268 }
02269
02275 template <template <class __Tp, class __AllocTp> class __SequenceCtr,
02276 class _Allocator>
02277 walker between_back(const walker& __parent,
02278 const __SequenceCtr<walker,_Allocator>& __children,
02279 const _Tp& __x)
02280 {
02281 return between(__parent, __parent._C_w_cur->_C_children.end(),
02282 __children, __x);
02283 }
02284
02290 template <template <class __Tp, class __AllocTp> class __SequenceCtr,
02291 class _Allocator>
02292 walker split_front(const walker& __parent,
02293 const __SequenceCtr<walker,_Allocator>& __children,
02294 const _Tp& __x)
02295 {
02296 return split(__parent, __parent._C_w_cur->_C_children.begin(), __children,
02297 __x);
02298 }
02299
02305 template <template <class __Tp, class __AllocTp> class __SequenceCtr,
02306 class _Allocator>
02307 walker between_front(const walker& __parent,
02308 const __SequenceCtr<walker,_Allocator>& __children,
02309 const _Tp& __x)
02310 {
02311 return between(__parent, __parent._C_w_cur->_C_children.begin(),
02312 __children, __x);
02313 }
02314
02316
02320 template <template <class __Tp, class __AllocTp> class __SequenceCtr,
02321 class _Allocator>
02322 walker between(const __SequenceCtr<walker,_Allocator>& __parents,
02323 const walker& __child, const parents_iterator& __pit,
02324 const _Tp& __x)
02325 {
02326 return insert_in_graph(__x, __parents, __child, __pit);
02327 }
02328
02333 template <template <class __Tp, class __AllocTp> class __SequenceCtr,
02334 class _Allocator>
02335 walker split(const __SequenceCtr<walker,_Allocator>& __parents,
02336 const walker& __child, const parents_iterator& __pr_it,
02337 const _Tp& __x)
02338 {
02339 container_iterator __cit;
02340 typename __SequenceCtr<walker,_Allocator>::iterator __pnt;
02341 walker __rv = between(__parents, __child, __pr_it, __x);
02342
02343 for(__pnt = __parents.begin(); __pnt != __parents.end(); ++__pnt)
02344 {
02345 __cit = __child._C_w_cur->get_parententry_iterator((void*)(*__pnt));
02346 if(__cit != __child._C_w_cur->_C_parents.end())
02347 __child._C_w_cur->_C_parents.erase(__cit);
02348 __cit = (*__pnt)._C_w_cur->get_childentry_iterator((void*)__child);
02349 if(__cit != (*__pnt)._C_w_cur->_C_children.end())
02350 (*__pnt)._C_w_cur->_C_children.erase(__cit);
02351 }
02352 return __rv;
02353 }
02354
02360 template <template <class __Tp, class __AllocTp> class __SequenceCtr,
02361 class _Allocator>
02362 walker split_back(const __SequenceCtr<walker,_Allocator>& __parents, const walker& __child,
02363 const _Tp& __x)
02364 {
02365 return split(__parents, __children, __child._C_w_cur->_C_parents.end(),
02366 __x);
02367 }
02368
02374 template <template <class __Tp, class __AllocTp> class __SequenceCtr,
02375 class _Allocator>
02376 walker between_back(const __SequenceCtr<walker,_Allocator>& __parents,
02377 const walker& __child, const _Tp& __x)
02378 {
02379 return between(__parents, __child,
02380 __child._C_w_cur->_C_children.end(), __x);
02381 }
02382
02388 template <template <class __Tp, class __AllocTp> class __SequenceCtr,
02389 class _Allocator>
02390 walker split_front(const __SequenceCtr<walker,_Allocator>& __parents,
02391 const walker& __child, const _Tp& __x)
02392 {
02393 return split(__parents, __children, __child._C_w_cur->_C_parents.begin(),
02394 __x);
02395 }
02396
02402 template <template <class __Tp, class __AllocTp> class __SequenceCtr,
02403 class _Allocator>
02404 walker between_front(const __SequenceCtr<walker,_Allocator>& __parents,
02405 const walker& __child, const _Tp& __x)
02406 {
02407 return between(__parents, __child,
02408 __child._C_w_cur->_C_children.begin(), __x);
02409 }
02410 #endif
02411
02413 _Self& operator=(const _RV_DG& __rl)
02414 {
02415 this->_C_ground = __rl.first;
02416 this->_C_sky = __rl.second;
02417 return *this;
02418 }
02419
02421 _Self& operator=(const erased_part& __ep)
02422 {
02423 this->_C_ground = __ep.first.first;
02424 this->_C_sky = __ep.first.second;
02425 return *this;
02426 }
02427 };
02428
02430
02431
02432
02433
02434
02435
02436
02438
02444 template <class _Tp,
02445 template <class __Ty, class __AllocT> class _SequenceCtr = std::vector,
02446 class _PtrAlloc = __VGTL_DEFAULT_ALLOCATOR(void *),
02447 class _Alloc = __VGTL_DEFAULT_ALLOCATOR(_Tp) >
02448 class dag : public dgraph<_Tp, _SequenceCtr, _PtrAlloc, _Alloc>
02449 {
02450 protected:
02451 typedef dag<_Tp,_SequenceCtr,_PtrAlloc,_Alloc> _Self;
02452 typedef dgraph<_Tp, _SequenceCtr, _PtrAlloc, _Alloc> _Base;
02453
02454 typedef typename _Base::allocator_type allocator_type;
02455 typedef typename _Base::_RV_DG _RV_DG;
02456 typedef typename _Base::_Node _Node;
02457
02458 typedef typename _Base::container_iterator container_iterator;
02459
02460 public:
02462 typedef typename _Base::walker walker;
02464 typedef typename _Base::const_walker const_walker;
02466 typedef typename _Base::children_iterator children_iterator;
02468 typedef typename _Base::parents_iterator parents_iterator;
02469
02471 typedef typename _Base::erased_part erased_part;
02472
02473 public:
02475 explicit dag(const allocator_type& __a = allocator_type()) : _Base(__a) {}
02476
02478 dag(const _Self& __dag) : _Base(__dag) {}
02479
02480
02481
02482
02484 dag(const _Base& __dag) : _Base(__dag)
02485 {
02486 if(!check_acyclicity(ground(), sky()))
02487
02488 clear();
02489 }
02490
02492 dag(const erased_part& __ep) : _Base(__ep)
02493 {
02494 if(!check_acyclicity(ground(), sky()))
02495
02496 clear();
02497 }
02498 #if 0
02499 void add_edge(const walker& __parent, const walker& __child)
02500 {
02501 }
02502
02503
02504 #endif
02505
02506 private:
02507
02508 bool check_edge(const walker& __parent, const walker& __child)
02509 {
02510
02511 }
02512
02513 public:
02515 bool check_acyclicity(const walker& __parent, const walker& __child)
02516 {
02517 return true;
02518 }
02519
02520 #if 0
02521 #ifdef __VGTL_MEMBER_TEMPLATES
02522 template <template <class __Tp, class __AllocTp> class __SequenceCtr,
02523 class _Allocator>
02524 void check_edges(const _SequenceCtr<std::pair<walker,walker>,_Allocator >& __edges)
02525 {
02526 }
02527 #endif
02528 #endif
02529
02531 _Self& operator=(const _RV_DG& __rl)
02532 {
02533 this->_C_ground = __rl.first;
02534 this->_C_sky = __rl.second;
02535 return *this;
02536 }
02537
02539 _Self& operator=(const erased_part& __ep)
02540 {
02541 this->_C_ground = __ep.first.first;
02542 this->_C_sky = __ep.first.second;
02543 return *this;
02544 }
02545 };
02546
02547
02549
02550 #if 0
02551
02552
02553 template <class _Tp,
02554 template <class __Key, class __Ty, class __Compare, class __AllocT> class _AssocCtr = std::multimap,
02555 class _Key = std::string,
02556 class _Compare = less<_Key>,
02557 class _PtrAlloc = __VGTL_DEFAULT_ALLOCATOR(void *),
02558 class _Alloc = __VGTL_DEFAULT_ALLOCATOR(_Tp) >
02559 class ldgraph : public __DG<_Tp, _AssocCtr<_Key, void*, _Compare, _PtrAlloc>,
02560 pair_adaptor<typename _AssocCtr<_Key, void*,
02561 _Compare, _PtrAlloc>::iterator>,
02562 _Key, _Alloc>
02563 {
02564 protected:
02565 typedef ldgraph<_Tp,_AssocCtr,_Key,_Compare,_PtrAlloc,_Alloc> _Self;
02566
02567 public:
02568 _Self& operator=(_Node* __x)
02569 {
02570 this->_C_node = __x;
02571 return *this;
02572 }
02573
02574
02575 };
02576
02577 template <class _Tp,
02578 template <class __Key, class __Ty, class __Compare, class __AllocT> class _AssocCtr = std::multimap,
02579 class _Key = std::string,
02580 class _Compare = less<_Key>,
02581 class _PtrAlloc = __VGTL_DEFAULT_ALLOCATOR(void *),
02582 class _Alloc = __VGTL_DEFAULT_ALLOCATOR(_Tp) >
02583 class ldag : public ldgraph<_Tp, _AssocCtr, _Key, _Compare, _PtrAlloc, _Alloc>
02584 {
02585 protected:
02586 typedef ldag<_Tp,_AssocCtr,_Key,_Compare,_PtrAlloc,_Alloc> _Self;
02587 typedef ldgraph<_Tp,_AssocCtr,_Key,_Compare,_PtrAlloc,_Alloc> _Base;
02588
02589 public:
02590 explicit ldag(const allocator_type& __a = allocator_type()) : _Base(__a) {}
02591
02592 explicit ldag() : _Base(allocator_type()) {}
02593
02594 ldag(const _Self& __dag) : _Base(__dag) {}
02595
02596
02597
02598
02599 #if 0
02600 void add_edge(const walker& __parent, const walker& __child)
02601 {
02602 }
02603
02604
02605
02606 private:
02607 void check_edge(const walker& __parent, const walker& __child)
02608 {
02609 }
02610
02611 #ifdef __VGTL_MEMBER_TEMPLATES
02612 template <template <class __Tp, class __AllocTp> class __SequenceCtr,
02613 class _Allocator>
02614 void check_edges(const _SequenceCtr<std::pair<walker,walker>,_Allocator >& __edges)
02615 {
02616 }
02617 #endif
02618 #endif
02619
02620 _Self& operator=(const _RV_DG& __rl)
02621 {
02622 this->_C_ground = __rl.first;
02623 this->_C_sky = __rl.second;
02624 return *this;
02625 }
02626 };
02627 #endif
02628
02629
02630
02631
02632
02633
02634
02635
02636
02637
02638
02639
02640
02641
02642
02643
02644
02645
02646
02647
02648
02649
02650
02651
02652
02653
02654
02655
02656
02657
02658
02659
02660
02661
02662
02663
02664
02665
02666
02667
02668
02669
02670
02671
02672
02673
02674
02675
02676
02677
02678
02679
02680
02681
02682
02683
02684
02685
02686
02687
02688
02689
02690
02691
02692
02693
02694
02695
02696
02697
02698
02699
02700
02701
02702
02703
02704
02705
02706
02707
02708
02709
02710
02711
02712
02713
02714
02715
02716
02717
02718
02719
02720
02721
02722
02723
02724
02725
02726
02727
02728
02729
02730
02731
02732
02733
02734
02735
02736
02737
02738
02739
02740
02741
02742
02743
02744
02745
02746
02747
02748
02749
02750
02751
02752
02753
02754
02755
02756
02757
02758
02759
02760
02761
02762
02763
02764
02765
02766
02767
02768
02769
02770
02771
02772
02773
02774
02775
02776
02777
02778
02779
02780
02781
02782
02783
02784
02785
02786
02787
02788
02789
02790
02791
02792
02793
02794
02795
02796
02797
02798
02799
02800
02801
02802
02803
02804
02805
02806
02807
02808
02809
02810
02811
02812
02813
02814
02815
02816
02817
02818
02819
02820
02821
02822
02823
02824
02825
02826
02827
02828
02829
02830
02831
02832
02833
02834
02835
02836
02837
02838
02839
02840
02841
02842
02843
02844
02845
02846
02847
02848
02849
02850
02851
02852
02853
02854
02855
02856
02857
02858
02859
02860
02861
02862
02863
02864
02865
02866
02867
02868
02869
02870
02871
02872
02873
02874
02875
02876
02877
02878
02879 __VGTL_END_NAMESPACE
02880
02881 #endif // __VGTL_DAG_H_