vgtl_dagbase.h

Go to the documentation of this file.

// Directed Graph base class implementation -*- C++ -*-

// $Id: vgtl_dagbase.h 347 2008-02-06 15:20:01Z schilly $
// 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_DAGBASE_H_
#define __VGTL_DAGBASE_H_

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

__VGTL_BEGIN_NAMESPACE


template <class _Tp, class _Ctr, class _Iterator>
class _DG_node
{
private:
  typedef void* _Void_pointer;
  typedef _Iterator _Ctr_iterator;
  typedef _DG_node<_Tp,_Ctr,_Iterator> _Self;

public:
  _Tp _C_data;
  _Ctr _C_parents;
  _Ctr _C_children;
  int _C_visited;

  _DG_node() {
               _C_visited=0;
               __VGTL_TRY {
                    _VGTL_Construct_1(&_C_data);
                    _VGTL_Construct_1(&_C_children);
                    _VGTL_Construct_1(&_C_parents);
               }
               __VGTL_UNWIND( ;);
             }

  ~_DG_node() {
                _VGTL_Destroy(&_C_data);
                _VGTL_Destroy(&_C_children);
                _VGTL_Destroy(&_C_parents);
              }

  void clear_children()
        { _C_children.erase(_C_children.begin(), _C_children.end()); }
  void clear_parents()
        { _C_parents.erase(_C_parents.begin(), _C_parents.end()); }

  _Ctr_iterator get_childentry_iterator(const _Void_pointer __p)
        { _Ctr_iterator __tmp;
          _Ctr_iterator __end = _C_children.end();
          for(__tmp = _C_children.begin(); __tmp != __end; ++__tmp)
            if(*__tmp == __p) break;
          return __tmp;
        }

  _Ctr_iterator get_parententry_iterator(const _Void_pointer __p)
        { _Ctr_iterator __tmp;
          _Ctr_iterator __end = _C_parents.end();
          for(__tmp = _C_parents.begin(); __tmp != __end; ++__tmp)
            if(*__tmp == __p) break;
          return __tmp;
        }


#ifdef __VGTL_MEMBER_TEMPLATES

  template <class _Output_Iterator>
  void add_all_children(_Output_Iterator fi, _Self* _parent);

  
  template <class _Output_Iterator>
  void add_all_parents(_Output_Iterator fi, _Self* _child);

  template <class Compare>
  void sort_child_edges(_Ctr_iterator first, _Ctr_iterator last, Compare comp)
  {
    sort(first, last, _G_compare_adaptor<Compare, _Self>(comp));
  }
  
  template <class Compare>
  void sort_parent_edges(_Ctr_iterator first, _Ctr_iterator last, Compare comp)
  {
    sort(first, last, _G_compare_adaptor<Compare, _Self>(comp));
  }
#endif /* __VGTL_MEMBER_TEMPLATES */
};

#ifdef __VGTL_MEMBER_TEMPLATES
template <class _Tp, class _Ctr, class _Iterator>
template <class _Output_Iterator>
inline void  // implementation of add children
_DG_node<_Tp,_Ctr,_Iterator>::
        add_all_children(_Output_Iterator fi, _Self* _parent)
{ _Ctr_iterator it;
  for(it = _C_children.begin();
      it != _C_children.end();
      ++it)
  {
    *fi++ = *it;
    ((_Self*)*it)->_C_parents.insert(((_Self*)*it)->_C_parents.end(), _parent);
  }
};

template <class _Tp, class _Ctr, class _Iterator>
template <class _Output_Iterator>
inline void  // implementation of add parent
_DG_node<_Tp,_Ctr,_Iterator>::
        add_all_parents(_Output_Iterator fi, _Self* _child)
{ _Ctr_iterator it;
  for(it = _C_parents.begin();
      it != _C_parents.end();
      ++it)
  {
    *fi++ = *it;
    ((_Self*)*it)->_C_children.insert(((_Self*)*it)->_C_children.end(), _child);
  }
};
#endif /* __VGTL_MEMBER_TEMPLATES */

#if __VGTL_USE_STD_ALLOCATORS


template <class _Tp, class _Ctr, class _TI, class _Allocator, bool _IsStatic>
class _DG_alloc_base {
public:
  typedef typename std::_Alloc_traits<_Tp, _Allocator>::allocator_type
          allocator_type;
  allocator_type get_allocator() const { return _Node_allocator; }

  _DG_alloc_base(const allocator_type& __a) : _Node_allocator(__a) {}

protected:
  _DG_node<_Tp,_Ctr,_TI>* _C_get_node()
    { return _Node_allocator.allocate(1); }
  void _C_put_node(_DG_node<_Tp,_Ctr,_TI>* __p)
    { _Node_allocator.deallocate(__p, 1); }

protected:
  typename std::_Alloc_traits<_DG_node<_Tp,_Ctr,_TI>, _Allocator>::allocator_type
           _Node_allocator;

protected:
  _DG_node<_Tp,_Ctr,_TI>* _C_ground;
  _DG_node<_Tp,_Ctr,_TI>* _C_sky;
  int _C_mark;
};


template <class _Tp, class _Ctr, class _TI, class _Allocator>
class _DG_alloc_base<_Tp, _Ctr, _TI, _Allocator, true> {
public:
  typedef typename std::_Alloc_traits<_Tp, _Allocator>::allocator_type
          allocator_type;
  allocator_type get_allocator() const { return allocator_type(); }

  _DG_alloc_base(const allocator_type&) {}

protected:
  typedef typename std::_Alloc_traits<_DG_node<_Tp,_Ctr,_TI>, _Allocator>::_Alloc_type
          _Alloc_type;
  _DG_node<_Tp,_Ctr,_TI>* _C_get_node()
    { return _Alloc_type::allocate(1); }
  void _C_put_node(_DG_node<_Tp,_Ctr,_TI>* __p)
    { _Alloc_type::deallocate(__p, 1); }

protected:
  _DG_node<_Tp,_Ctr,_TI>* _C_ground;
  _DG_node<_Tp,_Ctr,_TI>* _C_sky;
  int _C_mark;
};



template <class _Tp, class _Ctr, class _Iterator, class _CIterator,
          class _Alloc>
class _DG_base
  : public _DG_alloc_base<_Tp, _Ctr, _Iterator, _Alloc,
                        std::_Alloc_traits<_Tp, _Alloc>::_S_instanceless>
{
public:
  typedef _DG_alloc_base<_Tp, _Ctr, _Iterator, _Alloc,
                        std::_Alloc_traits<_Tp, _Alloc>::_S_instanceless>
          _Base;
  typedef typename _Base::allocator_type allocator_type;

  typedef _Ctr container_type;
  typedef _Iterator children_iterator;
  typedef _CIterator children_const_iterator;
  typedef _Iterator parents_iterator;
  typedef _CIterator parents_const_iterator;
  

  _DG_base(const allocator_type& __a) : _Base(__a) {
    this->_C_ground = _C_get_node();
    this->_C_sky = _C_get_node();
    memset(this->_C_ground, 0, sizeof(*this->_C_ground));
    memset(this->_C_sky,    0, sizeof(*this->_C_sky));
    this->_C_mark = 0;
    __VGTL_TRY {
      _VGTL_Construct_1(&this->_C_ground->_C_children);
      _VGTL_Construct_1(&this->_C_ground->_C_parents);
      _VGTL_Construct_1(&this->_C_ground->_C_data);
      _VGTL_Construct_1(&this->_C_sky->_C_children);
      _VGTL_Construct_1(&this->_C_sky->_C_parents);
      _VGTL_Construct_1(&this->_C_sky->_C_data);
    }
    __VGTL_UNWIND(_C_put_node(this->_C_ground); _C_put_node(this->_C_sky));
    this->_C_ground->_C_children.push_back((void*)this->_C_sky);
    this->_C_sky->_C_parents.push_back((void*)this->_C_ground);
    this->_C_ground->_C_visited=0;
    this->_C_sky->_C_visited=0;
  }

  ~_DG_base() {
    clear();
    //_C_put_node(this->_C_ground);
    //_C_put_node(this->_C_sky);
  }

protected:
  void clear_graph(_DG_node<_Tp,_Ctr,_Iterator>* _node); 

public:
  void clear();
  void clear_children()
        { this->_C_ground->clear_children(); }
  void clear_parents()
        { this->_C_sky->clear_parents(); }

  template <class _Output_Iterator>
  void add_all_children(_Output_Iterator fi,
                        _DG_node<_Tp,_Ctr,_Iterator>* _parent);
  template <class _Output_Iterator>
  void add_all_parents(_Output_Iterator fi,
                        _DG_node<_Tp,_Ctr,_Iterator>* _child);
};
#else /* __VGTL_USE_STD_ALLOCATORS */



template <class _Tp, class _Ctr, class _Iterator, class _CIterator,
          class _Alloc>
class _DG_base
{
public:
  typedef _Alloc allocator_type;
  allocator_type get_allocator() const { return allocator_type(); }
  
  typedef _Ctr container_type;
  typedef _Iterator children_iterator;
  typedef _CIterator children_const_iterator;
  typedef _Iterator parents_iterator;
  typedef _CIterator parents_const_iterator;

  _DG_base(const allocator_type&) {
    this->_C_ground = _C_get_node();
    this->_C_sky = _C_get_node();
    memset(this->_C_ground, 0, sizeof(*this->_C_ground));
    memset(this->_C_sky,    0, sizeof(*this->_C_sky));
    this->_C_mark = 0;
    __VGTL_TRY {
      _VGTL_Construct_1(&this->_C_ground->_C_children);
      _VGTL_Construct_1(&this->_C_ground->_C_parents);
      _VGTL_Construct_1(&this->_C_ground->_C_data);
      _VGTL_Construct_1(&this->_C_sky->_C_children);
      _VGTL_Construct_1(&this->_C_sky->_C_parents);
      _VGTL_Construct_1(&this->_C_sky->_C_data);
    }
    __VGTL_UNWIND(_C_put_node(this->_C_ground); _C_put_node(this->_C_sky));
    this->_C_ground->_C_children.push_back((void*)this->_C_sky);
    this->_C_sky->_C_parents.push_back((void*)this->_C_ground);
    this->_C_ground->_C_visited=0;
    this->_C_sky->_C_visited=0;
  }
  ~_DG_base() {
    clear();
    //_C_put_node(this->_C_ground);
    //_C_put_node(this->_C_sky);
  }

protected:
  void clear_graph(_DG_node<_Tp,_Ctr,_Iterator>* _node); 

public:
  void clear();

protected:
  typedef std::allocator<_DG_node<_Tp,_Ctr,_Iterator> > _Alloc_type;
  _DG_node<_Tp,_Ctr,_Iterator>* _C_get_node()
    { return _Alloc_type().allocate(1); }
  void _C_put_node(_DG_node<_Tp,_Ctr,_Iterator>* __p)
    { _Alloc_type().deallocate(__p, 1); }

protected:
  _DG_node<_Tp,_Ctr,_Iterator>* _C_ground;
  _DG_node<_Tp,_Ctr,_Iterator>* _C_sky;
  int _C_mark;

  void clear_children()
     { this->_C_ground->clear_children(); }
  void clear_parents()
     { this->_C_sky->clear_parents(); }

  template <class _Output_Iterator>
  void add_all_children(_Output_Iterator fi,
                        _DG_node<_Tp,_Ctr,_Iterator>* _parent);
  template <class _Output_Iterator>
  void add_all_parents(_Output_Iterator fi,
                        _DG_node<_Tp,_Ctr,_Iterator>* _child);
};

#endif /* __VGTL_USE_STD_ALLOCATORS */

// get rid of the subtree
template <class _Tp, class _Ctr, class _Iterator, class _CIterator,
          class _Alloc>
void
_DG_base<_Tp,_Ctr,_Iterator,_CIterator,_Alloc>::clear_graph(
        _DG_node<_Tp,_Ctr,_Iterator>* _node) // implementation of clear graph
{
  _Ctr* chld = &_node->_C_children;
  _Iterator it;

  if(_node->_C_parents.size() <= 1)
  {
    // otherwise we will visit this node again later
    for(it = chld->begin(); it != chld->end(); ++it)
      clear_graph((_DG_node<_Tp,_Ctr,_Iterator>*)(*it));
    _node->_C_children.erase(_node->_C_children.begin(),
                             _node->_C_children.end());
  
    _VGTL_Destroy(&_node->_C_children);
    _VGTL_Destroy(&_node->_C_data);
  }
  if(_node->_C_parents.size() >= 1)
    _node->_C_parents.erase(_node->_C_parents.begin());
  if(_node->_C_parents.size() == 0)
  {
    _VGTL_Destroy(&_node->_C_parents);
    _C_put_node(_node);
  }
}

template <class _Tp, class _Ctr, class _Iterator, class _CIterator,
          class _Alloc>
template <class _Output_Iterator>
inline void
_DG_base<_Tp,_Ctr,_Iterator,_CIterator,_Alloc>::
        add_all_children(_Output_Iterator fi,
                        _DG_node<_Tp,_Ctr,_Iterator>* _parent)
{ this->_C_ground->add_all_children(fi, _parent); };

template <class _Tp, class _Ctr, class _Iterator, class _CIterator,
          class _Alloc>
template <class _Output_Iterator>
inline void
_DG_base<_Tp,_Ctr,_Iterator,_CIterator,_Alloc>::
        add_all_parents(_Output_Iterator fi,
                        _DG_node<_Tp,_Ctr,_Iterator>* _child)
{ this->_C_sky->add_all_parents(fi, _child); };

template <class _Tp, class _Ctr, class _Iterator, class _CIterator,
          class _Alloc>
void
_DG_base<_Tp,_Ctr,_Iterator,_CIterator,_Alloc>::clear()
{
  clear_graph(this->_C_ground);
  //this->_C_ground->clear_children();
  //this->_C_ground->clear_parents();
  //this->_C_sky->clear_parents();
  //this->_C_sky->clear_children();
}

#if 0
// this comment explains, how the node type of directed graphs is
// instantiated. 

template <class _Tp>
class dag_node : public _DG_node<_Tp, vector<void*>, vector<void*>::iterator>
{
}

// if we replace the templates above, we get
  
// template <class _Tp>
// class dag_node
// {
// private:
//   typedef _Ctr_iterator vector<void*>::iterator;
// 
// public:
//   _Tp _C_data;
//   vector<void *> _C_parents;
//   vector<void *> _C_children;
//   int _C_visited;
//
//   _DG_node();  // a constructor
//
//   // and methods
//
//   void clear_children();
//   void clear_parents();
//
//   _Ctr_iterator get_childentry_iterator(const void* __p);
//   _Ctr_iterator get_parententry_iterator(const void* __p);
//
//   // and template member functions for automatically updating
//   // parents and children
//
//   template <class _Output_Iterator>
//     void add_all_children(_Output_Iterator fi, dag_node<_Tp>* _parent);
//      
//   template <class _Output_Iterator>
//     void add_all_parents(_Output_Iterator fi, dag_node<_Tp>* _child);
// }


// here is how the dag_base class essentially looks like

template <class _Tp>
class dag_base
{
protected:
   dag_node<_Tp>* _C_ground;
   dag_node<_Tp>* _C_sky;
   int _C_mark;

public:
   dag_base();    // a constructor
   ~dag_base();   // a destructor

private:
   // and methods
   void clear_graph(dag_node<_Tp>* _node);

public:
   void clear();  // remove the whole DAG

   dag_node<_Tp>* _C_get_node();           // construct a new node
   void _C_put_node(dag_node<_Tp>* __p);   // destroy a node

protected:
   void clear_children();   // clear the children vector
   void clear_parents();    // clear the parents vector

   // template member functions for parent, children handling
   template <class _Output_Iterator>
   void add_all_children(_Output_Iterator fi, dag_node<_Tp>* _parent);
   void add_all_parents(_Output_Iterator fi, dag_node<_Tp>* _child);
}

#endif /* 0 */

__VGTL_END_NAMESPACE


#endif // __VGTL_DAGBASE_H_ 

---