vgtl_dag.h

Go to the documentation of this file.

// DAG, directed graph implementation -*- C++ -*-

// $Id: vgtl_dag.h 555 2008-04-10 21:18:06Z herman $
// Copyright (C) 2001-2003 Hermann Schichl
//
// This file is part of the Vienna Graph Template Library.  This library
// is free software; you can redistribute it and/or modify it under the
// terms of the Library GNU General Public License as published by the
// Free Software Foundation; either version 2, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// Library GNU General Public License for more details.

// As a special exception, you may use this file as part of a free software
// library without restriction.  Specifically, if other files instantiate
// templates or use macros or inline functions from this file, or you compile
// this file and link it with other files to produce an executable, this
// file does not by itself cause the resulting executable to be covered by
// the Library GNU General Public License.  This exception does not however
// invalidate any other reasons why the executable file might be covered by
// the Library GNU General Public License.

#ifndef __VGTL_DAG_H_
#define __VGTL_DAG_H_

#include <vector>
#include <map>
#include <list>
#include <algorithm>
#include <iterator>
#include <string>
#include <utility>

#include <vgtl_helpers.h>
#include <vgtl_intadapt.h>

#include <vgtl_dagbase.h>

__VGTL_BEGIN_NAMESPACE

// forward reference
template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator,
          class _CIterator>
class _DG_iterator;


template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator,
          class _CIterator>
class _DG_walker
{
public:
  typedef _DG_walker<_Tp,_Tp&,_Tp*,_Ctr,_Iterator,_CIterator>    walker;
  typedef _DG_walker<_Tp,const _Tp&,const _Tp*,_Ctr,_Iterator,_CIterator>
                                                                  const_walker;

private:
  typedef _DG_walker<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_CIterator>    _Self;
  typedef _DG_iterator<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_CIterator>  _Itr;

public:

  typedef _Tp value_type;
  typedef _Ptr pointer;
  typedef _Ref reference;

private:
  typedef _DG_node<_Tp,_Ctr,_Iterator> _Node;
  typedef _Iterator _Ctr_iterator;
  typedef _CIterator _Ctr_const_iterator;

public:

  typedef _Ctr_iterator children_iterator;
  typedef _Ctr_iterator parents_iterator;
  typedef _Ctr_const_iterator children_const_iterator;
  typedef _Ctr_const_iterator parents_const_iterator;
  typedef _Node node_type;

  typedef size_t size_type;
  typedef ptrdiff_t difference_type;

public:
  _Node* _C_w_cur;

public:
  _DG_walker() {}

public:
  _DG_walker(_Node* __x) : _C_w_cur(__x) { }

  _DG_walker(const walker& __x) : _C_w_cur(__x._C_w_cur) {}

  reference operator*() const { return (*_C_w_cur)._C_data; }

#ifndef __SGI_STL_NO_ARROW_OPERATOR

  pointer operator->() const { return &(operator*()); }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */

public:
  const _Node* node() { return _C_w_cur; }

  size_type n_children() const { return (*_C_w_cur)._C_children.size(); }
  size_type n_parents() const { return (*_C_w_cur)._C_parents.size(); }

  bool is_root() const //checks if the node is root or not.
  { if(n_parents() != 1)
      return false;
    else
    {
      _Node* __help = (_Node*)*((*_C_w_cur)._C_parents.begin());
      return (*__help)._C_parents.empty();
    }
  }
  bool is_leaf() const
  { if(n_children() != 1)
      return false;
    else
    {
      _Node* __help = (_Node*)*((*_C_w_cur)._C_children.begin());
      return (*__help)._C_children.empty();
    }
  }

  bool is_ground() const { return (*_C_w_cur)._C_parents.empty(); }
  bool is_sky() const { return _C_w_cur ? (*_C_w_cur)._C_children.empty() : true; }
  
  children_iterator child_begin() { return (*_C_w_cur)._C_children.begin(); }
  children_const_iterator child_begin() const
        { return (*_C_w_cur)._C_children.begin(); }
  children_iterator child_end() { return (*_C_w_cur)._C_children.end(); }
  children_const_iterator child_end() const
        { return (*_C_w_cur)._C_children.end(); }

  parents_iterator parent_begin() { return (*_C_w_cur)._C_parents.begin(); }
  parents_const_iterator parent_begin() const
        { return (*_C_w_cur)._C_parents.begin(); }
  parents_iterator parent_end() { return (*_C_w_cur)._C_parents.end(); }
  parents_const_iterator parent_end() const
        { return (*_C_w_cur)._C_parents.end(); }
  
  template <class _Function>
  _Function for_each_child(_Function __f)
    {
      return for_each(child_begin(), child_end(), __f);
    }
  template <class _Function>
  _Function for_each_parent(_Function __f)
    {
      return for_each(parent_begin(), parent_end(), __f);
    }

public:

  bool operator==(const _Self& __x) const
        { return _C_w_cur == __x._C_w_cur; }
  bool operator!=(const _Self& __x) const 
        { return _C_w_cur != __x._C_w_cur; }

  _Self operator<<(parents_iterator __i) { 
    _Self __tmp = *this;
    __tmp._C_w_cur = (_Node*) *__i;
    return __tmp;
  }
 
  _Self operator>>(children_iterator __i) {
    _Self __tmp = *this;
    __tmp._C_w_cur = (_Node*) *__i;
    return __tmp;
  }

  _Self& operator<<=(parents_iterator __i) {
    _C_w_cur = (_Node*) *__i;
    return *this;
  }
  
  _Self& operator>>=(children_iterator __i) {
    _C_w_cur = (_Node*) *__i;
    return *this;
  }
  
  _Self operator<<(parents_const_iterator __i) { 
    _Self __tmp = *this;
    __tmp._C_w_cur = (_Node*) *__i;
    return __tmp;
  }
 
  _Self operator>>(children_const_iterator __i) {
    _Self __tmp = *this;
    __tmp._C_w_cur = (_Node*) *__i;
    return __tmp;
  }

  _Self& operator<<=(parents_const_iterator __i) {
    _C_w_cur = (_Node*) *__i;
    return *this;
  }
  
  _Self& operator>>=(children_const_iterator __i) {
    _C_w_cur = (_Node*) *__i;
    return *this;
  }
  
  _Self& operator=(const _Itr& __x) {
        _C_w_cur = __x._C_i_cur;
        return *this;
  }

  _Self& operator=(const _Self& __x) {
        _C_w_cur = __x._C_w_cur;
        return *this;
  }

  _Self& operator=(const _Node& __n) {
        _C_w_cur = &__n;
        return *this;
  }
};


template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator,
          class _CIterator>
class _DG_iterator
{
public:
  typedef _DG_iterator<_Tp,_Tp&,_Tp*,_Ctr,_Iterator,_CIterator>  iterator;
  typedef _DG_iterator<_Tp,const _Tp&,const _Tp*,_Ctr,_Iterator,_CIterator>
                                                                const_iterator;
  typedef _DG_iterator<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_CIterator>  _Self;
  typedef _DG_walker<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_CIterator>    _Walk;


  typedef std::bidirectional_iterator_tag iterator_category;
  typedef _Tp value_type;
  typedef _Ptr pointer;
  typedef _Ref reference;
  typedef _DG_node<_Tp,_Ctr,_Iterator> _Node;
  typedef size_t size_type;
  typedef ptrdiff_t difference_type;
  typedef _Iterator _Ctr_iterator;
  typedef _CIterator _Ctr_const_iterator;

protected:
  _Node* _C_i_cur;
  std::vector<_Ctr_iterator> _C_i_cur_it;

public:
  _DG_iterator() : _C_i_cur_it() {_C_i_cur_it.reserve(32);}
  _DG_iterator(const iterator& __x) : _C_i_cur(__x._C_i_cur),
                                      _C_i_cur_it(__x._C_i_cur_it) {}


  bool operator==(const _Self& __x) const
        { return (_C_i_cur->_C_parents.empty() &&
                   __x._C_i_cur->_C_parents.empty()) ||
                 (_C_i_cur->_C_children.empty() &&
                   __x._C_i_cur->_C_children.empty()) ||
                 ( _C_i_cur == __x._C_i_cur &&
                   _C_i_cur_it == __x._C_i_cur_it);
        }
  bool operator!=(const _Self& __x) const
        { return (!_C_i_cur->_C_parents.empty() ||
                   !__x._C_i_cur->_C_parents.empty()) &&
                 (!_C_i_cur->_C_children.empty() ||
                   !__x._C_i_cur->_C_children.empty()) &&
                 ( _C_i_cur != __x._C_i_cur ||
                   _C_i_cur_it != __x._C_i_cur_it);
        }

  reference operator*() const { return (*_C_i_cur)._C_data; }

#ifndef __SGI_STL_NO_ARROW_OPERATOR

  pointer operator->() const { return &(operator*()); }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */

private:
  void find_start_node();
  void find_next_node();
  void find_prev_node();
  
public:
  _Self& operator=(const _Walk& __x) {
        _C_i_cur = __x._C_w_cur;
        _C_i_cur_it.erase(_C_i_cur_it.begin(), _C_i_cur_it.end());
        // we have to find the next postorder node and
        // initialize the vector of iterators.
        find_start_node();
        return *this;
  }


  _Self& operator++() {
    find_next_node();
    return *this;
  }
  _Self operator++(int) {
    _Self __tmp = *this;
    ++*this;
    return __tmp;
  }

  _Self& operator--() {
    find_prev_node();
    return *this;
  }
  _Self operator--(int) {
    _Self __tmp = *this;
    --*this;
    return __tmp;
  }
};

#ifndef __VGTL_CLASS_PARTIAL_SPECIALIZATION // Specifies the iterator to be bi-directional.
template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator,
          class _CIterator>
inline bidirectional_iterator_tag
iterator_category(const _DG_iterator<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_CIterator>&)
{
  return bidirectional_iterator_tag();
}

template <class _Tp, class _Ref, class _Ptr, class _Ct, class _Iterator,
          class _CIterator> //Types the value of the iterator.
inline _Tp*
value_type(const _DG_iterator<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_CIterator>&)
{
  return 0;
}

//Tells the distance or we can say the no. of edges we want to traverse to reach 
//from one node to another through depth first pre-order walk. 


template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator,
          class _CIterator>  
inline ptrdiff_t*                                        
distance_type(const _DG_iterator<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_CIterator>&)
{
  return 0;
}

#endif /* __VGTL_CLASS_PARTIAL_SPECIALIZATION */


// Suppose we are in particlular node, this function tells us the path to
// this node from the top of the ground.Uses the preorder depth-first search
// and makes sure to visit the node only once.   
template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator,
          class _CIterator> 
void                                                                        
_DG_iterator<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_CIterator>::find_start_node()                 
{                                                                         
  _Node* __s = _C_i_cur;
  _Ctr_iterator __help;

  while(!__s->_C_parents.empty())
  {
    __help = ((_Node*)*__s->_C_parents.begin());
    _C_i_cur_it.insert(_C_i_cur_it.begin(),
        __help->get_entry_iterator((void*)__s));
    __s = __help;
  }
  while(!_C_i_cur->_C_children.empty())
  {
    
    for(__help = _C_i_cur->_C_children.begin();
        __help != _C_i_cur->_C_children.end(); ++__help)
    {
      __s = (_Node*)*__help;
      if(*(__s->_C_parents.begin()) == (void*)_C_i_cur)
        break;
    }
    if(__help == _C_i_cur->_C_children.end())
      break;
    _C_i_cur = __s;
    _C_i_cur_it.push_back(__help);
  }
  if(_C_i_cur->_C_children.empty())
  { // now we have reached sky -> go back one step
    __help = _C_i_cur_it.back();
    _C_i_cur_it.pop_back();
    _C_i_cur = (_Node*)*__help;
  }
}

//This finds the next node which comes after the present node through depth first search.
 


template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator,
          class _CIterator> 
void                                                                     
_DG_iterator<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_CIterator>::find_next_node()
{
  if(!_C_i_cur->_C_parents.empty()) // not yet through
  {
    _Ctr_iterator __help(_C_i_cur_it.back());
    _Node* __par;

    _C_i_cur_it.pop_back();
    __par = (_Node*)*(_C_i_cur->_C_parents.begin());

    for(++__help; __help != __par->_C_children.end(); ++__help)
    { // go to next subgraph
      _Node* __s = (_Node*)*__help;
      if(*(__s->_C_parents.begin()) == (void*)_C_i_cur)
      { // this is a valid subgraph
        _C_i_cur_it.push_back(__help);
        _C_i_cur = __s;
        while(!_C_i_cur->_C_children.empty());
        { // follow to the next leaf
          for(__help = _C_i_cur->_C_children.begin();
              __help != _C_i_cur->_C_children.end(); ++__help)
          {
            __s = (_Node*)*__help;
            if(*(__s->_C_parents.begin()) == (void*)_C_i_cur)
              break;
          }
          if(__help == _C_i_cur->_C_children.end())
            break;
          _C_i_cur = __s;
          _C_i_cur_it.push_back(__help);
        }
        break;
      } 
    }
    if(__help == __par->_C_children.end())
    {  // this was the last subtree -> hop one level up
      _C_i_cur = __par;
    }
    else if(_C_i_cur->_C_children.empty())
    { // we have reached sky -> go back one step
      __help = _C_i_cur_it.back();
      _C_i_cur_it.pop_back();
      _C_i_cur = (_Node*)*__help;
    }
  }
}

//Finds the previous node which comes from the current node through depth first search.


template <class _Tp, class _Ref, class _Ptr, class _Ctr, class _Iterator,
          class _CIterator> 
void                                                                     
_DG_iterator<_Tp,_Ref,_Ptr,_Ctr,_Iterator,_CIterator>::find_prev_node()
{
#if 0
  _Ctr_iterator help;

  if(_C_i_cur->_C_children.empty()) // this is a leaf -> go up
  {
    while(1)
    {
      if(_C_i_cur->_C_parent == NULL) // already through
        break;
      help = _C_i_cur_it.back();
      _C_i_cur_it.pop_back();
      _C_i_cur = (_Node*)_C_i_cur->_C_parent;
      if(help != _C_i_cur->_C_children.begin())
      { // go to prev subtree
        --help;
        _C_i_cur_it.push_back(help);
        _C_i_cur = (_Node*)*help;
        break;
      }
    }
  }
  else // go down
  {
    help = _C_i_cur->_C_children.end();
    --help;
    _C_i_cur_it.push_back(help);
    _C_i_cur = (_Node*)*help;
  }
#endif
}


template <class _Tp, class _Ctr, class _Iterator, class _CIterator,
          class _Inserter, class _Alloc>
class __DG : public _DG_base<_Tp, _Ctr, _Iterator, _CIterator, _Alloc>
{
public:
  typedef _Ctr  container_type;
  typedef _Iterator children_iterator;
  typedef _Iterator parents_iterator;
  typedef _CIterator children_const_iterator;
  typedef _CIterator parents_const_iterator;
  typedef _Inserter container_insert_arg;

protected:
  typedef void* _Void_pointer;
  typedef _DG_base<_Tp, container_type, children_iterator,
                   children_const_iterator, _Alloc> _Base;
  typedef _DG_node<_Tp, container_type, children_iterator> _Node;
  typedef __DG<_Tp,_Ctr,_Iterator,_CIterator,_Inserter,_Alloc> _Self;
  typedef std::pair<_Node*,_Node*> _RV_DG;
  typedef _Iterator container_iterator;
  typedef _CIterator container_const_iterator;

public:

  typedef _Tp                   value_type;
  typedef _Node                 node_type;
  typedef value_type*           pointer;
  typedef const value_type*     const_pointer;
  typedef value_type&           reference;
  typedef const value_type&     const_reference;
  typedef size_t                size_type;
  typedef ptrdiff_t             difference_type;

  typedef typename _Base::allocator_type allocator_type;
  allocator_type get_allocator() const { return _Base::get_allocator(); }

public:
  typedef _DG_iterator<_Tp,_Tp&,_Tp*,container_type,children_iterator,
                       children_const_iterator> iterator;
  typedef _DG_iterator<_Tp,const _Tp&,const _Tp*,container_type,
                children_iterator,children_const_iterator> const_iterator;

#ifdef __VGTL_CLASS_PARTIAL_SPECIALIZATION

  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
  typedef std::reverse_iterator<iterator>       reverse_iterator;
#else /* __VGTL_CLASS_PARTIAL_SPECIALIZATION */

  typedef std::reverse_bidirectional_iterator<const_iterator,value_type,
                                         const_reference,difference_type>
          const_reverse_iterator;
  typedef std::reverse_bidirectional_iterator<iterator,value_type,reference,
                                         difference_type>
          reverse_iterator;
#endif /* __VGTL_CLASS_PARTIAL_SPECIALIZATION */

  typedef _DG_walker<_Tp,_Tp&,_Tp*,container_type,children_iterator,
                     children_const_iterator> walker;
  typedef _DG_walker<_Tp,const _Tp&,const _Tp*,container_type,children_iterator,
                     children_const_iterator> const_walker;

  typedef std::pair<walker,walker>     edge;
  typedef std::pair<edge,bool>         enhanced_edge;

protected:
  typedef std::pair<_RV_DG, std::vector<enhanced_edge> > erased_part;

protected:
#ifdef __VGTL_HAS_NAMESPACES
  using _Base::_C_ground;
  using _Base::_C_sky;
  using _Base::_C_mark;
  using _Base::_C_put_node;
  using _Base::_C_get_node;
#endif /* __VGTL_HAS_NAMESPACES */

protected:
  _Node* _C_create_node(const _Tp& __x)
  {
    _Node* __p = _C_get_node();
    __p->_C_visited = 0;
    __VGTL_TRY {
      _VGTL_Construct_2(&__p->_C_data, __x);
      _VGTL_Construct_1(&__p->_C_children);
      _VGTL_Construct_1(&__p->_C_parents);
    }
    __VGTL_UNWIND(_C_put_node(__p));
    return __p;
  }

  _Node* _C_create_node()
  {
    _Node* __p = _C_get_node();
    __p->_C_visited = 0;
    __VGTL_TRY {
      _VGTL_Construct_1(&__p->_C_data);
      _VGTL_Construct_1(&__p->_C_children);
      _VGTL_Construct_1(&__p->_C_parents);
    }
    __VGTL_UNWIND(_C_put_node(__p));
    return __p;
  }

  void _C_destroy_node(_Node* __p)
  {
    __p->_C_visited = 0;
    _VGTL_Destroy(&__p->_C_data);
    _VGTL_Destroy(&__p->_C_children);
    _VGTL_Destroy(&__p->_C_parents);
    _C_put_node(__p);
  }

public:
  explicit __DG(const allocator_type& __a = allocator_type()) : _Base(__a) {}

  walker ground()
    { walker __help(this->_C_ground);
      return __help; }

  walker sky()
    { walker __help(this->_C_sky);
      return __help; }

  const_walker ground() const
    { const_walker __help(this->_C_ground); 
      return __help; }

  const_walker sky() const
    { const_walker __help(this->_C_sky);
      return __help; }

  children_iterator root_begin()
    { return this->_C_ground->_C_children.begin(); }
  children_iterator root_end()
    { return this->_C_ground->_C_children.end(); }
      
  children_const_iterator root_begin() const
    { return this->_C_ground->_C_children.begin(); }
  children_const_iterator root_end() const
    { return this->_C_ground->_C_children.end(); }
      
  parents_iterator leaf_begin()
    { return this->_C_sky->_C_parents.begin(); }
  parents_iterator leaf_end()
    { return this->_C_sky->_C_parents.end(); }
      
  parents_const_iterator leaf_begin() const
    { return this->_C_sky->_C_parents.begin(); }
  parents_const_iterator leaf_end() const
    { return this->_C_sky->_C_parents.end(); }
      
  iterator begin() // goes first node of the walk
    {
      iterator __help(this->_C_ground);
      return __help;
    }
  const_iterator begin() const 
    {
      const_iterator __help(this->_C_ground);
      return __help;
    }

  iterator end()
    {
      iterator __help(this->_C_sky);
      return --__help;
    }
  const_iterator end() const
    {
      const_iterator __help(this->_C_sky);
      return --__help;
    }

  reverse_iterator rbegin()
        { return reverse_iterator(end()); }
  reverse_iterator rend()
        { return reverse_iterator(begin()); }

  const_reverse_iterator rbegin() const
        { return const_reverse_iterator(end()); }
  const_reverse_iterator rend() const
        { return const_reverse_iterator(begin()); }
 
  bool empty() const
      { return *((*this->_C_ground)._C_children.begin()) == (void*)this->_C_sky; }

  size_type size() const {
    size_type __result = 0;
    distance(begin(), end(), __result);
    return __result;
  }

  size_type max_size() const { return size_type(-1); }

  void swap(_Self& __x)
    { __STD::swap(this->_C_ground, __x._C_ground);
      __STD::swap(this->_C_sky, __x._C_sky);
      __STD::swap(_C_mark, __x._C_mark); }

  walker insert_node_in_graph(_Node* __n, const walker& __parent,
                            const walker& __child,
                            const container_insert_arg& __Itc,
                            const container_insert_arg& __Itp) 
        { __parent._C_w_cur->_C_children.insert(__Itc, (void*)__n);
          __child._C_w_cur->_C_parents.insert(__Itp, (void*)__n);
          __n->_C_children.push_back((void*)__child._C_w_cur);
          __n->_C_parents.push_back((void*)__parent._C_w_cur);
          return walker(__n);
        }

  walker insert_in_graph(const _Tp& __x,  const walker& __parent,
                       const walker& __child,
                       const container_insert_arg& __Itc,
                       const container_insert_arg& __Itp)
        { 
          _Node* __tmp = _C_create_node(__x);
          return insert_node_in_graph(__tmp, __parent, __child, __Itc, __Itp);
        }
  
  walker insert_in_graph(const walker& __parent,
                       const walker& __child,
                       const container_insert_arg& __Itc,
                       const container_insert_arg& __Itp)
        { return insert_in_graph(_Tp(), __parent, __child, __Itc, __Itp); }

  void insert_subgraph(_Self& __subgraph,
                       const walker& __parent,
                       const walker& __child,
                       const container_insert_arg& __Itc,
                       const container_insert_arg& __Itp) 
        {
          __subgraph.add_all_children(inserter(__parent._C_w_cur->_C_children,
                __Itc), __parent._C_w_cur);
          __subgraph.add_all_parents(inserter(__child._C_w_cur->_C_parents,
                __Itp), __child._C_w_cur);
          __subgraph.clear_children();
          __subgraph.clear_parents();
        }
 
#ifdef __VGTL_MEMBER_TEMPLATES

  template <template <class __Tp, class __AllocTp> class __SequenceCtr1,
            template <class __Tp, class __AllocTp> class __SequenceCtr2,
            class _Allocator1, class _Allocator2>
  walker insert_node_in_graph(_Node* __node,
                       const __SequenceCtr1<walker,_Allocator1>& __parents,
                       const __SequenceCtr2<walker,_Allocator2>& __children)                                       
  {
    typedef typename __SequenceCtr1<walker,_Allocator1>::const_iterator
                                                                     _Sequ_itp;
    typedef typename __SequenceCtr2<walker,_Allocator2>::const_iterator
                                                                     _Sequ_itc;

    for(_Sequ_itp __b = __parents.begin(); __b != __parents.end(); ++__b)
    {
      __node->_C_parents.insert(__node->_C_parents.end(), (void*)(*__b).node());
      (*__b)._C_w_cur->_C_children.insert((*__b)._C_w_cur->_C_children.end(),
          (void*)__node);
    }
    for(_Sequ_itc __b = __children.begin(); __b != __children.end(); ++__b)
    {
      __node->_C_children.insert(__node->_C_children.end(), (void*)(*__b).node());
      (*__b)._C_w_cur->_C_parents.insert((*__b)._C_w_cur->_C_parents.end(),
          (void*)__node);
    }
    return walker(__node);
  }

  template <template <class __Tp, class __AllocTp> class __SequenceCtr1,
            template <class __Tp, class __AllocTp> class __SequenceCtr2,
            class _Allocator1, class _Allocator2>
  walker insert_in_graph(const _Tp& __x,
                       const __SequenceCtr1<walker,_Allocator1>& __parents,
                       const __SequenceCtr2<walker,_Allocator2>& __children)
  {
    _Node* __tmp = _C_create_node(__x);
    return insert_node_in_graph(__tmp, __parents, __children);
  }

  template <template <class __Tp, class __AllocTp> class __SequenceCtr1,
            template <class __Tp, class __AllocTp> class __SequenceCtr2,
            class _Allocator1, class _Allocator2>
  walker insert_in_graph(const __SequenceCtr1<walker,_Allocator1>& __parents,
                         const __SequenceCtr2<walker,_Allocator2>& __children)
  {
    _Node* __tmp = _C_create_node();
    return insert_node_in_graph(__tmp, __parents, __children);
  }

  template <template <class __Tp, class __AllocTp> class __SequenceCtr,
            class _Allocator>
  walker insert_node_in_graph(_Node* __node, const walker& __parent,
                       const container_insert_arg& __pref,
                       const __SequenceCtr<walker,_Allocator>& __children)
  {
    typedef typename __SequenceCtr<walker,_Allocator>::const_iterator _Sequ_it;
    _Sequ_it __b;

    __node->_C_parents.insert(__node->_C_parents.end(), (void*)__parent._C_w_cur);
    __parent._C_w_cur->_C_children.insert(__pref, (void*)__node);
    for(__b = __children.begin(); __b != __children.end(); ++__b)
    {
      __node->_C_children.insert(__node->_C_children.end(),
          (void*)(*__b)._C_w_cur);
      (*__b)._C_w_cur->_C_parents.insert((*__b)._C_w_cur->_C_parents.end(),
          (void*)__node);
    }
    return walker(__node);
  }

  template <template <class __Tp, class __AllocTp> class __SequenceCtr,
            class _Allocator>
  walker insert_in_graph(const _Tp& __x, const walker& __parent,
                         const container_insert_arg& __pref,
                         const __SequenceCtr<walker,_Allocator>& __children)
  {
    _Node* __tmp = _C_create_node(__x);
    return insert_node_in_graph(__tmp, __parent, __pref, __children);
  }

  template <template <class __Tp, class __AllocTp> class __SequenceCtr,
            class _Allocator>
  walker insert_in_graph(const walker& __parent,
                         const container_insert_arg& __pref,
                         const __SequenceCtr<walker,_Allocator>& __children)
  {
    _Node* __tmp = _C_create_node();
    return insert_node_in_graph(__tmp, __parent, __pref, __children);
  }

  template <template <class __Tp, class __AllocTp> class __SequenceCtr,
            class _Allocator>
  walker insert_node_in_graph(_Node* __node,
                const __SequenceCtr<walker,_Allocator>& __parents,
                const walker& __child,
                const container_insert_arg& __cref)
  {
    typedef typename __SequenceCtr<walker,_Allocator>::const_iterator _Sequ_it;
    _Sequ_it __b;

    __node->_C_children.insert(__node->_C_children.end(), (void*)__child.node());
    __child._C_w_cur->_C_parents.insert(__cref, (void*)__node);
    for(__b = __parents.begin(); __b != __parents.end(); ++__b)
    {
      __node->_C_parents.insert(__node->_C_parents.end(), (void*)(*__b).node());
      (*__b)._C_w_cur->_C_children.insert((*__b)._C_w_cur->_C_children.end(),
          (void*)__node);
    }
    return walker(__node);
  }

  template <template <class __Tp, class __AllocTp> class __SequenceCtr,
            class _Allocator>
  walker insert_in_graph(const _Tp& __x,
              const __SequenceCtr<walker,_Allocator>& __parents,
              const walker& __child,
              const container_insert_arg& __cref)
  {
    _Node* __tmp = _C_create_node(__x);
    return insert_node_in_graph(__tmp, __parents, __child, __cref);
  }

  template <template <class __Tp, class __AllocTp> class __SequenceCtr,
            class _Allocator>
  walker insert_in_graph(const __SequenceCtr<walker,_Allocator>& __parents,
                         const walker& __child,
                         const container_insert_arg& __cref)
  {
    _Node* __tmp = _C_create_node();
    return insert_node_in_graph(__tmp, __parents, __child, __cref);
  }

  template <template <class __Tp, class __AllocTp> class __SequenceCtr1,
            template <class __Tp, class __AllocTp> class __SequenceCtr2,
            class _Allocator1, class _Allocator2>
  void insert_subgraph(_Self& __subgraph,
                       const __SequenceCtr1<walker,_Allocator1>& __parents,
                       const __SequenceCtr2<walker,_Allocator2>& __children)
  {
    typedef typename __SequenceCtr1<walker,_Allocator1>::const_iterator
                                                                     _Sequ_itp;
    typedef typename __SequenceCtr2<walker,_Allocator2>::const_iterator
                                                                     _Sequ_itc;
    _Sequ_itp __sitp;
    _Sequ_itc __sitc;
    children_iterator __b;
    walker __wb;
    _Node* __n;

    __sitp = __parents.begin();
    for(__b = __subgraph._C_ground->_C_children.begin();
        __b != __subgraph._C_ground->_C_children.end();
        ++__b)
    {
      if(__sitp == __parents.end())
        __wb = (*this)._C_ground;
      else
        __wb = *__sitp++;
      __n = __wb.node();
      __n->_C_children.insert(__n->_C_children.end(), *__b);
      ((_Node*)*__b)->_C_parents.insert(((_Node*)*__b)->_C_parents.end(),
                                        (void*)__n);
    }
    __sitc = __children.begin();
    for(__b = __subgraph._C_sky->_C_parents.begin();
        __b != __subgraph._C_sky->_C_parents.end();
        ++__b)
    {
      if(__sitc == __children.end())
        __wb = (*this)._C_sky;
      else
        __wb = *__sitc++;
      __n = __wb.node();
      __n->_C_parents.insert(__n->_C_parents.end(), *__b);
      ((_Node*)*__b)->_C_children.insert(((_Node*)*__b)->_C_children.end(),
                                        (void*)__n);
    }
    __subgraph.clear_children();
    __subgraph.clear_parents();
  }
#endif /* __VGTL_MEMBER_TEMPLATES */
  
  void add_edge(const edge& __edge,
                const container_insert_arg& __Itc,
                const container_insert_arg& __Itp)
        { add_edge(__edge.first, __edge.second, __Itc, __Itp); }

  void add_edge(const walker& __parent, const walker& __child,
                const container_insert_arg& __Itc,
                const container_insert_arg& __Itp)
        {
          int do_remove(0);
          if(__parent._C_w_cur->_C_children.size() == 1)
          {
            container_iterator __it;
            __it = __parent._C_w_cur->_C_children.begin();
            if(*__it == (void*)this->_C_sky)
              do_remove += 1;
          }
          if(__child._C_w_cur->_C_parents.size() == 1)
          {
            container_iterator __it;
            __it = __child._C_w_cur->_C_parents.begin();
            if(*__it == (void*)this->_C_ground)
              do_remove += 2;
          }
          __parent._C_w_cur->_C_children.insert(__Itc, (void*)__child._C_w_cur);
          __child._C_w_cur->_C_parents.insert(__Itp, (void*)__parent._C_w_cur);
          if(do_remove & 1) // remove sky from parent
          {
            container_iterator __it;
            __it = __parent._C_w_cur->get_childentry_iterator((void*)this->_C_sky);
            __parent._C_w_cur->_C_children.erase(__it);
            __it = this->_C_sky->get_parententry_iterator((void*)__parent._C_w_cur);
            this->_C_sky->_C_parents.erase(__it);
          }
          if(do_remove & 2 &&
             (__parent._C_w_cur != (void*)this->_C_ground ||
              __child._C_w_cur != (void*)this->_C_sky))
            // remove ground from child
          {
            container_iterator __it;
            __it = __child._C_w_cur->get_parententry_iterator((void*)this->_C_ground);
            __child._C_w_cur->_C_parents.erase(__it);
            __it = this->_C_ground->get_childentry_iterator((void*)__child._C_w_cur);
            this->_C_ground->_C_children.erase(__it);
          }
        }

  void replace_edge_to_child(const walker& __parent,
                             const walker& __child_old,
                             const walker& __child_new)
        { container_iterator __it;
          __it = __parent._C_w_cur->get_childentry_iterator((void*) __child_old._C_w_cur);
          if(__it == __parent._C_w_cur->_C_children.end())
            return;  // don't replace unless it's there
          (*__it) = (void*) __child_new._C_w_cur;
          __it = __child_old._C_w_cur->get_parententry_iterator((void*) __parent._C_w_cur);
          if(__it == __child_old._C_w_cur->_C_parents.end())
            return;     // should never happen unless corruption occurred
          __child_old._C_w_cur->_C_parents.erase(__it);
          if(__child_old._C_w_cur->_C_parents.empty())
          {
            __child_old._C_w_cur->_C_parents.insert(
                     __child_old._C_w_cur->_C_parents.end(), (void*)this->_C_ground);
            this->_C_ground->_C_children.insert(this->_C_ground->_C_children.end(),
                     (void*)__child_old._C_w_cur);
          }
          if(__child_new._C_w_cur->_C_parents.size() == 1)
          {
            if(*__child_new._C_w_cur->_C_parents.begin() == (void*)this->_C_ground)
            {
              __it = this->_C_ground->get_childentry_iterator((void*) __child_new._C_w_cur);
              if(__it != this->_C_ground->_C_children.end()) // always!
                this->_C_ground->_C_children.erase(__it);
              __child_new._C_w_cur->_C_parents.erase(__child_new._C_w_cur->
                  _C_parents.begin());
            }
          }
          __child_new._C_w_cur->_C_parents.insert(
             __child_new._C_w_cur->_C_parents.end(), (void*)__parent._C_w_cur);
        }

  void replace_edge_to_parent(const walker& __parent_old,
                        const walker& __parent_new, const walker& __child)
        { container_iterator __it;
          __it = __child._C_w_cur->get_parententry_iterator((void*) __parent_old._C_w_cur);
          if(__it == __child._C_w_cur->_C_parents.end())
            return;  // don't replace unless it's there
          (*__it) = (void*) __parent_new._C_w_cur;
          __it = __parent_old._C_w_cur->get_childentry_iterator((void*) __child._C_w_cur);
          if(__it == __parent_old._C_w_cur->_C_children.end())
            return;     // should never happen unless corruption occurred
          __parent_old._C_w_cur->_C_children.erase(__it);
          if(__parent_old._C_w_cur->_C_children.empty())
          {
            __parent_old._C_w_cur->_C_children.insert(
                  __parent_old._C_w_cur->_C_children.end(), (void*)this->_C_sky);
            this->_C_sky->_C_parents.insert(this->_C_sky->_C_parents.end(),
                     (void*)__parent_old._C_w_cur);
          }
          if(__parent_new._C_w_cur->_C_children.size() == 1)
          {
            if(*__parent_new._C_w_cur->_C_children.begin() == (void*)this->_C_sky)
            {
              __it = this->_C_sky->get_parententry_iterator((void*) __parent_new._C_w_cur);
              if(__it != this->_C_sky->_C_parents.end()) // always!
                this->_C_sky->_C_parents.erase(__it);
              __parent_new._C_w_cur->_C_children.erase(__parent_new._C_w_cur->
                  _C_children.begin());
            }
          }
          __parent_new._C_w_cur->_C_children.insert(
            __parent_new._C_w_cur->_C_children.end(), (void*)__child._C_w_cur);
        }

  void remove_edge(const edge& __edge)
        { remove_edge(__edge.first, __edge.second); }

  void remove_edge_and_deattach(const walker& __parent, const walker& __child)
        { container_iterator __it;
          __it = __parent._C_w_cur->get_childentry_iterator((void*) __child._C_w_cur);
          if(__it == __parent._C_w_cur->_C_children.end())
            return;     // no such edge
          __parent._C_w_cur->_C_children.erase(__it);
          __it = __child._C_w_cur->get_parententry_iterator((void*) __parent._C_w_cur);
          if(__it == __child._C_w_cur->_C_parents.end())
            return;     // should never happen unless corruption occurred
          __child._C_w_cur->_C_parents.erase(__it);
        }

  void remove_edge(const walker& __parent, const walker& __child)
        { 
          remove_edge_and_deattach(__parent, __child);
          // now make sure that no dangling nodes hang around. If we have
          // just created a node without parents or a node without children,
          // then connect them to ground or to sky.
          if(__parent._C_w_cur->_C_children.empty())
          {
            __parent._C_w_cur->_C_children.insert(
                     __parent._C_w_cur->_C_children.end(), (void*)this->_C_sky);
            this->_C_sky->_C_parents.insert(this->_C_sky->_C_parents.end(),
                     (void*)__parent._C_w_cur);
          }
          if(__child._C_w_cur->_C_parents.empty())
          {
            __child._C_w_cur->_C_parents.insert(
                     __child._C_w_cur->_C_parents.end(), (void*)this->_C_ground);
            this->_C_ground->_C_children.insert(this->_C_ground->_C_children.end(),
                     (void*)__child._C_w_cur);
          }
        }
 
  template <class Compare>                                             
  void sort_child_edges(walker __position, children_iterator first,  
                        children_iterator last, Compare comp)         
  { (*__position._C_w_cur).sort_child_edges(first, last, comp); }

  template <class Compare>
  void sort_parent_edges(walker __position, parents_iterator first,
                         parents_iterator last, Compare comp)
  { (*__position._C_w_cur).sort_parent_edges(first, last, comp); }

  template <class Compare>
  void sort_child_edges(walker __position, Compare comp)
  { (*__position._C_w_cur).sort_child_edges(__position.child_begin(),
                                            __position.child_end(), comp); }

  template <class Compare>
  void sort_parent_edges(walker __position, Compare comp)
  { (*__position._C_w_cur).sort_parent_edges(__position.parent_begin(),
                                             __position.parent_end(), comp); }

  walker insert_node(_Node* _node, const walker& __position,
                   const container_insert_arg& __It) 
        { if(__position.sky()) // cannot insert after the virtual leaf
            return;
          __position._C_w_cur->add_all_children(
                inserter(_node->_C_children, __It), _node);
          __position._C_w_cur->clear_children();
          __position._C_w_cur->_C_children.insert(
                __position._C_w_cur->_C_children.end(), _node);
          _node->_C_parents.insert(_node->_C_parents.end(),__position._C_w_cur);
          return walker(_node);
        }

  walker insert_node(const _Tp& __x, const walker& __position,
                   const container_insert_arg& __It)
        { return insert_node(_C_create_node(__x), __position, __It); }


  walker insert_node(const walker& __position,
                   const container_insert_arg& __It)
        { return insert_node(_Tp(), __position, __It); }

  walker insert_node_before(_Node* _node, const walker& __position,
                          const container_insert_arg& __It) 
        { if(__position.ground())
            return;
          __position._C_w_cur->add_all_parents(
                back_inserter(_node->_C_parents), _node);
          __position._C_w_cur->clear_parents();
          __position._C_w_cur->_C_parents.insert(
                __position._C_w_cur->_C_parents.end(), _node);
          _node->_C_children.push_back(__position.C_w_cur);
          return walker(_node);
        }

  void insert_node_before(const _Tp& __x, const walker& __position,
                          const container_insert_arg& __It)
        { return insert_node_before(_C_create_node(__x), __position, __It); }

  void insert_node_before(const walker& __position,
                          const container_insert_arg& __It)
        { return insert_node_before(_Tp(), __position, __It); }


  void merge(const walker& __position, const walker& __second,
             bool merge_parent_edges = true, bool merge_child_edges = true)
        { _Node* __tp = __position._C_w_cur;
          _Node* __ts = __second._C_w_cur;
          _Node* __p;

          if(__position.is_sky() || __position.is_ground() ||
             __second.is_sky() || __second.is_ground() ||
             __position == __second)
            // cannot merge anything with sky, ground, or itself
            return;

          container_iterator __i, __j;
          bool mrg_it;
          bool __is_root = __position.is_root();
          bool __is_leaf = __position.is_leaf();
          
          for(__i = __ts->_C_children.begin();
              __i != __ts->_C_children.end(); ++__i)
          {
            mrg_it = 0;
            __p = (_Node*)*__i;
            if(merge_child_edges)
            {
              for(__j = __tp->_C_children.begin();
                  __j != __tp->_C_children.end(); ++__j)
              {
                if(*__i == *__j)
                {
                  mrg_it = 1;
                  break;
                }
              }
            }
            __j = __p->get_parententry_iterator(__ts);
            if(__p == this->_C_sky || mrg_it)
              __p->_C_parents.erase(__j);
            else
              *__j = (void *)__tp;
            if(!mrg_it && __p != this->_C_sky)
              __tp->_C_children.insert(__tp->_C_children.end(), (void*)__p);
          }
          if(__is_leaf && __tp->_C_children.size() > 1)
          {
            __j = this->_C_sky->get_parententry_iterator(__tp);
            this->_C_sky->_C_parents.erase(__j);
            __j = __tp->get_childentry_iterator(this->_C_sky);
            __tp->_C_children.erase(__j);
          }
          for(__i = __ts->_C_parents.begin();
              __i != __ts->_C_parents.end(); ++__i)
          {
            mrg_it = 0;
            __p = (_Node*)*__i;
            if(merge_parent_edges)
            {
              for(__j = __tp->_C_parents.begin();
                  __j != __tp->_C_parents.end(); ++__j)
              {
                if(*__i == *__j)
                {
                  mrg_it = 1;
                  break;
                }
              }
            }
            __j = __p->get_childentry_iterator(__ts);
            if(__p == this->_C_ground || mrg_it)
              __p->_C_children.erase(__j);
            else
              *__j = (void *)__tp;
            if(!mrg_it && __p != this->_C_ground)
              __tp->_C_parents.insert(__tp->_C_parents.end(), (void*)__p);
          }
          if(__is_root && __tp->_C_parents.size() > 1)
          {
            __j = this->_C_ground->get_childentry_iterator(__tp);
            this->_C_ground->_C_children.erase(__j);
            __j = __tp->get_parententry_iterator(this->_C_ground);
            __tp->_C_parents.erase(__j);
          }
          // here call the merge method for the data class
          (__tp->_C_data).merge(__ts->_C_data);
          __ts->clear_children();
          __ts->clear_parents();
          _C_destroy_node(__ts);
        }
  
  void erase(const walker& __position)
        { _Node* __tmp = __position._C_w_cur;

          if(!__tmp->_C_children.empty() && !__tmp->_C_parents.empty())
          { // cannot erase the virtual root or the virtual leaf node
            container_iterator __ip, __ic;
            _Node* __p;
            bool do_it;

            do_it = !__position.is_leaf();
            for(__ip = __tmp->_C_parents.begin();
                __ip != __tmp->_C_parents.end(); ++__ip)
            {
              __p = (_Node*)*__ip;
              __ic = __p->get_childentry_iterator(__tmp);
              ++__ic;
              if(__position.is_root())
              {
                                std::list<void*> __clst;
                for(container_iterator __icc = __tmp->_C_children.begin();
                    __icc != __tmp->_C_children.end(); ++__icc)
                {
                  _Node* __c = (_Node*)*__icc;
                  if(__c->_C_parents.size() == 1) // this node becomes a root
                  {
                    __c->_C_parents.insert(__c->_C_parents.end(), (void*)__p);
                                        __clst.push_back((void*)__c);
                  }
                }
                                __p->_C_children.insert(__ic, __clst.begin(), __clst.end());
              }
              else if(do_it || __p->_C_children.size() == 1)
                __tmp->add_all_children(inserter(__p->_C_children, __ic), __p);
              // we have to do this since inserting usually
              // invalidates the iterators. We have to do it
              // in this sequence because we do not want the
              // children to be reordered
              __ic = __p->get_childentry_iterator(__tmp);
              __p->_C_children.erase(__ic);
              if(__p->_C_children.empty())
                __p->_C_children.insert(__p->_C_children.end(),
                    (void*) this->_C_sky);
            }
            for(__ic = __tmp->_C_children.begin();
                __ic != __tmp->_C_children.end(); ++__ic)
            {
              __p = (_Node*)*__ic;
              __ip = __p->get_parententry_iterator(__tmp);
              __p->_C_parents.erase(__ip);
              if(__p->_C_parents.empty())
                __p->_C_parents.insert(__p->_C_parents.end(),
                    (void*) this->_C_ground);
            }
            __tmp->clear_parents();
            __tmp->clear_children();
            _C_destroy_node(__tmp);
          }
        }

  void partial_erase_to_parent(const walker& __position, const walker& __parent,                               unsigned int idx)
        { _Node* __tmp = __position._C_w_cur;
          _Node* __p = __parent._C_w_cur;

          if(!__tmp->_C_children.empty() && !__tmp->_C_parents.empty())
          { // cannot erase the virtual root or the virtual leaf node
            container_iterator __ic;
            bool do_it;

            do_it = !__position.is_leaf();
            __ic = __p->_C_children.begin()+idx;
            if(*__ic != (void*)__tmp)
              return;   // this is not a proper parent/child relation
            ++__ic;
            if(__position.is_root())
            {
                      std::list<void*> __clst;
              for(container_iterator __icc = __tmp->_C_children.begin();
                  __icc != __tmp->_C_children.end(); ++__icc)
              {
                _Node* __c = (_Node*)*__icc;
                if(__c->_C_parents.size() == 1) // this node becomes a root
                {
                  __c->_C_parents.insert(__c->_C_parents.end(), (void*)__p);
                                  __clst.push_back((void*)__c);
                                }
              }
                      __p->_C_children.insert(__ic, __clst.begin(), __clst.end());
            }
            else if(do_it || __p->_C_children.size() == 1)
              __tmp->add_all_children(inserter(__p->_C_children, __ic), __p);
            // we have to do this since inserting usually
            // invalidates the iterators. We have to do it
            // in this sequence because we do not want the
            // children to be reordered
            __ic = __p->_C_children.begin()+idx;
            __p->_C_children.erase(__ic);
            if(__p->_C_children.empty())
              __p->_C_children.insert(__p->_C_children.end(),
                  (void*) this->_C_sky);

            parents_iterator __ip;
            __ip = __tmp->get_parententry_iterator((void*)__parent._C_w_cur);
            __tmp->_C_parents.erase(__ip);
            
            if(__tmp->_C_parents.empty())
            {
              for(__ic = __tmp->_C_children.begin();
                  __ic != __tmp->_C_children.end(); ++__ic)
              {
                __p = (_Node*)*__ic;
                __ip = __p->get_parententry_iterator(__tmp);
                __p->_C_parents.erase(__ip);
                if(__p->_C_parents.empty())
                  __p->_C_parents.insert(__p->_C_parents.end(),
                      (void*) this->_C_ground);
              }
              __tmp->clear_children();
              _C_destroy_node(__tmp);
            }
          }
        }


private:
  void cut_excess_edges(const walker& __position, _Node* __ngrd, _Node* __nsky,
                        bool maximal, bool upwards, std::vector<enhanced_edge>& __ev)
  {
    std::vector<walker> __v(1);
    __v[0] = __position;
    cut_excess_edges(__v, __ngrd, __nsky, maximal, upwards, __ev);
  }

  bool parents_are_marked(int __mark, const walker& __pson)
  {
    parents_iterator _pit;
    const_walker __pr;
    walker __position(__pson);

    for(_pit = __position.parent_begin(); _pit != __position.parent_end();
        ++_pit)
    {
      __pr = __position << _pit;
      if(__pr.node()->_C_visited < __mark && !__pr.is_ground())
        return false;
    }
    return true;
  }
  
  bool children_are_marked(int __mark, const walker& __pson)
  {
    children_iterator _cit;
    const_walker __ch;
    walker __position(__pson);

    for(_cit = __position.child_begin(); _cit != __position.child_end();
        ++_cit)
    {
      __ch = __position >> _cit;
      if(__ch.node()->_C_visited < __mark && !__ch.is_sky())
        return false;
    }
    return true;
  }
  
  void dnrecursive_mark_node(int __mark, const walker& __pson, 
                             bool maximal)
  {
    children_iterator _cit;
    walker __position(__pson);

    if(__position._C_w_cur->_C_visited == __mark || // we've already been here
       __position.is_ground() || __position.is_sky()) // this is virtual
      return;
    if(!maximal && !parents_are_marked(__mark, __position))
      // in minimal removal only nodes, which can only be
      // reached by marked parents may be removed.
      return;
    __position._C_w_cur->_C_visited = __mark;
    for(_cit = __position.child_begin();
        _cit != __position.child_end(); ++_cit)
      dnrecursive_mark_node(__mark, __position>>_cit, maximal);
  }

  void uprecursive_mark_node(int __mark, const walker& __pson, 
                             bool maximal)
  {
    walker __position(__pson);
    parents_iterator _pit;

    if(__position._C_w_cur->_C_visited == __mark || // we've already been here
       __position.is_ground() || __position.is_sky()) // this is virtual
      return;
    if(!maximal && !children_are_marked(__mark, __position))
      // in minimal removal only nodes, which can only be
      // reached by marked parents may be removed.
      return;
    __position._C_w_cur->_C_visited = __mark;
    for(_pit = __position.parent_begin();
        _pit != __position.parent_end(); ++_pit)
      dnrecursive_mark_node(__mark, __position<<_pit, maximal);
  }

  void recursive_cut_edges(int __mark, const walker& __pson,
                _Node* __ngrd, _Node* __nsky, std::vector<enhanced_edge>& __ev)
  // ATTENTION: This has still an infinite loop bug if a the graph
  //            contains cycles.
  {
    children_iterator _cit;
    _Node* _h;
    walker _w;
    walker __position(__pson);
    edge _e;
    bool _rcf(false);
    std::list<children_iterator> _er_cit;

    for(_cit = __position.child_begin(); _cit != __position.child_end(); ++_cit)
    {
      _h = (_Node*)(*_cit);
      _w = __position >> _cit;
      if((__position._C_w_cur->_C_visited == __mark && _h->_C_visited < __mark)
       ||(__position._C_w_cur->_C_visited < __mark && _h->_C_visited == __mark))
      // we traverse from a "to be removed node" to a "to be kept node" or
      // vice verse
      {
        container_iterator __it;

        // remember the edge
        _e = make_pair(__position, _w);
        // remember the higher part of the edge for later removal
        _er_cit.push_back(_cit);
        // remove the lower part of the edge
        __it = _h->get_parententry_iterator((void*)__position._C_w_cur);
        if(__it != _h->_C_parents.end())
          _h->_C_parents.erase(__it);
        if(__position._C_w_cur->_C_visited == __mark)
          // we traverse from remove to keep
        {
          // now make sure that no dangling nodes hang around. If we have
          // just created a node without parents or a node without children,
          // then connect them to ground or to sky.
          if(_h->_C_parents.empty())
          {
            _h->_C_parents.insert(_h->_C_parents.end(), (void*)this->_C_ground);
            this->_C_ground->_C_children.insert(this->_C_ground->_C_children.end(),
                                          (void*)_h);
            _rcf = true;
          }
          else
            _rcf = false;
        }
        else
          // we traverse from keep to remove
        {
          if(_h->_C_parents.empty())
          {
            _h->_C_parents.insert(_h->_C_parents.end(), (void*)__ngrd);
            __ngrd->_C_children.insert(__ngrd->_C_children.end(), (void*)_h);
          }
        }
        __ev.push_back(make_pair(_e, _rcf));
      }
      recursive_cut_edges(__mark, _w, __ngrd, __nsky, __ev);
    }
    if(!_er_cit.empty())
    {
      // now remove all the upper parts of the edges
      // we have to do that so complicated, because
      // we cannot remove entries from a STL sequence
      // container while iterating it without knowing
      // which container it is.
      children_iterator _hit, _eit;
      typename std::list<children_iterator>::iterator _erc;

      _erc = _er_cit.begin();;
      _eit = __position._C_w_cur->_C_children.end(); 
      for(_hit = _cit = __position._C_w_cur->_C_children.begin();
          _cit != _eit; ++_cit)
      {
        if(_cit == *_erc)
          ++_erc;
        else
        {
          if(_cit != _hit)
            *_hit = *_cit;
          ++_hit;
        }
      }
      __position._C_w_cur->_C_children.erase(_hit, _eit);

      if(__position._C_w_cur->_C_visited == __mark)
      {
        // we remove this node
        if(__position._C_w_cur->_C_children.empty())
        {
          __position._C_w_cur->_C_children.insert(
                  __position._C_w_cur->_C_children.end(), (void*)__nsky);
          __nsky->_C_parents.insert(__nsky->_C_parents.end(),
                  (void*)__position._C_w_cur);
        }
      }
      else
      {
        // now make sure that no dangling nodes hang around. If we have
        // just created a node without parents or a node without children,
        // then connect them to ground or to sky.
        if(__position._C_w_cur->_C_children.empty())
        {
          __position._C_w_cur->_C_children.insert(
                  __position._C_w_cur->_C_children.end(), (void*)this->_C_sky);
          this->_C_sky->_C_parents.insert(this->_C_sky->_C_parents.end(),
                  (void*)__position._C_w_cur);
        }
      }
    }
  }
  
#ifdef __VGTL_MEMBER_TEMPLATES
  template <template <class __Tp, class __AllocTp> class __SequenceCtr,
            class _Allocator>
  void cut_excess_edges(const __SequenceCtr<walker,_Allocator>& __positions,
                        _Node* __ngrd, _Node* __nsky, bool maximal,
                        bool upwards, std::vector<enhanced_edge>& __ev)
  {
    int _actmark = ++_C_mark;
    typename __SequenceCtr<walker,_Allocator>::const_iterator _pit;
    walker _w;

    for(_pit = __positions.begin(); _pit != __positions.end(); ++_pit)
    {
      _w = *_pit;
      if(upwards)
        uprecursive_mark_node(_actmark, _w, maximal);
      else
        dnrecursive_mark_node(_actmark, _w, maximal);
    }
    recursive_cut_edges(_actmark, ground(), __ngrd, __nsky, __ev);
  }
#endif /* __VGTL_MEMBER_TEMPLATES */
  //The algorithmic part of the erasing of the subgraph ends here
  
public:
  void clear_erased_part(erased_part& _ep)
  {
    _ep.second.clear();
    clear_graph(_ep.first.first);
  }

  erased_part erase_maximal_subgraph(const walker& __position)
        { _RV_DG __rv(_C_create_node(),_C_create_node());
          std::vector<enhanced_edge> __ev;

          cut_excess_edges(__position, __rv.first, __rv.second, true, false,
                           __ev);
          return make_pair(__rv,__ev);
        }

  erased_part erase_minimal_subgraph(const walker& __position)
        { _RV_DG __rv(_C_create_node(),_C_create_node());
          std::vector<enhanced_edge> __ev;

          cut_excess_edges(__position, __rv.first, __rv.second, false, false,
                           __ev);
          return make_pair(__rv,__ev);
        }

#ifdef __VGTL_MEMBER_TEMPLATES

  template <template <class __Tp, class __AllocTp> class __SequenceCtr,
            class _Allocator>
  erased_part erase_maximal_subgraph(
      const __SequenceCtr<walker,_Allocator>& __positions)
        { _RV_DG __rv(_C_create_node(),_C_create_node());
          std::vector<enhanced_edge> __ev;
          
          cut_excess_edges(__positions, __rv.first, __rv.second, true, false,
                           __ev);
          return make_pair(__rv,__ev);
        }

  template <template <class __Tp, class __AllocTp> class __SequenceCtr,
            class _Allocator>
  erased_part erase_minimal_subgraph(
      const __SequenceCtr<walker,_Allocator>& __positions)
        { _RV_DG __rv(_C_create_node(),_C_create_node());
          std::vector<enhanced_edge> __ev;
          
          cut_excess_edges(__positions, __rv.first, __rv.second, false, false,
                           __ev);
          return make_pair(__rv,__ev);
        }
#endif /* __VGTL_MEMBER_TEMPLATES */

  erased_part erase_maximal_pregraph(const walker& __position)
        { _RV_DG __rv(_C_create_node(),_C_create_node());
          std::vector<enhanced_edge> __ev;

          cut_excess_edges(__position, __rv.first, __rv.second, true, true,
                           __ev);
          return make_pair(__rv,__ev);
        }
  
  erased_part erase_minimal_pregraph(const walker& __position)
        { _RV_DG __rv(_C_create_node(),_C_create_node());
          std::vector<enhanced_edge> __ev;

          cut_excess_edges(__position, __rv.first, __rv.second, false, true,
                           __ev);
          return make_pair(__rv,__ev);
        }

#ifdef __VGTL_MEMBER_TEMPLATES

  template <template <class __Tp, class __AllocTp> class __SequenceCtr,
            class _Allocator>
  erased_part erase_maximal_pregraph(
      const __SequenceCtr<walker,_Allocator>& __positions)
        { _RV_DG __rv(_C_create_node(),_C_create_node());
          std::vector<enhanced_edge> __ev;
          
          cut_excess_edges(__positions, __rv.first, __rv.second, true, true,
                           __ev);
          return make_pair(__rv,__ev);
        }

  template <template <class __Tp, class __AllocTp> class __SequenceCtr,
            class _Allocator>
  erased_part erase_minimal_pregraph(
      const __SequenceCtr<walker,_Allocator>& __positions)
        { _RV_DG __rv(_C_create_node(),_C_create_node());
          std::vector<enhanced_edge> __ev;
          
          cut_excess_edges(__positions, __rv.first, __rv.second, false, true,
                           __ev);
          return make_pair(__rv,__ev);
        }
#endif /* __VGTL_MEMBER_TEMPLATES */

  bool erase_child(const walker& __position,
                   const children_iterator& __It)
        {
          _Node* __chld = (_Node*)*__It;

          if(__chld->_C_children.size() != 1 || __chld->_C_parents.size() != 1)
          { return false; }
          else
          {
            _Node* __c2;
            parents_iterator __pit;

            __c2 = (_Node*)*__chld->_C_children.begin();
            __pit = __c2->get_parententry_iterator((void*)__chld);
            *__pit = (void*)__position->_C_w_cur;
            *__It = (void*)__c2;
            _C_destroy_node(__chld);
            return true;
          }
        }

  bool erase_parent(const walker& __position,
                    const parents_iterator& __It)
        {
          _Node* __prnt = (_Node*)*__It;

          if(__prnt->_C_children.size() != 1 || __prnt->_C_parents.size() != 1)
          { return false; }
          else
          {
            _Node* __p2;
            children_iterator __cit;

            __p2 = (_Node*)*__prnt->_C_parents.begin();
            __cit = __p2->get_childentry_iterator((void*)__prnt);
            *__cit = (void*)__position->_C_w_cur;
            *__It = (void*)__p2;
            _C_destroy_node(__prnt);
            return true;
          }
        }

  void clear() { _Base::clear(); } 

private:
  _Node* copy_subgraph(_Node* __x, _Node* __par, std::map<_Node*,_Node*>& __nconn)
  { children_iterator cit;
    typedef typename std::map<_Node*,_Node*>::iterator map_it;
    std::pair<map_it,bool> _rv;
    _Node* __h = _C_create_node();
    _Node* __cs;
    map_it __cdit;

    _VGTL_Construct_2(&__h->_C_data, __x->_C_data);
    __h->_C_parents.insert(__h->_C_parents.end(), (void*)__par);
    __h->_C_visited = 0;
    if(__x->_C_parents.size() > 1)
      _rv = __nconn.insert(make_pair(__x,__h)); // keep for later use
    for(cit = __x->_C_children.begin(); cit != __x->_C_children.end(); ++cit)
    {
      __cs = (_Node*)*cit;
      __cdit = __nconn.find(__cs);// prevent copying 
      if(__cdit == __nconn.end()) // not found
        __h->_C_children.insert(__h->_C_children.end(),
                        copy_subgraph(__cs, __h, __nconn));
      else
      {
        (*__cdit).second->_C_parents.insert(
                                 (*__cdit).second->_C_parents.end(), __h);
        __h->_C_children.insert(__h->_C_children.end(),
                                                (void*)(*__cdit).second);
      }
    }
    return __h;
  }

public:
  __DG(const _Self& __x) : _Base(__x.get_allocator())
    { children_iterator cit;
      std::map<_Node*,_Node*> __nconn;
      __nconn.insert(make_pair(__x._C_sky, this->_C_sky));
      this->_C_mark = 0;
      this->_C_ground->clear_children();
      this->_C_sky->clear_parents();
      for(cit = __x._C_ground->_C_children.begin();
          cit != __x._C_ground->_C_children.end(); ++cit)
      {
        if((_Node*)*cit != __x._C_sky) // only wrong if graph is empty
          this->_C_ground->_C_children.insert(this->_C_ground->_C_children.end(),
                copy_subgraph((_Node*)*cit, this->_C_ground, __nconn));
      }
    }

  ~__DG() {}

  _Self& operator=(const _Self& __x); 

  _Self& operator=(const _RV_DG& __rl)
  {
    this->_C_ground = __rl.first;
    this->_C_sky = __rl.second;
    return *this;
  }

  _Self& operator=(const erased_part& __ep)
  {
    this->_C_ground = __ep.first.first;
    this->_C_sky = __ep.first.second;
    return *this;
  }

#if 0

  friend bool operator== __VGTL_NULL_TMPL_ARGS (
    const __DG& __x, const __DG& __y);
#endif
}; 

#if 0
// THIS DOES NOT WORK!
template <class _Tp, class _Ctr, class _Iterator, class _CIterator, 
          class _Inserter, class _Alloc>
inline bool operator==(const __DG<_Tp,_Ctr,_Iterator,_CIterator,_Inserter,
                                  _Alloc>& __x,
                       const __DG<_Tp,_Ctr,_Iterator,_CIterator,_Inserter,
                                  _Alloc>& __y)
{
  typedef typename __DG<_Tp,_Ctr,_Iterator,_CIterator,_Inserter,
                        _Alloc>::const_walker const_walker;
  const_walker __w1 = __x.begin(cw_pre);
  const_walker __w2 = __y.begin(cw_pre);
  const_walker __e1 = __x.end(cw_pre);
  const_walker __e2 = __y.end(cw_pre);
  
  // compare values and tree structure with a pre-post-order walk
  for(; __w1 != __e1 && __w2 != __e2 ; ++__w1, ++__w2)
    if(__w1.in_preorder() != __w2.in_preorder() ||
       (__w1.in_preorder() && *__w1 != *__w2))
      return false;
  return __w1 == __e1 && __w2 == __e2;
}
#endif

template <class _Tp, class _Ctr, class _Iterator, class _CIterator,
          class _Inserter, class _Alloc>
__DG<_Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc>&
__DG<_Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc>::operator=(
    const __DG<_Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc>& __x)
{
  if (this != &__x)
  {
    children_iterator cit;
    std::map<_Node*,_Node*> __nconn;
    
    clear();
    __nconn.insert(make_pair(__x._C_sky, this->_C_sky));
    this->_C_mark = 0;
    for(cit = __x._C_ground->_C_children.begin();
        cit != __x._C_ground->_C_children.end(); ++cit)
    {
      if((_Node*)*cit != __x._C_sky) // only wrong if graph is empty
        this->_C_ground->_C_children.insert(this->_C_ground->_C_children.end(),
                copy_subgraph((_Node*)*cit, this->_C_ground, __nconn));
    }
  }
  return *this;
}


template <class _Tp,
         template <class __Ty, class __AllocT> class _SequenceCtr = std::vector,
         class _PtrAlloc = __VGTL_DEFAULT_ALLOCATOR(void *),
         class _Alloc = __VGTL_DEFAULT_ALLOCATOR(_Tp) >
class dgraph : public __DG<_Tp, _SequenceCtr<void*, _PtrAlloc>,
                        typename _SequenceCtr<void*, _PtrAlloc>::iterator,
                        typename _SequenceCtr<void*, _PtrAlloc>::const_iterator,
                        typename _SequenceCtr<void*, _PtrAlloc>::iterator,
                        _Alloc>
{
private:
  typedef typename _SequenceCtr<void*, _PtrAlloc>::iterator ___cit;
  typedef __DG<_Tp,_SequenceCtr<void*, _PtrAlloc>,
               typename _SequenceCtr<void*, _PtrAlloc>::iterator,
               typename _SequenceCtr<void*, _PtrAlloc>::const_iterator,
               typename _SequenceCtr<void*, _PtrAlloc>::iterator,
               _Alloc>  _Base;
protected:
  typedef dgraph<_Tp,_SequenceCtr,_PtrAlloc,_Alloc> _Self;
  typedef typename _Base::allocator_type allocator_type;
  typedef typename _Base::_RV_DG _RV_DG;
  typedef typename _Base::_Node _Node;

  typedef typename _Base::container_iterator container_iterator;

  typedef typename _Base::erased_part erased_part;

public:
  typedef typename _Base::walker walker;
  typedef typename _Base::const_walker const_walker;
  typedef typename _Base::children_iterator children_iterator;
  typedef typename _Base::parents_iterator parents_iterator;
  typedef typename _Base::parents_const_iterator parents_const_iterator;
  typedef typename _Base::children_const_iterator children_const_iterator;
  
public:
  explicit dgraph(const allocator_type& __a = allocator_type()) : _Base(__a) {} 
  
  dgraph(const _Self& __dg) : _Base(__dg) {}
  
  dgraph(const erased_part& __ep, const allocator_type& __a = allocator_type())
                            : _Base(__a)
    {
      this->_C_ground = __ep.first.first;
      this->_C_sky = __ep.first.second;
    }
  
  // destructor is automatic

  void clear() { _Base::clear(); }
  
  walker between(const walker& __parent, const children_iterator& __cit,
                      const walker& __child, const parents_iterator& __pit,
                      const _Tp& __x)
    { 
      return insert_in_graph(__x, __parent, __child, __cit, __pit);
    }


  walker split(const walker& __parent, const children_iterator& __ch_it,
              const walker& __child, const parents_iterator& __pa_it,
              const _Tp& __x)
    {
      container_iterator __cit;
      
      walker __rv = between(__parent, __ch_it, __child, __pa_it, __x);

      __cit = __parent._C_w_cur->get_childentry_iterator((void*)__child._C_w_cur);
      if(__cit != __parent._C_w_cur->_C_children.end())
        __parent._C_w_cur->_C_children.erase(__cit);
      __cit = __child._C_w_cur->get_parententry_iterator((void*)__parent._C_w_cur);
      if(__cit != __child._C_w_cur->_C_parents.end())
        __child._C_w_cur->_C_parents.erase(__cit);
      return __rv;
    }
  
  
  walker between_back(const walker& __parent, const walker& __child,
                      const _Tp& __x)
    { 
      return insert_in_graph(__x, __parent, __child,
          __parent._C_w_cur->_C_children.end(),
          __child._C_w_cur->_C_parents.end());
    }

  
  walker split_back(const walker& __parent,
              const walker& __child, const _Tp& __x)
    {
      container_iterator __cit;
      
      __cit = __parent._C_w_cur->get_childentry_iterator((void*)__child._C_w_cur);
      if(__cit != __parent._C_w_cur->_C_children.end())
        __parent._C_w_cur->_C_children.erase(__cit);
      __cit = __child._C_w_cur->get_parententry_iterator((void*)__parent._C_w_cur);
      if(__cit != __child._C_w_cur->_C_parents.end())
        __child._C_w_cur->_C_parents.erase(__cit);
      return between_back(__parent, __child, __x);
    }
  
  walker between_front(const walker& __parent, const walker& __child,
                      const _Tp& __x)
    { 
      return insert_in_graph(__x, __parent, __child,
          __parent._C_w_cur->_C_children.begin(),
          __child._C_w_cur->_C_parents.begin());
    }


  walker split_front(const walker& __parent,
              const walker& __child, const _Tp& __x)
    {
      container_iterator __cit;
      
      __cit = __parent._C_w_cur->get_childentry_iterator((void*)__child._C_w_cur);
      if(__cit != __parent._C_w_cur->_C_children.end())
        __parent._C_w_cur->_C_children.erase(__cit);
      __cit = __child._C_w_cur->get_parententry_iterator((void*)__parent._C_w_cur);
      if(__cit != __child._C_w_cur->_C_parents.end())
        __child._C_w_cur->_C_parents.erase(__cit);
      return between_front(__parent, __child, __x);
    }
  

#ifdef __VGTL_MEMBER_TEMPLATES
  template <template <class __Tp, class __AllocTp> class __SequenceCtr1,
            template <class __Tp, class __AllocTp> class __SequenceCtr2,
            class _Allocator1, class _Allocator2>
  walker between(const __SequenceCtr1<walker,_Allocator1>& __parents,
                 const __SequenceCtr2<walker,_Allocator2>& __children,
                 const _Tp& __x)
    { 
      typename __SequenceCtr1<walker,_Allocator1>::iterator __wpit;
      typename __SequenceCtr2<walker,_Allocator2>::iterator __wcit;
      _Node* __tmp = _C_create_node(__x);
      walker __help(__tmp);

      if(__parents.empty() || __children.empty())
        return;
      __wpit = __parents.begin();
      __wcit = __children.begin();
      insert_node_in_graph(__tmp, *__wpit, *__wcit,
          (*__wpit)._C_w_cur->_C_children.end(),
          (*__wcit)._C_w_cur->_C_parents.end());
      for(++__wpit; __wpit != __parents.end(); ++__wpit)
        add_edge(*__wpit, __help, (*__wpit)._C_w_cur->_C_children.end(),
                 __tmp->_C_parents.end());
      for(++__wcit; __wcit != __children.end(); ++__wcit)
        add_edge(__help, *__wcit, __tmp->_C_children.end(),
                 (*__wcit)._C_w_cur->_C_parents.end());
      return __help;
    }

  template <template <class __Tp, class __AllocTp> class __SequenceCtr1,
            template <class __Tp, class __AllocTp> class __SequenceCtr2,
            class _Allocator1, class _Allocator2>
  void split(const __SequenceCtr1<walker,_Allocator1>& __parents,
             const __SequenceCtr2<walker,_Allocator2>& __children,
             const _Tp& __x)
    {
      container_iterator __cit;
      typename __SequenceCtr1<walker,_Allocator1>::const_iterator __pnt;
      typename __SequenceCtr2<walker,_Allocator2>::const_iterator __cld;
      
      for(__cld = __children.begin(); __cld != __children.end(); ++__cld)
        for(__pnt = __parents.begin(); __pnt != __parents.end(); ++__pnt)
        {
          __cit = (*__pnt)._C_w_cur->get_childentry_iterator((void*)(*__cld)._C_w_cur);
          if(__cit != (*__pnt)._C_w_cur->_C_children.end())
            (*__pnt)._C_w_cur->_C_children.erase(__cit);
          __cit = (*__cld)._C_w_cur->get_parententry_iterator((void*)(*__pnt)._C_w_cur);
          if(__cit != (*__cld)._C_w_cur->_C_parents.end())
            (*__cld)._C_w_cur->_C_parents.erase(__cit);
        }
      between(__parents, __children, __x);
    }
#endif /* __VGTL_MEMBER_TEMPLATES */
  
  void insert_subgraph(_Self& __subgraph, const walker& __parent,
                       const children_iterator& __ch_it, const walker& __child,
                       const parents_iterator& __pa_it)
    {
      insert_subgraph(__subgraph, __parent, __child, __ch_it, __pa_it);
    }
  
  void insert_back_subgraph(_Self& __subgraph, const walker& __parent,
                       const walker& __child)
    {
      insert_subgraph(__subgraph, __parent, __child,
          __parent._C_w_cur->_C_children.end(),
          __child._C_w_cur->_C_parents.end());
    }
 
 
  void insert_front_subgraph(_Self& __subgraph, const walker& __parent,
                       const walker& __child)
    {
      insert_subgraph(__subgraph, __parent, __child,
          __parent._C_w_cur->_C_children.begin(),
          __child._C_w_cur->_C_parents.begin());
    }

  //here the two graphs are clubbed with the previous edges of the original graph being conserved 
#ifdef __VGTL_MEMBER_TEMPLATES
  // this is NOT YET DEFINED
#if 0
  template <template <class __Tp, class __AllocTp> class __SequenceCtr1,
            template <class __Tp, class __AllocTp> class __SequenceCtr2,
            class _Allocator1, class _Allocator2>
  void insert_subgraph(_Self& __subgraph,
                       const __SequenceCtr1<walker,_Allocator1>& __parents,
                       const __SequenceCtr2<walker,_Allocator2>& __children)
  {
    insert_subgraph(__subgraph, __parents, __children);
  }
#endif // 0
#endif /* __VGTL_MEMBER_TEMPLATES */
 
  void add_edge(const walker& __parent, const children_iterator& __ch_it,
                const walker& __child, const parents_iterator& __pa_it)
      {
        _Base::add_edge(__parent, __child, __ch_it, __pa_it);
      }

  void add_edge_back(const walker& __parent, const walker& __child)
      {
        add_edge(__parent, __parent._C_w_cur->_C_children.end(), __child,
                 __child._C_w_cur->_C_parents.end());
      }

  void add_edge_front(const walker& __parent, const walker& __child)
      {
        add_edge(__parent, __parent._C_w_cur->_C_children.begin(), __child,
                 __child._C_w_cur->_C_parents.begin());
      }

  // remove_edge is inherited
  
#ifdef __VGTL_MEMBER_TEMPLATES

  template <template <class __Tp, class __AllocTp> class __SequenceCtr,
            class _Allocator>
  walker between(const walker& __parent, const children_iterator& __cit,
                        const __SequenceCtr<walker,_Allocator>& __children,
                        const _Tp& __x)
  {
    return insert_in_graph(__x, __parent, __cit, __children);
  }

  template <template <class __Tp, class __AllocTp> class __SequenceCtr,
            class _Allocator>
  walker split(const walker& __parent, const children_iterator& __ch_it,
                const __SequenceCtr<walker,_Allocator>& __children,
                const _Tp& __x)
  {
    container_iterator __cit;
    typename __SequenceCtr<walker,_Allocator>::const_iterator __cld;
    walker __rv = between(__parent, __ch_it, __children, __x);
    
    for(__cld = __children.begin(); __cld != __children.end(); ++__cld)
    {
      __cit = __parent._C_w_cur->get_childentry_iterator((void*)(*__cld)._C_w_cur);
      if(__cit != __parent._C_w_cur->_C_children.end())
        __parent._C_w_cur->_C_children.erase(__cit);
      __cit = (*__cld)._C_w_cur->get_parententry_iterator((void*)__parent._C_w_cur);
      if(__cit != (*__cld)._C_w_cur->_C_parents.end())
        (*__cld)._C_w_cur->_C_parents.erase(__cit);
    }
    return __rv;
  }

  template <template <class __Tp, class __AllocTp> class __SequenceCtr,
            class _Allocator>
  walker split_back(const walker& __parent,
                    const __SequenceCtr<walker, _Allocator>& __children,
                    const _Tp& __x)
  {
    return split(__parent, __parent._C_w_cur->_C_children.end(), __children,
                  __x);
  }

  template <template <class __Tp, class __AllocTp> class __SequenceCtr,
            class _Allocator>
  walker between_back(const walker& __parent,
                      const __SequenceCtr<walker,_Allocator>& __children,
                      const _Tp& __x)
  {
    return between(__parent, __parent._C_w_cur->_C_children.end(),
                          __children, __x);
  }

  template <template <class __Tp, class __AllocTp> class __SequenceCtr,
            class _Allocator>
  walker split_front(const walker& __parent,
                    const __SequenceCtr<walker,_Allocator>& __children,
                    const _Tp& __x)
  {
    return split(__parent, __parent._C_w_cur->_C_children.begin(), __children,
                  __x);
  }

  template <template <class __Tp, class __AllocTp> class __SequenceCtr,
            class _Allocator>
  walker between_front(const walker& __parent,
                            const __SequenceCtr<walker,_Allocator>& __children,
                            const _Tp& __x)
  {
    return between(__parent, __parent._C_w_cur->_C_children.begin(),
                          __children, __x);
  }


  template <template <class __Tp, class __AllocTp> class __SequenceCtr,
            class _Allocator>
  walker between(const __SequenceCtr<walker,_Allocator>& __parents,
                        const walker& __child, const parents_iterator& __pit,
                        const _Tp& __x)
  {
    return insert_in_graph(__x, __parents, __child, __pit);
  }

  template <template <class __Tp, class __AllocTp> class __SequenceCtr,
            class _Allocator>
  walker split(const __SequenceCtr<walker,_Allocator>& __parents,
                const walker& __child, const parents_iterator& __pr_it,
                const _Tp& __x)
  {
    container_iterator __cit;
    typename __SequenceCtr<walker,_Allocator>::iterator __pnt;
    walker __rv = between(__parents, __child, __pr_it, __x);
    
    for(__pnt = __parents.begin(); __pnt != __parents.end(); ++__pnt)
    {
      __cit = __child._C_w_cur->get_parententry_iterator((void*)(*__pnt));
      if(__cit != __child._C_w_cur->_C_parents.end())
        __child._C_w_cur->_C_parents.erase(__cit);
      __cit = (*__pnt)._C_w_cur->get_childentry_iterator((void*)__child);
      if(__cit != (*__pnt)._C_w_cur->_C_children.end())
        (*__pnt)._C_w_cur->_C_children.erase(__cit);
    }
    return __rv;
  }

  template <template <class __Tp, class __AllocTp> class __SequenceCtr,
            class _Allocator>
  walker split_back(const __SequenceCtr<walker,_Allocator>& __parents, const walker& __child, 
              const _Tp& __x)
  {
    return split(__parents, __child, __child._C_w_cur->_C_parents.end(),
                  __x);
  }

  template <template <class __Tp, class __AllocTp> class __SequenceCtr,
            class _Allocator>
  walker between_back(const __SequenceCtr<walker,_Allocator>& __parents,
                      const walker& __child, const _Tp& __x)
  {
    return between(__parents, __child,
                          __child._C_w_cur->_C_children.end(), __x);
  }

  template <template <class __Tp, class __AllocTp> class __SequenceCtr,
            class _Allocator>
  walker split_front(const __SequenceCtr<walker,_Allocator>& __parents,
                    const walker& __child, const _Tp& __x)
  {
    return split(__parents, __child, __child._C_w_cur->_C_parents.begin(),
                  __x);
  }

  template <template <class __Tp, class __AllocTp> class __SequenceCtr,
            class _Allocator>
  walker between_front(const __SequenceCtr<walker,_Allocator>& __parents,
                            const walker& __child, const _Tp& __x)
  {
    return between(__parents, __child,
                          __child._C_w_cur->_C_children.begin(), __x);
  }
#endif /* __VGTL_MEMBER_TEMPLATES */

  _Self& operator=(const _RV_DG& __rl)
  {
    this->_C_ground = __rl.first;
    this->_C_sky = __rl.second;
    return *this;
  }

  _Self& operator=(const erased_part& __ep)
  {
    this->_C_ground = __ep.first.first;
    this->_C_sky = __ep.first.second;
    return *this;
  }
};







// this class produces a directed graph with additional acyclicity checks.

template <class _Tp,
          template <class __Ty, class __AllocT> class _SequenceCtr = std::vector,
          class _PtrAlloc = __VGTL_DEFAULT_ALLOCATOR(void *),
          class _Alloc = __VGTL_DEFAULT_ALLOCATOR(_Tp) >
class dag : public dgraph<_Tp, _SequenceCtr, _PtrAlloc, _Alloc>
{
protected:
  typedef dag<_Tp,_SequenceCtr,_PtrAlloc,_Alloc> _Self;
  typedef dgraph<_Tp, _SequenceCtr, _PtrAlloc, _Alloc> _Base;

  typedef typename _Base::allocator_type allocator_type;
  typedef typename _Base::_RV_DG _RV_DG;
  typedef typename _Base::_Node _Node;

  typedef typename _Base::container_iterator container_iterator;

public:
  typedef typename _Base::walker walker;
  typedef typename _Base::const_walker const_walker;
  typedef typename _Base::children_iterator children_iterator;
  typedef typename _Base::parents_iterator parents_iterator;
  typedef typename _Base::children_const_iterator children_const_iterator;
  typedef typename _Base::parents_const_iterator parents_const_iterator;

  typedef typename _Base::erased_part erased_part;
  
public:
  explicit dag(const allocator_type& __a = allocator_type()) : _Base(__a) {}

  dag(const _Self& __dag) : _Base(__dag) {}

  // destructor automatic
  
  // this should be rewritten to ensure acyclicity
  dag(const _Base& __dag) : _Base(__dag)
  {
    if(!check_acyclicity(this->ground(), this->sky()))
    // if the graph is not acyclic, get rid of it
      this->clear();
  }

  dag(const erased_part& __ep) : _Base(__ep)
  {
    if(!check_acyclicity(this->ground(), this->sky()))
    // if the graph is not acyclic, get rid of it
      this->clear();
  }
#if 0
  void add_edge(const walker& __parent, const walker& __child)
  {
  }

  // also all splits....
#endif

private:
  // APPROPRIATE CALLS FOR THESE FUNCTIONS HAVE TO BE ADDED
  bool check_edge(const walker& __parent, const walker& __child)
  { // TODO this should check, whether one added edge does destroys acyclicity
    return true;
  }

public:
  bool check_acyclicity(const walker& __parent, const walker& __child)
  { // TODO this should check, whether a directed graph is acyclic
    return true;
  }

#if 0
#ifdef __VGTL_MEMBER_TEMPLATES
  template <template <class __Tp, class __AllocTp> class __SequenceCtr,
            class _Allocator>
  void check_edges(const _SequenceCtr<std::pair<walker,walker>,_Allocator >& __edges)
  {
  }
#endif /* __VGTL_MEMBER_TEMPLATES */
#endif
  
  _Self& operator=(const _RV_DG& __rl)
  {
    this->_C_ground = __rl.first;
    this->_C_sky = __rl.second;
    return *this;
  }

  _Self& operator=(const erased_part& __ep)
  {
    this->_C_ground = __ep.first.first;
    this->_C_sky = __ep.first.second;
    return *this;
  }
};



#if 0


template <class _Tp,
          template <class __Key, class __Ty, class __Compare, class __AllocT> class _AssocCtr = std::multimap,
          class _Key = std::string,
          class _Compare = less<_Key>,
          class _PtrAlloc = __VGTL_DEFAULT_ALLOCATOR(void *),
          class _Alloc = __VGTL_DEFAULT_ALLOCATOR(_Tp) >
class ldgraph : public __DG<_Tp, _AssocCtr<_Key, void*, _Compare, _PtrAlloc>,
                            pair_adaptor<typename _AssocCtr<_Key, void*,
                                         _Compare, _PtrAlloc>::iterator>,
                            _Key, _Alloc>
{
protected:
  typedef ldgraph<_Tp,_AssocCtr,_Key,_Compare,_PtrAlloc,_Alloc> _Self;
  
public:
  _Self& operator=(_Node* __x)
  {
    this->_C_node = __x;
    return *this;
  }

  // NOT YET IMPLEMENTED  
};

template <class _Tp,
          template <class __Key, class __Ty, class __Compare, class __AllocT> class _AssocCtr = std::multimap,
          class _Key = std::string,
          class _Compare = less<_Key>,
          class _PtrAlloc = __VGTL_DEFAULT_ALLOCATOR(void *),
          class _Alloc = __VGTL_DEFAULT_ALLOCATOR(_Tp) >
class ldag : public ldgraph<_Tp, _AssocCtr, _Key, _Compare, _PtrAlloc, _Alloc>
{
protected:
  typedef ldag<_Tp,_AssocCtr,_Key,_Compare,_PtrAlloc,_Alloc> _Self;
  typedef ldgraph<_Tp,_AssocCtr,_Key,_Compare,_PtrAlloc,_Alloc> _Base;
  
public:
  explicit ldag(const allocator_type& __a = allocator_type()) : _Base(__a) {}

  explicit ldag() : _Base(allocator_type()) {}

  ldag(const _Self& __dag) : _Base(__dag) {}

  // destructor automatic
  
  // this should be rewritten to ensure acyclicity
#if 0
  void add_edge(const walker& __parent, const walker& __child)
  {
  }

  // also all splits....

private:
  void check_edge(const walker& __parent, const walker& __child)
  {
  }

#ifdef __VGTL_MEMBER_TEMPLATES
  template <template <class __Tp, class __AllocTp> class __SequenceCtr,
            class _Allocator>
  void check_edges(const _SequenceCtr<std::pair<walker,walker>,_Allocator >& __edges)
  {
  }
#endif /* __VGTL_MEMBER_TEMPLATES */
#endif
  
  _Self& operator=(const _RV_DG& __rl)
  {
    this->_C_ground = __rl.first;
    this->_C_sky = __rl.second;
    return *this;
  }
};
#endif

// this comment explains the walker class after replacing
// the default templates and the intermediate classes
//
// A walker is a generalization of a pointer. It points to the
// data of graph nodes (It uses as the same amount of memory as a
// pointer). The only difference between a walker and a pointer is
// that there are different methods for changing the walker to point
// to some other node.
// (Mathematically it is like the difference between a partial order
// (the DAG) and a linear order (the pointer). If a pointer points to
// something ++ goes to the next higher array element and -- goes to
// the next smaller array element. For a walker >> goes to one of the
// next smaller elements and << goes to one of the next bigger elements,
// since they are no longer unique in a partial order, a choice has to
// be made which of them should be taken.)
//
// template <class _Tp>
// class dag_walker
// {
//   // some type definitions
// private:
//   typedef dag_walker<_Tp> _Self;
// 
// public:
//   typedef _Tp value_type;
//   typedef _Tp* pointer;
//   typedef _Tp& reference;
//
// private:
//   typedef std::vector<void *>::iterator _Ctr_iterator;
//
// public:
//   typedef _Ctr_iterator children_iterator;
//   typedef _Ctr_iterator parents_iterator;
//
// private:
//   typedef dag_node<_Tp> _Node;
//
// public:
//   typedef _Node node_type;
//   typedef size_t size_type;
//
// protected:
//   // this is the pointer to the current node!
//   _Node* _C_w_cur;
//
// public:
//   // constructors and destructor
//   dag_walker();
//   dag_walker(_Node* __x);          // points to *__x afterwards
//   dag_walker(const walker& __x);   // copy constructor
//   ~dag_walker();
//
//   // assignment
//   _Self& operator=(const _Self& __x);
//   _Self& operator=(const _Node& __n);
//
//   // dereference (to the node data, i.e. what we call node)
//   reference operator*() const { return (*_C_w_cur)._C_data; }
//   pointer operator->() const { return &(operator*()); }
//
//   // access to the full node - this should not be used outside
//   // GTL, since it can be used to corrupt the structure of the DAG
//   const _Node* node();
//
//   // other enhanced methods for gaining info on nodes
//   size_type n_children();   // number of children
//   size_type n_parents();    // number of parents
//
//   bool is_root();           // points to a root node
//   bool is_leaf();           // points to a leaf node
//
//   bool is_ground();         // we are at the ground (i.e. below all roots)
//   bool is_sky();            // we are in the sky (i.e. above all leafs)
//
//   // these can be used to iterate through all children (parents) and
//   // to use the operators << and >>
//   children_iterator child_begin(); // first child
//   children_iterator child_end();   // beyond last child
//
//   parents_iterator parent_begin(); // first parent
//   parents_iterator parent_end();   // beyond last parent
//
//   // operators for walkers
//   // comparison
//   bool operator==(const _Self& __x) const {}
//   bool operator!=(const _Self& __x) const {}
//
//   // navigation (i.e. change to another element)
//   // these are the replacement for the ++ and -- operators
//   // for pointers.
//   // go up to parent __i
//   _Self operator<<(parents_iterator __i);
//   // go down to child __i
//   _Self operator>>(children_iterator __i);
//
//   // and the same combined with assignment
//   _Self& operator<<=(parents_iterator __i);
//   _Self& operator>>=(children_iterator __i);
// }

// this comment explains, how the dag class looks like after
// replacing the default templates and the intermediate classes
//
// template <class _Tp>
// class dag : dag_base<_Tp>   // this is from vgtl_dagbase.h
// {
// private:
//   typedef dag<_Tp> _Self;
//   typedef dag_base<_Tp> _Base;
//   typedef dag_walker<_Tp> walker;
//
//   // constructors, destructor
//   dag();
//   dag(const _Self& __dag);
//   ~dag();
//
//   // assignment
//   _Self& operator=(const _Self& __x);
//
//   // comparison
//   friend bool operator== (const _Self& __x, const _Self& __y);
//
//   // clear graph
//   void clear();
//
//   // insert a node N between a (some) parent(s) and a (some) child(ren)
//   // such that Ns parents is/are the given parent(s) and Ns children is/are
//   // the given child(ren). The return value is always a walker pointing
//   // to the new node.
//
//   // here the exact point of insertion can be chosen
//   walker between(const walker& __parent, const children_iterator& __cit,
//                  const walker& __child, const parents_iterator& __pit,
//                  const _Tp& __x);
//
//   // here the new edge is appended to the list of edges in the parents
//   // and children vectors
//   walker between_back(const walker& __parent, const walker& __child,
//                       const _Tp& __x);
//
//   // here the new edge is prepended to the list of edges in the parents
//   // and children vectors
//   walker between_front(const walker& __parent, const walker& __child,
//                        const _Tp& __x);
//
//   // insert between a list of parents and children. The new edges are
//   // appended
//   walker between(const __SequenceCtr<walker>& __parents,
//                  const __SequenceCtr<walker>& __children,
//                  const _Tp& __x);
//
//   // insert between one parent and a list of children
//   walker between(const walker& __parent, const children_iterator& __cit,
//                  const __SequenceCtr<walker>& __children,
//                  const _Tp& __x);
//   walker between_back(const walker& __parent,
//                       const __SequenceCtr<walker>& __children,
//                       const _Tp& __x);
//   walker between_front(const walker& __parent,
//                        const __SequenceCtr<walker>& __children,
//                        const _Tp& __x);
//
//   // insert between one child and many parents
//   walker between(const __SequenceCtr<walker>& __parents,
//                  const walker& __child, const parents_iterator& __pit,
//                  const _Tp& __x);
//   walker between_back(const __SequenceCtr<walker>& __parents,
//                       const walker& __child, const _Tp& __x);
//   walker between_front(const __SequenceCtr<walker>& __parents,
//                        const walker& __child, const _Tp& __x);
//
//
//   // insert a node N between a (some) parent(s) and a (some) child(ren)
//   // if parent(s) and child(ren) are connected the edges from parent to
//   // children are split into edges from parent(s) to N and edges from N
//   // to child(ren)
//   //
//   // here the exact point of insertion can be chosen
//   walker split(const walker& __parent, const children_iterator& __cit,
//                const walker& __child, const parents_iterator& __pit,
//                const _Tp& __x);
//
//   // here the new edge is appended to the list of edges in the parents
//   // and children vectors
//   walker split_back(const walker& __parent, const walker& __child,
//                    const _Tp& __x);
//
//   // here the new edge is prepended to the list of edges in the parents
//   // and children vectors
//   walker split_front(const walker& __parent, const walker& __child,
//                      const _Tp& __x);
//
//   // insert between a list of parents and children. The new edges are
//   // appended
//   walker split(const __SequenceCtr<walker>& __parents,
//                const __SequenceCtr<walker>& __children,
//                const _Tp& __x);
//
//   // insert between one parent and a list of children
//   walker split(const walker& __parent, const children_iterator& __cit,
//                const __SequenceCtr<walker>& __children,
//                const _Tp& __x);
//   walker split_back(const walker& __parent,
//                     const __SequenceCtr<walker>& __children,
//                     const _Tp& __x);
//   walker split_front(const walker& __parent,
//                      const __SequenceCtr<walker>& __children,
//                      const _Tp& __x);
//
//   // insert between one child and many parents
//   walker split(const __SequenceCtr<walker>& __parents,
//                const walker& __child, const parents_iterator& __pit,
//                const _Tp& __x);
//   walker split_back(const __SequenceCtr<walker>& __parents,
//                     const walker& __child, const _Tp& __x);
//   walker split_front(const __SequenceCtr<walker>& __parents,
//                      const walker& __child, const _Tp& __x);
//
//   
//   // insert a whole subgraph
//   void insert_subgraph(_Self& __subgraph,
//                        const std::vector<walker>& __parents.
//                        const std::vector<walker>& __children);
//
//   // add a single edge
//   // where you want in the lists
//   void add_edge(const walker& __parent, const children_iterator& __ch_it,
//                 const walker& __child, const parents_iterator& __pa_it);
//   // always in the end
//   void add_edge_back(const walker& __parent, const walker& __child);
//   // always in the front
//   void add_edge_front(const walker& __parent, const walker& __child);
//
//   // remove an edge
//   void remove_edge(const walker& __parent, const walker& __child);
//
//   // erase a node from the graph
//   void erase(const walker& __position);
//
//   // erase a child node if it is a leaf
//   bool erase_child(const walker& __position, const children_iterator& __It);
//  
//   // erase a parent node if it is a root
//   bool erase_parent(const walker& __position, const parents_iterator& __It);
//
//   // and there are not properly implemented functions for removing
//   // whole subgraphs
// }

__VGTL_END_NAMESPACE

#endif // __VGTL_DAG_H_ 

---