vgtl_ldagbase.h

Go to the documentation of this file.

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

// $Id: vgtl_ldagbase.h 347 2008-02-06 15:20:01Z schilly $
// Copyright (C) 2001-2007 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_LDAGBASE_H_
#define __VGTL_LDAGBASE_H_

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

__VGTL_BEGIN_NAMESPACE


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

public:
  _Tp* _C_data;
  _Ctr _C_inedges;
  _Ctr _C_outedges;
  int _C_visited;

  _LDG_node() {
               _C_visited=0;
               __VGTL_TRY {
                    _C_data = new _Tp;
                    std::_Construct(&_C_inedges);
                    std::_Construct(&_C_outedges);
               }
               __VGTL_UNWIND( );
             }

  ~_LDG_node() {
                __VGTL_TRY {
                    std::_Destroy(&_C_inedges);
                    std::_Destroy(&_C_outedges);
                    delete _C_data;
                }
                __VGTL_UNWIND();
              }

  void clear_in_edges()
        { _C_inedges.erase(_C_inedges.begin(), _C_inedges.end()); }
  void clear_out_edges()
        { _C_outedges.erase(_C_outedges.begin(), _C_outedges.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_in_edges(_Ctr_iterator first, _Ctr_iterator last, Compare comp)
  {
    sort(first, last, _G_compare_adaptor<Compare, _Self>(comp));
  }
  
  template <class Compare>
  void sort_out_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
_LDG_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
_LDG_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 */


template <class _Te, class _TN>
class _LDG_edge
{
private:
  typedef void* _Void_pointer;
  typedef _Iterator _Ctr_iterator;
  typedef _LDG_edge<_Te,_TN> _Self;

public:
  _Te* _E_data;
  _TN* _E_snode;
  _TN* _E_tnode;

  _LDG_edge() {
               __VGTL_TRY {
                    _E_data = new _Te;
               }
               __VGTL_UNWIND( );
               _E_snode = NULL;
               _E_tnode = NULL;
             }

  ~_LDG_node() {
                __VGTL_TRY {
                    delete _E_data;
                }
                __VGTL_UNWIND();
              }

#ifdef __VGTL_MEMBER_TEMPLATES
#endif /* __VGTL_MEMBER_TEMPLATES */
  set_parent(_TN* p) { _E_pnode = p; }
  
  set_child(_TN* c) { _E_cnode = c; }
  
  set_edge(_TN* p, _TN* c) { set_parent(p); set_child(c); }

  _TN* source() { return _E_snode; }
  _TN* target() { return _E_tnode; }

  const _TN* source() const { return _E_snode; }
  const _TN* target() const { return _E_tnode; }
};

#ifdef __VGTL_MEMBER_TEMPLATES
#endif /* __VGTL_MEMBER_TEMPLATES */

#if __VGTL_USE_STD_ALLOCATORS


template <class _Tp, class _Ctr, class _TI, class _Te, class _NAllocator, 
          class _EAllocator, bool _IsStatic>
class _LDG_alloc_base {
public:
  typedef typename std::_Alloc_traits<_Tp, _NAllocator>::allocator_type
          node_allocator_type;
  node_allocator_type get_node_allocator() const { return _Node_allocator; }

  typedef typename std::_Alloc_traits<_Te, _EAllocator>::allocator_type
          edge_allocator_type;
  edge_allocator_type get_edge_allocator() const { return _Edge_allocator; }

  _LDG_alloc_base(const node_allocator_type& __na, const egde_allocator_type& __ea)
        : _Node_allocator(__na), _Edge_allocator(__ea) {}

private:
  typedef typename _LDG_node<_Tp,_Ctr,_TI> _Node;

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

  _LDG_edge<_Te,_Node>* _C_get_edge()
    { return _Node_allocator.allocate(1); }
  void _C_put_edge(_LDG_edge<_Te,_Node>* __p)
    { _Node_allocator.deallocate(__p, 1); }

protected:
  typename std::_Alloc_traits<_LDG_node<_Tp,_Ctr,_TI>, _NAllocator>::allocator_type
           _Node_allocator;
  typename std::_Alloc_traits<_LDG_node<_Te,_Tp>, _EAllocator>::allocator_type
           _Edge_allocator;

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


template <class _Tp, class _Ctr, class _TI, class _Te, class _NAllocator,
          class _EAllocator>
class _LDG_alloc_base<_Tp, _Ctr, _TI, _Te, _NAllocator, _EAllocator, true> {
public:
  typedef typename std::_Alloc_traits<_Tp, _NAllocator>::allocator_type
          node_allocator_type;
  node_allocator_type get_node_allocator() const { return node_allocator_type(); }

  typedef typename std::_Alloc_traits<_Te, _EAllocator>::allocator_type
          edge_allocator_type;
  edge_allocator_type get_edge_allocator() const { return edge_allocator_type(); }

  _LDG_alloc_base(const node_allocator_type&, const edge_allocator_type&) {}

private:
  typedef typename _LDG_node<_Tp,_Ctr,_TI> _Node;

protected:
  typedef typename std::_Alloc_traits<_LDG_node<_Tp,_Ctr,_TI>, _Allocator>::_Alloc_type
          _NAlloc_type;
  typedef typename std::_Alloc_traits<_LDG_edge<_Te,_Tp>, _Allocator>::_Alloc_type
          _EAlloc_type;

  _LDG_node<_Tp,_Ctr,_TI>* _C_get_node()
    { return _NAlloc_type::allocate(1); }
  void _C_put_node(_LDG_node<_Tp,_Ctr,_TI>* __p)
    { _NAlloc_type::deallocate(__p, 1); }

  _LDG_edge<_Te,_Node>* _C_get_edge()
    { return _EAlloc_type::allocate(1); }
  void _C_put_edge(_LDG_edge<_Te,_Node>* __p)
    { _EAlloc_type::deallocate(__p, 1); }

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



template <class _Tp, class _Ctr, class _Iterator, class _CIterator, class _Te,
          class _NAlloc, class _EAlloc>
class _LDG_base
  : public _LDG_alloc_base<_Tp, _Ctr, _Iterator, _Te, _NAlloc, _EAlloc,
                        std::_Alloc_traits<_Tp, _NAlloc>::_S_instanceless>
{
public:
  typedef _LDG_alloc_base<_Tp, _Ctr, _Iterator, _Te, _NAlloc, _EAlloc,
                        std::_Alloc_traits<_Tp, _NAlloc>::_S_instanceless>
          _Base;
  typedef typename _Base::node_allocator_type node_allocator_type;
  typedef typename _Base::edge_allocator_type edge_allocator_type;

  typedef _Ctr container_type;
  typedef _Iterator in_iterator;
  typedef _CIterator in_const_iterator;
  typedef _Iterator out_iterator;
  typedef _CIterator out_const_iterator;
  

  _LDG_base(const node_allocator_type& __a, const edge_allocator_type& __e)
         : _Base(__a, __e) {
    _Te* e;
    this->_C_mark = 0;
    __VGTL_TRY {
      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));
      std::_Construct(&this->_C_ground->_C_children);
      std::_Construct(&this->_C_ground->_C_parents);
      this->_C_ground->_C_data = new _Tp;
      std::_Construct(&this->_C_sky->_C_children);
      std::_Construct(&this->_C_sky->_C_parents);
      this->_C_sky->_C_data = new _Tp;
      e = _C_get_edge();
      e->_E_data = new _Te;
    }
    __VGTL_UNWIND(_C_put_node(this->_C_ground); _C_put_node(this->_C_sky);
                  _C_put_edge(e); )
    this->_C_ground->_C_children.push_back(e);
    this->_C_sky->_C_parents.push_back(e);
    e->set_edge(&this->_C_ground, &this->_C_sky);
    this->_C_ground->_C_visited=0;
    this->_C_sky->_C_visited=0;
  }

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

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

public:
  void clear();
  void clear_out_edges()
        { this->_C_ground->clear_out_edges(); }
  void clear_in_edges()
        { this->_C_sky->clear_in_edges(); }

  template <class _Output_Iterator>
  void add_all_out_edges(_Output_Iterator fi,
                        _LDG_node<_Tp,_Ctr,_Iterator>* _parent);
  template <class _Output_Iterator>
  void add_all_in_edges(_Output_Iterator fi,
                        _LDG_node<_Tp,_Ctr,_Iterator>* _child);
};
#else /* __VGTL_USE_STD_ALLOCATORS */



template <class _Tp, class _Ctr, class _Iterator, class _CIterator, class _Te,
          class _NAlloc, class _EAlloc>
class _LDG_base
{
public:
  typedef _NAlloc node_allocator_type;
  typedef _EAlloc edge_allocator_type;
  node_allocator_type get_node_allocator() const { return node_allocator_type(); }
  edge_allocator_type get_edge_allocator() const { return edge_allocator_type(); }
  
  typedef _Ctr container_type;
  typedef _Iterator out_iterator;
  typedef _CIterator out_const_iterator;
  typedef _Iterator in_iterator;
  typedef _CIterator in_const_iterator;

  _LDG_base(const node_allocator_type&, const edge_allocator_type&) {
    _Te* e;
    this->_C_mark = 0;
    __VGTL_TRY {
      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));
      std::_Construct(&this->_C_ground->_C_children);
      std::_Construct(&this->_C_ground->_C_parents);
      this->_C_ground->_C_data = new _Tp;
      std::_Construct(&this->_C_sky->_C_children);
      std::_Construct(&this->_C_sky->_C_parents);
      this->_C_sky->_C_data = new _Tp;
      e = _C_get_edge();
      e->_E_data = new _Te;
    }
    __VGTL_UNWIND(_C_put_node(this->_C_ground); _C_put_node(this->_C_sky);
                  _C_put_edge(e); )
    this->_C_ground->_C_children.push_back(e);
    this->_C_sky->_C_parents.push_back(e);
    e->set_edge(&this->_C_ground, &this->_C_sky);
    this->_C_ground->_C_visited=0;
    this->_C_sky->_C_visited=0;
  }
  ~_LDG_base() {
    clear();
    //_C_put_node(this->_C_ground);
    //_C_put_node(this->_C_sky);
  }

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

private:
  typedef typename _LDG_node<_Tp,_Ctr,_Iterator> _Node;

public:
  void clear();

protected:
  typedef std::allocator<_LDG_node<_Tp,_Ctr,_Iterator> > _NAlloc_type;
  typedef std::allocator<_LDG_edge<_Te,_Node> > _EAlloc_type;
  _LDG_node<_Tp,_Ctr,_Iterator>* _C_get_node()
    { return _NAlloc_type().allocate(1); }
  void _C_put_node(_LDG_node<_Tp,_Ctr,_Iterator>* __p)
    { _NAlloc_type().deallocate(__p, 1); }

  _LDG_edge<_Te,_Node>* _C_get_edge()
    { return _EAlloc_type().allocate(1); }
  void _C_put_edge(_LDG_edge<_Te,_Node>* __p)
    { _EAlloc_type().deallocate(__p, 1); }

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

  void clear_out_edges()
     { this->_C_ground->clear_out_edges(); }
  void clear_in_edges()
     { this->_C_sky->clear_in_edges(); }

  template <class _Output_Iterator>
  void add_all_out_edges(_Output_Iterator fi,
                        _LDG_node<_Tp,_Ctr,_Iterator>* _parent);
  template <class _Output_Iterator>
  void add_all_in_edges(_Output_Iterator fi,
                        _LDG_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 _Te,
          class _NAlloc, class _EAlloc>
void
_LDG_base<_Tp,_Ctr,_Iterator,_CIterator,_Te,_NAlloc,_EAlloc>::clear_graph(
        _LDG_node<_Tp,_Ctr,_Iterator>* _node) // implementation of clear graph
{
  _Ctr* oed = &_node->_C_out_edges;
  _Iterator it;

  if(_node->_C_in_edges.size() <= 1)
  {
    // otherwise we will visit this node again later
    for(it = oed->begin(); it != oed->end(); ++it)
      clear_graph((_LDG_node<_Tp,_Ctr,_Iterator>*)(*it));
    _node->_C_out_edges.erase(_node->_C_out_edges.begin(),
                              _node->_C_out_edges.end());
  
    std::_Destroy(&_node->_C_out_edges);
    delete _node->_C_data;
  }
  if(_node->_C_in_edges.size() >= 1)
    _node->_C_in_edges.erase(_node->_C_in_edges.begin());
  if(_node->_C_in_edges.size() == 0)
  {
    std::_Destroy(&_node->_C_in_edges);
    _C_put_node(_node);
  }
}

template <class _Tp, class _Ctr, class _Iterator, class _CIterator, class _Te,
          class _NAlloc, class _EAlloc>
template <class _Output_Iterator>
inline void
_LDG_base<_Tp,_Ctr,_Iterator,_CIterator,_Te,_NAlloc,_EAlloc>::
        add_all_out_edges(_Output_Iterator fi,
                        _LDG_node<_Tp,_Ctr,_Iterator>* _parent)
{ this->_C_ground->add_all_out_edges(fi, _parent); };

template <class _Tp, class _Ctr, class _Iterator, class _CIterator, class _Te,
          class _NAlloc, class _EAlloc>
template <class _Output_Iterator>
inline void
_LDG_base<_Tp,_Ctr,_Iterator,_CIterator,_Te,_NAlloc,_EAlloc>::
        add_all_parents(_Output_Iterator fi,
                        _LDG_node<_Tp,_Ctr,_Iterator>* _child)
{ this->_C_sky->add_all_in_edges(fi, _child); };

template <class _Tp, class _Ctr, class _Iterator, class _CIterator, class _Te,
          class _NAlloc, class _EAlloc>
void
_LDG_base<_Tp,_Ctr,_Iterator,_CIterator,_Te,_NAlloc,_EAlloc>::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 labelled directed graphs is
// instantiated. 

template <class _Tp>
class ldag_node : public _LDG_node<_Tp, vector<void*>, vector<void*>::iterator>
{
}

template <class _Te, class _Tp>
class ldag_edge : public _LDG_edge<_Te, _LDG_node<_Tp> >
{
}

// if we replace the templates above, we get
  
template <class _Tp>
class ldag_node
{
private:
  typedef _Ctr_iterator vector<void*>::iterator;

public:
  _Tp _C_data;
  vector<void *> _C_in_edges;
  vector<void *> _C_out_edges;
  int _C_visited;

  _LDG_node();  // a constructor

  // and methods

  void clear_out_edges();
  void clear_in_edges();

  _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_out_edges(_Output_Iterator fi, ldag_node<_Tp>* _parent);
     
  template <class _Output_Iterator>
    void add_all_in_edges(_Output_Iterator fi, ldag_node<_Tp>* _child);
}


template <class _Te, class _Tp>
class ldag_edge
{
public:
  _Te _E_data;
  ldag_node<_Tp>* _E_snode;
  ldag_node<_Tp>* _E_tnode;

  _LDG_edge();  // a constructor

  // and methods

  void set_edge(ldag_node<_Tp>* s, _Tp* t);
  void set_source(ldag_node<_Tp>* s);
  void set_target(ldag_node<_Tp>* t);

  ldag_node<_Tp>* source() { return _E_snode; }
  ldag_node<_Tp>* target() { return _E_tnode; }

  const ldag_node<_Tp>* source() const { return _E_snode; }
  const ldag_node<_Tp>* target() const { return _E_tnode; }
}


// here is how the ldag_base class essentially looks like

template <class _Tp>
class ldag_base
{
protected:
   ldag_node<_Tp>* _C_ground;
   ldag_node<_Tp>* _C_sky;
   int _C_mark;

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

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

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

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

   ldag_edge<_Te,_Tp>* _C_get_edge();           // construct a new edge
   void _C_put_edge(ldag_edge<_Te,_Tp>* __p);   // destroy a edge

protected:
   void clear_out_edges();   // clear the children vector
   void clear_in_edges();    // clear the parents vector

   // template member functions for out, in edges handling
   template <class _Output_Iterator>
   void add_all_out_edges(_Output_Iterator fi, ldag_node<_Tp>* _parent);
   void add_all_in_edges(_Output_Iterator fi, ldag_node<_Tp>* _child);
}

#endif /* 0 */

__VGTL_END_NAMESPACE


#endif // __VGTL_LDAGBASE_H_ 

---