/* Copyright (c) 1997-2006
   Ewgenij Gawrilow, Michael Joswig (Technische Universitaet Berlin, Germany)
   http://www.math.tu-berlin.de/polymake,  mailto:polymake@math.tu-berlin.de

   This program is free software; you can redistribute it and/or modify it
   under the terms of the GNU General Public License as published by the
   Free Software Foundation; either version 2, or (at your option) any
   later version: http://www.gnu.org/licenses/gpl.txt.

   This program 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
   GNU General Public License for more details.
*/

#ifndef _POLYMAKE_GRAPH_H
#define _POLYMAKE_GRAPH_H "$Project: polymake $$Id: Graph.h 7402 2006-07-27 23:44:14Z gawrilow $"

#ifndef _POLYMAKE_SPARSE2D_H
#  include <sparse2d.h>
#endif
#ifndef _POLYMAKE_INCIDENCE_MATRIX_H
#  include <IncidenceMatrix.h>
#endif
#ifndef _POLYMAKE_ASSOC_H
#  include <assoc.h>
#endif
#ifndef _POLYMAKE_CONVERTERS_H
#  include <converters.h>
#endif
#ifndef _POLYMAKE_CASCADED_CONTAINER_H
#  include <CascadedContainer.h>
#endif
#ifndef _POLYMAKE_SELECTED_SUBSET_H
#  include <SelectedSubset.h>
#endif
#ifndef _POLYMAKE_GENERIC_GRAPH_H
#  include <GenericGraph.h>
#endif

namespace pm {
namespace graph {

using pm::sparse2d::restriction_kind;
using pm::sparse2d::full;
using pm::sparse2d::dying;

template <typename NodeAttr, typename EdgeAttr, kind dir, restriction_kind restriction=full>
class Table;
template <typename NodeAttr, typename EdgeAttr, kind dir, restriction_kind restriction=full>
struct node_entry;

template <typename NodeAttr, typename EdgeAttr, kind dir, bool _out_edges /* =false */, restriction_kind restriction=full>
class traits_base : public sparse2d::it_traits<EdgeAttr, _out_edges, dir!=directed> {
public:
   typedef sparse2d::it_traits<EdgeAttr,_out_edges,dir!=directed> traits_for_iterator;
   typedef typename traits_for_iterator::Node Node;
   static const bool is_skew=(dir==skew);
protected:
   mutable AVL::Ptr<Node> root_links[3];
public:
   typedef EdgeAttr data_type;

   static const bool symmetric=(dir!=directed), row_oriented=_out_edges /* =false */;
   typedef AVL::tree< sparse2d::traits<traits_base, symmetric, restriction> > own_tree;
   typedef AVL::tree< sparse2d::traits<traits_base<NodeAttr,EdgeAttr,dir,(!symmetric && !row_oriented),restriction>,
				       symmetric, restriction> >
      cross_tree;
protected:
   typedef node_entry<NodeAttr,EdgeAttr,dir,restriction> entry;
   typedef sparse2d::ruler<entry> own_ruler;
   typedef own_ruler cross_ruler;

   Node* head_node() const
   {
      return reinterpret_cast<Node*>(const_cast<traits_base*>(this));
   }

   const entry& get_node_entry() const
   {
      return *entry::reverse_cast(static_cast<const own_tree*>(this));
   }
   entry& get_node_entry()
   {
      return *entry::reverse_cast(static_cast<own_tree*>(this));
   }

   const cross_ruler& get_cross_ruler() const
   {
      return get_node_entry().get_ruler();
   }
   cross_ruler& get_cross_ruler()
   {
      return get_node_entry().get_ruler();
   }

   int visit_by_copy(Node* n) const
   {
      return 2*this->get_line_index() - n->key;
   }
public:
   typedef int arg_type;
   traits_base(int index_arg) : traits_for_iterator(index_arg) { }

   const cross_tree& get_cross_tree(int i) const
   {
      return get_cross_ruler()[i].out();
   }
   cross_tree& get_cross_tree(int i)
   {
      return get_cross_ruler()[i].out();
   }

   friend class Table<NodeAttr,EdgeAttr,dir,restriction>;
};

template <typename NodeAttr, typename EdgeAttr, restriction_kind restriction>
class traits_base<NodeAttr, EdgeAttr, directed, true, restriction> {
protected:
   typedef sparse2d::cell<EdgeAttr> Node;

   mutable AVL::Ptr<Node> root_links[3];
public:
   typedef EdgeAttr data_type;

   static const bool symmetric=false, row_oriented=true, is_skew=false;

   typedef sparse2d::it_traits<EdgeAttr,true,false> traits_for_iterator;
   typedef traits_base<NodeAttr,EdgeAttr,directed,!row_oriented,restriction> cross_traits_base;

   static AVL::Ptr<Node>& link(Node *n, AVL::link_index X)
   {
      return n->links[X-AVL::L + 3];
   }

   int get_line_index() const
   {
      return get_node_entry().in().get_line_index();
   }
   traits_for_iterator get_it_traits() const { return get_line_index(); }

   typedef AVL::tree< sparse2d::traits<traits_base, symmetric, restriction> > own_tree;
   typedef AVL::tree< sparse2d::traits<cross_traits_base, symmetric, restriction> > cross_tree;
protected:
   typedef node_entry<NodeAttr, EdgeAttr, directed, restriction> entry;
   typedef sparse2d::ruler<entry> own_ruler;
   typedef own_ruler cross_ruler;

   Node* head_node() const
   {
      return reinterpret_cast<Node*>(reinterpret_cast<char*>(const_cast<traits_base*>(this))-
				     sizeof(cross_traits_base));
   }

   const entry& get_node_entry() const
   {
      return *entry::reverse_cast(static_cast<const own_tree*>(this));
   }
   entry& get_node_entry()
   {
      return *entry::reverse_cast(static_cast<own_tree*>(this));
   }

   const cross_ruler& get_cross_ruler() const
   {
      return get_node_entry().get_ruler();
   }
   cross_ruler& get_cross_ruler()
   {
      return get_node_entry().get_ruler();
   }

   int visit_by_copy(Node* n) const
   {
      return 2*get_line_index() - n->key;
   }
public:
   typedef const traits_base& arg_type;

   const cross_tree& get_cross_tree(int i) const
   {
      return get_cross_ruler()[i].in();
   }
   cross_tree& get_cross_tree(int i)
   {
      return get_cross_ruler()[i].in();
   }

   friend class Table<NodeAttr,EdgeAttr,directed,restriction>;
};

template <typename NodeAttr, typename EdgeAttr, kind dir /* !directed */, restriction_kind restriction=full>
struct node_entry_trees {
   typedef AVL::tree< sparse2d::traits<traits_base<NodeAttr,EdgeAttr,dir,false,restriction>,
				       true, restriction> >
      out_tree_type;
   typedef out_tree_type in_tree_type;
   out_tree_type _out;

   explicit node_entry_trees(int index_arg) : _out(index_arg) { }

   out_tree_type& out() { return _out; }
   const out_tree_type& out() const { return _out; }
   out_tree_type& in() { return _out; }
   const out_tree_type& in() const { return _out; }
   int degree() const { return _out.size(); }

   static const node_entry<NodeAttr,EdgeAttr,dir,restriction>*
   reverse_cast(const out_tree_type* t)
   {
      return static_cast<const node_entry<NodeAttr,EdgeAttr,dir,restriction>*>
	                (pm::reverse_cast(t, &node_entry_trees::_out));
   }
   static node_entry<NodeAttr,EdgeAttr,dir,restriction>*
   reverse_cast(out_tree_type* t)
   {
      return static_cast<node_entry<NodeAttr,EdgeAttr,dir,restriction>*>
	                (pm::reverse_cast(t, &node_entry_trees::_out));
   }
};

template <typename NodeAttr, typename EdgeAttr, restriction_kind restriction>
struct node_entry_trees<NodeAttr, EdgeAttr, directed, restriction> {
   typedef AVL::tree< sparse2d::traits<traits_base<NodeAttr,EdgeAttr,directed,true,restriction>,
				       false, restriction> >
      out_tree_type;
   typedef AVL::tree< sparse2d::traits<traits_base<NodeAttr,EdgeAttr,directed,false,restriction>,
				       false, restriction> >
      in_tree_type;
   in_tree_type _in;
   out_tree_type _out;

   explicit node_entry_trees(int index_arg) : _in(index_arg) { }

   out_tree_type& out() { return _out; }
   const out_tree_type& out() const { return _out; }
   in_tree_type& in() { return _in; }
   const in_tree_type& in() const { return _in; }
   int degree() const { return _out.size()+_in.size(); }

   static const node_entry<NodeAttr,EdgeAttr,directed,restriction>*
   reverse_cast(const out_tree_type* t)
   {
      return static_cast<const node_entry<NodeAttr,EdgeAttr,directed,restriction>*>
	                (pm::reverse_cast(t, &node_entry_trees::_out));
   }
   static node_entry<NodeAttr,EdgeAttr,directed,restriction>*
   reverse_cast(out_tree_type* t)
   {
      return static_cast<node_entry<NodeAttr,EdgeAttr,directed,restriction>*>
	                (pm::reverse_cast(t, &node_entry_trees::_out));
   }
   static const node_entry<NodeAttr,EdgeAttr,directed,restriction>*
   reverse_cast(const in_tree_type* t)
   {
      return static_cast<const node_entry<NodeAttr,EdgeAttr,directed,restriction>*>
	                (pm::reverse_cast(t, &node_entry_trees::_in));
   }
   static node_entry<NodeAttr,EdgeAttr,directed,restriction>*
   reverse_cast(in_tree_type* t)
   {
      return static_cast<node_entry<NodeAttr,EdgeAttr,directed,restriction>*>
	                (pm::reverse_cast(t, &node_entry_trees::_in));
   }
};

template <typename NodeAttr>
struct node_entry_data {
   NodeAttr data;

   node_entry_data() : data() { }

   template <typename Data>
   explicit node_entry_data(const Data& node_arg)
      : data(node_arg) { }

   NodeAttr& get_node_attr() { return data; }
   const NodeAttr& get_node_attr() const { return data; }
};

template <>
struct node_entry_data<nothing> {
   node_entry_data() { }

   template <typename Data>
   explicit node_entry_data(const Data&) { }

   nothing& get_node_attr()
   {
      return std::pair<int,nothing>::second;
   }
   const nothing& get_node_attr() const
   {
      return std::pair<int,nothing>::second;
   }
};

template <typename EdgeIterator>
class skew_proxy {
   typedef typename EdgeIterator::value_type::data_type edge_attr;
   edge_attr val;
   EdgeIterator edge;
   operations::neg<const edge_attr&> op;
public:
   skew_proxy() { }

   skew_proxy(const EdgeIterator& edge_arg)
      : val(edge_arg->get_data()), edge(edge_arg)
   {
      if (edge.is_inversed(*edge)) op.assign(val);
   }

   skew_proxy(typename function_argument<edge_attr>::type& tmp_val) : val(tmp_val) { }

   operator const edge_attr& () const { return val; }

protected:
   void update()
   {
      if (edge.is_inversed(*edge))
	 edge->get_data()=op(val);
      else
	 edge->get_data()=val;
   }
public:
   skew_proxy& operator= (typename function_argument<edge_attr>::type x)
   {
      val=x; update();
      return *this;
   }

   skew_proxy& operator= (const skew_proxy& v)
   {
      return operator=(v.val);
   }

   template <typename T>
   skew_proxy& operator+= (const T& x)
   {
      val+=x; update();
      return *this;
   }
   template <typename T>
   skew_proxy& operator-= (const T& x)
   {
      val-=x; update();
      return *this;
   }
   skew_proxy& operator++()
   {
      ++val; update();
      return *this;
   }
   skew_proxy& operator--()
   {
      --val; update();
      return *this;
   }
   template <typename T>
   skew_proxy& operator*= (const T& x)
   {
      val*=x; update();
      return *this;
   }
   template <typename T>
   skew_proxy& operator/= (const T& x)
   {
      val/=x; update();
      return *this;
   }
   template <typename T>
   skew_proxy& operator%= (const T& x)
   {
      val%=x; update();
      return *this;
   }
   template <typename T>
   skew_proxy& operator<<= (const T& x)
   {
      val<<=x; update();
      return *this;
   }
   template <typename T>
   skew_proxy& operator>>= (const T& x)
   {
      val>>=x; update();
      return *this;
   }
};

template <typename tree_type, bool _is_skew=tree_type::is_skew>
struct node_entry_edge_access {
   typedef typename tree_type::iterator::value_type::data_type edge_value_type;
   typedef typename assign_const<edge_value_type, identical<edge_value_type,nothing>::value>::type& edge_ref;
   typedef const edge_value_type& const_edge_ref;

   template <typename Iterator>
   static typename if_else<attrib<typename Iterator::reference>::is_const, const_edge_ref, edge_ref>::type
   get_edge_data(const Iterator& it)
   {
      return it->get_data();
   }

   template <typename Iterator>
   static const_edge_ref get_edge_data(const Iterator& it, const_edge_ref def)
   {
      return it.at_end() ? def : *it;
   }
};

template <typename tree_type>
struct node_entry_edge_access<tree_type, true> {
   typedef typename tree_type::iterator::value_type::data_type edge_value_type;
   typedef skew_proxy<typename tree_type::iterator> edge_ref;
   typedef const skew_proxy<typename tree_type::const_iterator> const_edge_ref;

   static edge_ref get_edge_data(const typename tree_type::iterator& it) { return it; }
   static const_edge_ref get_edge_data(const typename tree_type::const_iterator& it) { return it; }

   static const_edge_ref get_edge_data(const typename tree_type::const_iterator& it, const edge_value_type& def)
   {
      if (it.at_end()) return def;
      return it;
   }
};

template <typename NodeAttr, typename EdgeAttr, kind _dir, restriction_kind restriction>
struct node_entry
   : public node_entry_trees<NodeAttr, EdgeAttr, _dir, restriction>,
     public node_entry_data<NodeAttr>,
     public node_entry_edge_access<typename node_entry_trees<NodeAttr, EdgeAttr, _dir, restriction>::out_tree_type, _dir==skew> {

   typedef NodeAttr node_attr;
   typedef EdgeAttr edge_attr;
   static const kind dir=_dir;

   explicit node_entry(int index_arg)
      : node_entry_trees<NodeAttr, EdgeAttr, dir, restriction>(index_arg) { }

   template <typename Data>
   node_entry(int index_arg, const Data& node_arg)
      : node_entry_trees<NodeAttr, EdgeAttr, dir, restriction>(index_arg),
	node_entry_data<NodeAttr>(node_arg) { }

   int get_line_index() const { return this->in().get_line_index(); }

   const sparse2d::ruler<node_entry>& get_ruler() const
   {
      return sparse2d::ruler<node_entry>::reverse_cast(this, get_line_index());
   }
   sparse2d::ruler<node_entry>& get_ruler()
   {
      return sparse2d::ruler<node_entry>::reverse_cast(this, get_line_index());
   }
};

} // end namespace graph

template <typename NodeAttr, typename EdgeAttr, graph::restriction_kind restriction> inline
void relocate(graph::node_entry_trees<NodeAttr,EdgeAttr,graph::directed,restriction>* from,
	      graph::node_entry_trees<NodeAttr,EdgeAttr,graph::directed,restriction>* to)
{
   relocate(&from->_out, &to->_out);
   relocate(&from->_in, &to->_in);
}

template <typename NodeAttr, typename EdgeAttr, graph::kind dir, graph::restriction_kind restriction> inline
void relocate(graph::node_entry_trees<NodeAttr,EdgeAttr,dir,restriction>* from,
	      graph::node_entry_trees<NodeAttr,EdgeAttr,dir,restriction>* to)
{
   relocate(&from->_out, &to->_out);
}

template <typename NodeAttr, typename EdgeAttr, graph::kind dir, graph::restriction_kind restriction> inline
void relocate(graph::node_entry<NodeAttr,EdgeAttr,dir,restriction>* from,
	      graph::node_entry<NodeAttr,EdgeAttr,dir,restriction>* to)
{
   relocate(static_cast<graph::node_entry_trees<NodeAttr, EdgeAttr, dir, restriction>*>(from),
	    static_cast<graph::node_entry_trees<NodeAttr, EdgeAttr, dir, restriction>*>(to));
   relocate(&from->get_node_attr(), &to->get_node_attr());
}

template <typename NodeAttr, typename EdgeAttr, graph::kind dir> inline
void relocate(graph::Graph<NodeAttr,EdgeAttr,dir>*,
	      graph::Graph<NodeAttr,EdgeAttr,dir>*);

namespace graph {

template <typename NodeAttr, typename EdgeAttr, kind dir, restriction_kind restriction>
class Table {
public:
   typedef node_entry<NodeAttr,EdgeAttr,dir,restriction> entry;
   typedef sparse2d::ruler<entry> ruler;
protected:
   ruler *R;
   typedef Table<NodeAttr,EdgeAttr,dir,dying> restricted_Table;
public:
   static const bool symmetric=(dir!=directed);
   typedef bool2type<symmetric> sym_discr;

   Table()
      : R(ruler::construct(0)) { }

   explicit Table(int n)
      : R(ruler::construct(n)) { }

   template <typename Iterator>
   Table(int n, Iterator node_src)
      : R(ruler::construct(n,node_src)) { }

   Table(const Table& t)
      : R(ruler::construct(*t.R)) { }

   ~Table()
   {
      if (restriction==full)
	 reinterpret_cast<restricted_Table*>(this)->~restricted_Table();
      else
	 ruler::destroy(R);
   }

   Table& operator= (const Table& t)
   {
      this->~Table();
      new(this) Table(t);
      return *this;
   }

   void swap(Table& t) { std::swap(R,t.R); }
   int size() const { return R->size(); }

   void clear(int n=0)
   {
      R=ruler::resize_and_clear(R,n);
   }
   void resize(int n)
   {
      R=ruler::resize(R,n);
   }

   typedef typename entry::out_tree_type out_tree_type;
   typedef typename entry::in_tree_type in_tree_type;

   entry& operator[] (int n)
   {
      return (*R)[n];
   }
   const entry& operator[] (int n) const
   {
      return (*R)[n];
   }

   int add_node()
   {
      int n=size();
      R=ruler::resize(R,n+1);
      return n;
   }

protected:
   struct squeeze_node_handler {
      bool operator() (int, const entry& t) const
      {
	 return t.degree()>0;
      }
   };

   template <typename Iterator, bool complement>
   struct delete_node_handler {
      bool operator() (int n, entry& t)
      {
	 bool match=complement;
	 if (!it.at_end() && n==*it) {
	    ++it;
	    match=!complement;
	 }
	 if (match) {
	    t.out().clear();
	    if (!symmetric) t.in().clear();
	 }
	 return !match;
      }

      delete_node_handler(const Iterator& it_arg) : it(it_arg) { }
   protected:
      Iterator it;
   };

   template <typename Tree>
   void renumber_edges(Tree& t, int /*nnew*/, int diff, False)
   {
      for (typename Entire<Tree>::iterator e=entire(t); !e.at_end(); ++e)
	 e->key -= diff;
   }
   void renumber_edges(typename entry::in_tree_type& t, int nnew, int diff, True)
   {
      const int diag=2*t.line_index;
      for (typename Entire<typename entry::in_tree_type>::iterator e=entire(t); !e.at_end(); ) {
	 sparse2d::cell<EdgeAttr>& c=*e; ++e;
	 c.key -= diff << (c.key==diag);
      }
      t.line_index=nnew;
   }

   template <typename NumberConsumer, typename NodeHandler>
   void squeeze(NumberConsumer nc, NodeHandler good_node)
   {
      int n=0, nnew=0;
      for (entry *t=R->begin(), *end=R->end(); t!=end; ++t, ++n) {
	 if (good_node(n,*t)) {
	    if (int diff=n-nnew) {
	       if (!symmetric) t->in().line_index=nnew;
	       renumber_edges(t->out(), nnew, diff, bool2type<symmetric>());
	       if (!symmetric) renumber_edges(t->in(), nnew, diff, bool2type<symmetric>());
	       relocate(t, t-diff);
	    }
	    ++nnew; *nc++=n;
	 } else {
	    t->~entry();
	 }
      }
      if (nnew < n) R=ruler::resize(R,nnew,false);
   }

public:
   template <typename NumberConsumer>
   void squeeze(NumberConsumer nc)
   {
      squeeze(nc, squeeze_node_handler());
   }

   template <typename Iterator, bool complement>
   void delete_nodes(Iterator nodes_to_delete, bool2type<complement>)
   {
      squeeze(black_hole<int>(), delete_node_handler<Iterator,complement>(nodes_to_delete));
   }

#ifdef POLY_DEBUG
public:
   void check(const char* prefix) const
   {
      for (const entry *r=R->begin(), *end=R->end(); r!=end; ++r) {
	 check(r->out(), prefix, "(out)");
	 if (!symmetric) check(r->in(), prefix, "(in)");
      }
   }
protected:
   template <typename Tree>
   void check(const Tree& t, const char* prefix, const char* direction) const
   {
      std::ostringstream label;
      label << prefix << "node " << t.get_line_index() << direction << ": ";
      t.check(label.str().c_str());
   }
#endif // POLY_DEBUG
public:
   ruler& get_ruler() { return *R; }
   const ruler& get_ruler() const { return *R; }
};

template <typename Iterator, typename Accessor>
class incident_edge_iterator : public unary_transform_iterator<Iterator, Accessor> {
   typedef unary_transform_iterator<Iterator, Accessor> _super;
public:
   typedef incident_edge_iterator<typename iterator_traits<Iterator>::iterator, Accessor>
      iterator;
   typedef incident_edge_iterator<typename iterator_traits<Iterator>::const_iterator, Accessor>
      const_iterator;

   incident_edge_iterator() { }

   template <typename Accessor2>
   incident_edge_iterator(const incident_edge_iterator<typename iterator_traits<Iterator>::iterator, Accessor2>& it)
      : _super(it) { }

   incident_edge_iterator(const Iterator& cur_arg, const Accessor& acc_arg=Accessor())
      : _super(cur_arg, acc_arg) { }

   int from_node() const
   {
      return (Iterator::symmetric || Iterator::row_oriented) ? this->get_line_index() : _super::index();
   }
   int to_node() const
   {
      return (Iterator::symmetric || Iterator::row_oriented) ? _super::index() : this->get_line_index();
   }
};

struct incident_edge_access_constructor : unary_transform_constructor<> {
   template <typename Iterator, typename Accessor, typename ExpectedFeatures>
   struct defs
      : unary_transform_constructor<>::defs<Iterator, Accessor, ExpectedFeatures> {
      typedef incident_edge_iterator<Iterator, Accessor> iterator;
   };
};

template <bool _is_skew>
struct incident_edge_list_accessor {
   typedef BuildUnary<sparse2d::cell_accessor> type;
};

template <typename IteratorRef>
struct incident_edge_skew_accessor {
   typedef IteratorRef argument_type;
   typedef typename deref<IteratorRef>::type Iterator;
   typedef typename inherit_const<skew_proxy<Iterator>, typename Iterator::reference>::type result_type;
   result_type operator() (const Iterator& it) const { return it; }
};

template <>
struct incident_edge_list_accessor<true> {
   typedef BuildUnaryIt<incident_edge_skew_accessor> type;
};

template <typename Tree>
class incident_edge_list
   : public modified_tree< incident_edge_list<Tree>,
			   list( Operation< pair< typename incident_edge_list_accessor<Tree::is_skew>::type,
				                  BuildUnaryIt<sparse2d::cell_index_accessor> > >,
				 IteratorConstructor< incident_edge_access_constructor >,
				 Hidden< Tree > ) > {
   typedef modified_tree<incident_edge_list> _super;
protected:
   ~incident_edge_list();

   template <typename Iterator>
   void _insert(const typename _super::iterator& dst, const Iterator& src, False)
   {
      this->insert(dst,src.index());
   }

   template <typename Iterator>
   void _insert(const typename _super::iterator& dst, const Iterator& src, True)
   {
      this->insert(dst, src.index(), *src);
   }

   template <typename Iterator>
   void _assign(const typename _super::iterator&, const Iterator&, False) { }

   template <typename Iterator>
   void _assign(const typename _super::iterator& dst, const Iterator& src, True) { *dst=*src; }

   template <typename Iterator>
   struct assign_data_helper {
      static const bool assign_data=!(identical<typename _super::iterator::value_type, nothing>::value ||
			              identical<typename iterator_traits<Iterator>::value_type, nothing>::value);
      typedef bool2type<assign_data> discr;
   };

   template <typename Iterator>
   void copy(Iterator src)
   {
      typename _super::iterator dst=this->begin();
      for (; !src.at_end(); ++src) {
	 int idiff=1;
	 while (!dst.at_end()) {
	    int idiff=dst.index()-src.index();
	    if (idiff<0) this->erase(dst++);
	    else         break;
	    idiff=1;
	 }
	 if (idiff>0) _insert(dst, src, typename assign_data_helper<Iterator>::discr());
	 else         _assign(dst, src, typename assign_data_helper<Iterator>::discr());
      }
      while (!dst.at_end()) this->erase(dst++);
   }

   template <typename Iterator>
   void init(Iterator src, False)
   {
      typename _super::iterator e=this->end();
      const int diag= Tree::symmetric ? this->hidden().get_line_index() : 0;
      for (; !src.at_end(); ++src) {
	 if (Tree::symmetric && src.index() > diag) break;
	 _insert(e, src, typename assign_data_helper<Iterator>::discr());
      }
   }

   template <typename Iterator>
   void init(Iterator src, True)
   {
      typename _super::iterator dst=this->begin();
      for (; !src.at_end(); ++src) {
	 int idiff=1;
	 while (!dst.at_end()) {
	    int idiff=dst.index()-src.index();
	    if (idiff<=0) ++dst;
	    if (idiff>=0) break;
	    idiff=1;
	 }
	 if (idiff>0) _insert(dst, src, typename assign_data_helper<Iterator>::discr());
      }
   }

   maximal<int> max_input_dim(False) const { return maximal<int>(); }
   int max_input_dim(True) const { return this->hidden().get_line_index(); }
public:
   int dim() const { return this->max_size(); }

   typedef typename if_else<Tree::symmetric, int, maximal<int> >::type max_input_dim_type;
   max_input_dim_type max_input_dim() const
   {
      return max_input_dim(bool2type<Tree::symmetric>());
   }

   incident_edge_list& operator= (const incident_edge_list& l)
   {
      copy(entire(l));
      return *this;
   }

   template <typename,typename,kind> friend class Graph;
   using _super::get_comparator_object;
};

template <typename IteratorRef>
struct lower_edge_predicate {
   typedef IteratorRef argument_type;
   typedef bool result_type;

   bool operator() (argument_type it) const
   {
      return it.index() <= it.get_line_index();
   }
};

template <typename Tree>
class lower_incident_edge_list
   : public modified_container_impl< lower_incident_edge_list<Tree>,
				     list( Hidden< incident_edge_list<Tree> >,
					   IteratorConstructor< input_truncator_constructor >,
					   Operation< BuildUnaryIt<lower_edge_predicate> > ) > {
public:
   int dim() const { return this->hidden().dim(); }
};

template <typename EntryRef>
struct node_accessor {
   typedef EntryRef argument_type;
   typedef typename deref<EntryRef>::type entry_type;
   typedef typename inherit_ref<typename deref<EntryRef>::type::node_attr, EntryRef>::type result_type;

   result_type operator() (argument_type t) const
   {
      return t.get_node_attr();
   }

   typedef typename entry_type::out_tree_type out_tree_type;
   typedef typename entry_type::in_tree_type in_tree_type;
   typedef incident_edge_list<out_tree_type> out_edge_list;
   typedef incident_edge_list<in_tree_type> in_edge_list;
   typedef incidence_line<out_tree_type> out_neighbor_list;
   typedef incidence_line<in_tree_type> in_neighbor_list;
   typedef out_neighbor_list neighbor_list;
   typedef typename inherit_ref<out_edge_list, EntryRef>::type out_edge_list_ref;
   typedef typename inherit_ref<in_edge_list, EntryRef>::type in_edge_list_ref;
   typedef typename inherit_ref<out_neighbor_list, EntryRef>::type out_neighbor_list_ref;
   typedef typename inherit_ref<in_neighbor_list, EntryRef>::type in_neighbor_list_ref;
   typedef out_neighbor_list_ref neighbor_list_ref;
   typedef typename if_else<attrib<EntryRef>::is_const, typename entry_type::const_edge_ref, typename entry_type::edge_ref>::type
       edge_ref;

   out_edge_list_ref out_edges(EntryRef t) const
   {
      return reinterpret_cast<out_edge_list_ref>(t.out());
   }
   in_edge_list_ref in_edges(EntryRef t) const
   {
      return reinterpret_cast<in_edge_list_ref>(t.in());
   }

   typename out_tree_type::const_iterator _out_edge(EntryRef t, int n2, True) const
   {
      typename out_tree_type::const_iterator e=t.out().find(n2);
      if (e.at_end()) throw no_match("non-existing edge");
      return e;
   }
   typename in_tree_type::const_iterator _in_edge(EntryRef t, int n2, True) const
   {
      typename in_tree_type::const_iterator e=t.in().find(n2);
      if (e.at_end()) throw no_match("non-existing edge");
      return e;
   }

   typename out_tree_type::iterator _out_edge(EntryRef t, int n2, False) const
   {
      return t.out().insert(n2);
   }
   typename in_tree_type::iterator _in_edge(EntryRef t, int n2, False) const
   {
      return t.in().insert(n2);
   }
   edge_ref out_edge(EntryRef t, int n2) const
   {
      return t.get_edge_data(_out_edge(t, n2, bool2type<attrib<EntryRef>::is_const>()));
   }
   edge_ref in_edge(EntryRef t, int n2) const
   {
      return t.get_edge_data(_in_edge(t, n2, bool2type<attrib<EntryRef>::is_const>()));
   }
   edge_ref try_edge(EntryRef t, int n2, const typename entry_type::edge_attr& def) const
   {
      return t.get_edge_data(t.out().find(n2), def);
   }

   int out_degree(EntryRef t) const
   {
      return t.out().size();
   }
   int in_degree(EntryRef t) const
   {
      return t.in().size();
   }
   int degree(EntryRef t) const
   {
      return t.degree();
   }

   out_neighbor_list_ref out_neighbors(EntryRef t) const
   {
      return reinterpret_cast<out_neighbor_list_ref>(t.out());
   }
   in_neighbor_list_ref in_neighbors(EntryRef t) const
   {
      return reinterpret_cast<in_neighbor_list_ref>(t.in());
   }
   neighbor_list_ref neighbors(EntryRef t) const
   {
      return reinterpret_cast<neighbor_list_ref>(t.out());
   }
};

template <typename Iterator, typename Accessor>
struct node_iterator : public unary_transform_iterator<Iterator, Accessor> {
   typedef unary_transform_iterator<Iterator, Accessor> _super;
public:
   typedef node_iterator<typename iterator_traits<Iterator>::iterator, Accessor> iterator;
   typedef node_iterator<typename iterator_traits<Iterator>::const_iterator, Accessor> const_iterator;

   node_iterator() { }

   template <typename Accessor2>
   node_iterator(const node_iterator<typename iterator_traits<Iterator>::iterator, Accessor2>& it)
      : _super(it) { }

   node_iterator(const Iterator& cur_arg, const Accessor& acc_arg=Accessor())
      : _super(cur_arg,acc_arg) { }

protected:
   typename iterator_traits<Iterator>::reference entry() const
   {
      return *static_cast<const typename _super::super&>(*this);
   }
public:
   typedef typename _super::helper::operation::out_edge_list_ref out_edge_list_ref;
   typedef typename _super::helper::operation::in_edge_list_ref in_edge_list_ref;
   typedef typename _super::helper::operation::edge_ref edge_ref;
   typedef typename _super::helper::operation::out_neighbor_list_ref out_neighbor_list_ref;
   typedef typename _super::helper::operation::in_neighbor_list_ref in_neighbor_list_ref;
   typedef typename _super::helper::operation::neighbor_list_ref neighbor_list_ref;

   out_edge_list_ref out_edges() const
   {
      return this->op.out_edges(entry());
   }
   in_edge_list_ref in_edges() const
   {
      return this->op.in_edges(entry());
   }

   edge_ref out_edge(int n2) const
   {
      return this->op.out_edge(entry(), n2);
   }
   edge_ref in_edge(int n2) const
   {
      return this->op.in_edge(entry(), n2);
   }
   edge_ref edge(int n2) const
   {
      return this->op.out_edge(entry(), n2);
   }

   int out_degree() const
   {
      return this->op.out_degree(entry());
   }
   int in_degree() const
   {
      return this->op.in_degree(entry());
   }
   int degree() const
   {
      return this->op.degree(entry());
   }

   out_neighbor_list_ref out_neighbors() const
   {
      return this->op.out_neighbors(entry());
   }
   in_neighbor_list_ref in_neighbors() const
   {
      return this->op.in_neighbors(entry());
   }
   neighbor_list_ref neighbors() const
   {
      return this->op.neighbors(entry());
   }
};

struct node_access_constructor : unary_transform_constructor<> {
   template <typename Iterator, typename Accessor, typename ExpectedFeatures>
   struct defs : unary_transform_constructor<>::defs<Iterator,Accessor,ExpectedFeatures> {
      typedef node_iterator<Iterator,Accessor> iterator;
   };
};

template <typename _Table>
class node_container
   : public modified_container_impl< node_container<_Table>,
				     list( Container< typename _Table::ruler >,
					   Operation< pair< BuildUnary<node_accessor>, BuildUnary<sparse2d::line_index_accessor> > >,
					   IteratorConstructor< node_access_constructor >,
					   MasqueradedTop ) > {
protected:
   ~node_container();
public:
   typename node_container::container& get_container() { return this->hidden().get_ruler(); }
   const typename node_container::container& get_container() const { return this->hidden().get_ruler(); }

   void resize(int n) { this->hidden().clear(n); }
};
} // end namespace graph

template <typename Iterator, typename Accessor, typename Feature>
struct check_iterator_feature<graph::node_iterator<Iterator, Accessor>, Feature>
   : check_iterator_feature<unary_transform_iterator<Iterator, Accessor>, Feature> { };

template <typename Iterator, typename Accessor, typename Feature>
struct check_iterator_feature<graph::incident_edge_iterator<Iterator, Accessor>, Feature>
   : check_iterator_feature<unary_transform_iterator<Iterator, Accessor>, Feature> { };

namespace graph {

template <bool _out_edges, template <typename> class MasqueradeLine, typename EntryRef=void>
class line_factory {
public:
   typedef EntryRef argument_type;
   typedef typename if_else<_out_edges, typename deref<EntryRef>::type::out_tree_type,
			                typename deref<EntryRef>::type::in_tree_type >::type
      tree_type;
   typedef typename inherit_ref<MasqueradeLine<tree_type>, EntryRef>::type result_type;

   result_type operator() (EntryRef t) const
   {
      return _do(t, bool2type<_out_edges>());
   }
private:
   result_type _do(EntryRef t, True) const
   {
      return reinterpret_cast<result_type>(t.out());
   }
   result_type _do(EntryRef t, False) const
   {
      return reinterpret_cast<result_type>(t.in());
   }
};

template <bool _out_edges, template <typename> class MasqueradeLine>
class line_factory<_out_edges, MasqueradeLine, void> : operations::incomplete { };

} // end namespace graph

template <bool _out_edges, template <typename> class MasqueradeLine, typename Iterator, typename EntryRef>
struct unary_op_builder<graph::line_factory<_out_edges,MasqueradeLine,void>, Iterator, EntryRef>
   : empty_op_builder< graph::line_factory<_out_edges,MasqueradeLine,EntryRef> > { };

namespace graph {

template <typename _Table, bool _out_edges, template <typename> class MasqueradeLine>
class line_container
   : public modified_container_impl< line_container<_Table,_out_edges,MasqueradeLine>,
				     list( Container< typename _Table::ruler >,
					   Operation< pair< line_factory<_out_edges, MasqueradeLine>,
					                    BuildUnary<sparse2d::line_index_accessor> > >,
					   Hidden< _Table > ) > {
protected:
   ~line_container();
public:
   typename line_container::container& get_container() { return this->hidden().get_ruler(); }
   const typename line_container::container& get_container() const { return this->hidden().get_ruler(); }

   void resize(int n) { this->hidden().clear(n); }
};

template <typename _Table, bool _symmetric=_Table::symmetric>
struct edge_container_helper {
   typedef line_container<_Table,true,incident_edge_list> type;
};
template <typename _Table>
struct edge_container_helper<_Table,true> {
   typedef line_container<_Table,true,lower_incident_edge_list> type;
};

template <typename _Table>
class edge_container
   : public cascade_impl< edge_container<_Table>,
			  list( Hidden< typename edge_container_helper<_Table>::type >,
				CascadeDepth< int2type<2> > ) > {
protected:
   ~edge_container();
};
} // end namespace graph

template <typename Tree>
struct spec_object_traits< graph::incident_edge_list<Tree> >
   : spec_object_traits<is_container> {
   static const bool IO_hide_dim=true;
   static const int is_resizeable=0;
   static const IO_separator_kind IO_separator=IO_sep_inherit;
};

template <typename Tree>
struct spec_object_traits< graph::lower_incident_edge_list<Tree> >
   : spec_object_traits< graph::incident_edge_list<Tree> > { };

template <typename Tree>
struct check_container_feature< graph::incident_edge_list<Tree>, sparse > : True { };

template <typename Tree>
struct check_container_feature< graph::lower_incident_edge_list<Tree>, sparse > : True { };

namespace graph {

template <typename _Table>
class neighborhood
   : public GenericIncidenceMatrix< neighborhood<_Table>, typename _Table::sym_discr > {
protected:
   ~neighborhood();
public:
   typedef _Table hidden_type;

   const _Table& hidden() const { return reinterpret_cast<const _Table&>(*this); }
};

} // end namespace graph

template <typename _Table>
class Rows< graph::neighborhood<_Table> >
   : public graph::line_container<_Table, true, incidence_line> {
protected:
   ~Rows();
};

template <typename _Table>
class Cols< graph::neighborhood<_Table> >
   : public graph::line_container<_Table, false, incidence_line> {
protected:
   ~Cols();
};

template <typename _Table>
class matrix_random_access_methods< graph::neighborhood<_Table> > {
public:
   bool operator() (int i, int j) const
   {
      return static_cast<const graph::neighborhood<_Table>*>(this)->hidden().exists_edge(i,j);
   }
};

namespace graph {

template <typename NodeAttr, typename EdgeAttr, kind _dir>
class Graph
   : public GenericGraph< Graph<NodeAttr,EdgeAttr,_dir>, NodeAttr, EdgeAttr, _dir > {
protected:
   typedef Table<NodeAttr, EdgeAttr, _dir> table_type;
   shared_object<table_type> data;

public:
   Graph() { }

   explicit Graph(int n)
      : data( make_constructor(n, (table_type*)0) ) { }

   Graph(const GenericGraph<Graph>& G2)
      : data(G2.top().data) { }

   template <typename Graph2, kind dir2>
   Graph(const GenericGraph<Graph2, NodeAttr, EdgeAttr, dir2>& G2)
      : data( make_constructor(G2.nodes(), pm::nodes(G2).begin(), (table_type*)0) )
   {
      const bool need_merge= dir2==directed && _dir!=directed;
      _copy(out_edge_lists(G2).begin(), bool2type<need_merge>());
   }

   template <typename Graph2, typename NodeAttr2, typename EdgeAttr2, kind dir2>
   explicit Graph(const GenericGraph<Graph2, NodeAttr2, EdgeAttr2, dir2>& G2)
      : data( make_constructor(G2.nodes(), attach_converter<NodeAttr>(pm::nodes(G2)).begin(), (table_type*)0) )
   {
      const bool need_merge= dir2==directed && _dir!=directed;
      _copy_conv(out_edge_lists(G2).begin(), bool2type<need_merge>());
   }

   Graph& operator= (const GenericGraph<Graph>& G2)
   {
      data=G2.top().data;
      return *this;
   }

   template <typename Graph2, kind dir2>
   Graph& operator= (const GenericGraph<Graph2, NodeAttr, EdgeAttr, dir2>& G2)
   {
      data=make_constructor(G2.nodes(), pm::nodes(G2).begin(), (table_type*)0);
      const bool need_merge= dir2==directed && _dir!=directed;
      _copy(out_edge_lists(G2).begin(), bool2type<need_merge>());
      return *this;
   }

   template <typename Graph2, typename NodeAttr2, typename EdgeAttr2, kind dir2>
   Graph& operator= (const GenericGraph<Graph2, NodeAttr2, EdgeAttr2, dir2>& G2)
   {
      data=make_constructor(G2.nodes(), attach_converter<NodeAttr>(pm::nodes(G2)).begin(), (table_type*)0);
      const bool need_merge= dir2==directed && _dir!=directed;
      _copy_conv(out_edge_lists(G2).begin(), bool2type<need_merge>());
      return *this;
   }

   int nodes() const { return data->size(); }

   void resize(int n) { data->resize(n); }

   void clear(int n=0)
   {
      if (data.is_shared())
	 data=make_constructor(n, (table_type*)0);
      else
	 data->clear(n);
   }

   // for IndexDispenser
   class ResizeTraits {
      Graph *G;
   protected:
      void resize(int n) { G->resize(n); }
   public:
      ResizeTraits(Graph& G_arg) : G(&G_arg) { }
   };

   void swap(Graph& G) { data.swap(G.data); }

   friend void pm::relocate<>(Graph* from, Graph* to);

   template <typename NumberConsumer>
   void squeeze(NumberConsumer nc)
   {
      data->squeeze(nc);
   }
      
   void squeeze()
   {
      data->squeeze(black_hole<int>());
   }

   void delete_node(int n)
   {
      INDEX_CHECK((n<0 || n>=nodes()), "delete_node - node id out of range");
      data->delete_nodes(entire(item2container(n)), False());
   }

   template <typename Set>
   void delete_nodes(const GenericSet<Set>& nodes_to_delete)
   {
      if (!nodes_to_delete.top().empty())
	 data->delete_nodes(entire(nodes_to_delete), False());
   }

   template <typename Set>
   void delete_nodes(const Complement<Set>& nodes_to_delete)
   {
      data->delete_nodes(entire(nodes_to_delete.top()), True());
   }

   typedef graph::node_container<table_type> node_container;
   typedef node_container& node_container_ref;
   typedef const node_container& const_node_container_ref;

   typedef graph::edge_container<table_type> edge_container;
   typedef edge_container& edge_container_ref;
   typedef const edge_container& const_edge_container_ref;

   template <template <typename> class MasqueradeLine>
   struct edge_access {
      typedef line_container<table_type, true, MasqueradeLine> out;
      typedef line_container<table_type, false, MasqueradeLine> in;
   };

   typedef typename edge_access<incident_edge_list>::out out_edge_list_container;
   typedef out_edge_list_container& out_edge_list_container_ref;
   typedef const out_edge_list_container& const_out_edge_list_container_ref;

   typedef typename out_edge_list_container::value_type out_edge_list;
   typedef out_edge_list& out_edge_list_ref;
   typedef const out_edge_list& const_out_edge_list_ref;

   typedef typename edge_access<incident_edge_list>::in in_edge_list_container;
   typedef in_edge_list_container& in_edge_list_container_ref;
   typedef const in_edge_list_container& const_in_edge_list_container_ref;

   typedef typename in_edge_list_container::value_type in_edge_list;
   typedef in_edge_list& in_edge_list_ref;
   typedef const in_edge_list& const_in_edge_list_ref;

   typedef graph::neighborhood<table_type> neighborhood_matrix;
   typedef neighborhood_matrix& neighborhood_matrix_ref;
   typedef const neighborhood_matrix& const_neighborhood_matrix_ref;

   typedef typename neighborhood_matrix::row_type out_neighbor_list;
   typedef typename neighborhood_matrix::col_type in_neighbor_list;
   typedef typename if_else<_dir==directed, nothing, out_neighbor_list>::type neighbor_list;
   typedef out_neighbor_list& out_neighbor_list_ref;
   typedef const out_neighbor_list& const_out_neighbor_list_ref;
   typedef in_neighbor_list& in_neighbor_list_ref;
   typedef const in_neighbor_list& const_in_neighbor_list_ref;
   typedef typename if_else<_dir==directed, nothing, out_neighbor_list_ref>::type neighbor_list_ref;
   typedef typename if_else<_dir==directed, nothing, const_out_neighbor_list_ref>::type const_neighbor_list_ref;

   template <typename MasqueradeRef>
   MasqueradeRef pretend()
   {
      return reinterpret_cast<MasqueradeRef>(*data);
   }

   template <typename MasqueradeRef>
   MasqueradeRef pretend() const
   {
      return reinterpret_cast<MasqueradeRef>(*data);
   }

   NodeAttr& node(int n)
   {
      INDEX_CHECK((n<0 || n>=nodes()), "node - node id out of range");
      return (*data)[n].get_node_attr();
   }
   const NodeAttr& node(int n) const
   {
      INDEX_CHECK((n<0 || n>=nodes()), "node - node id out of range");
      return (*data)[n].get_node_attr();
   }

   template <typename Data>
   int add_node(const Data& d)
   {
      int n=data->add_node();
      (*data)[n].get_node_attr()=d;
      return n;
   }

   int add_node() { return data->add_node(); }

   int out_degree(int n) const
   {
      INDEX_CHECK((n<0 || n>=nodes()), "out_degree - node id out of range");
      return (*data)[n].out().size();
   }
   int in_degree(int n) const
   {
      INDEX_CHECK((n<0 || n>=nodes()), "in_degree - node id out of range");
      return (*data)[n].in().size();
   }
   int degree(int n) const
   {
      INDEX_CHECK((n<0 || n>=nodes()), "degree - node id out of range");
      return (*data)[n].degree();
   }

private:
   typedef typename table_type::entry node_entry_type;
   typedef node_accessor<node_entry_type&> node_acc;
   typedef node_accessor<const node_entry_type&> const_node_acc;
public:
   typename node_acc::edge_ref
   edge(int n1, int n2)
   {
      INDEX_CHECK((n1<0 || n1>=nodes() || n2<0 || n2>=nodes()), "edge - node id out of range");
      node_acc n;
      return n.out_edge((*data)[n1], n2);
   }
   typename const_node_acc::edge_ref
   edge(int n1, int n2) const
   {
      INDEX_CHECK((n1<0 || n1>=nodes() || n2<0 || n2>=nodes()), "edge - node id out of range");
      const_node_acc n;
      return n.out_edge((*data)[n1], n2);
   }
   typename const_node_acc::edge_ref
   try_edge(int n1, int n2, const EdgeAttr& def) const
   {
      INDEX_CHECK((n1<0 || n1>=nodes() || n2<0 || n2>=nodes()), "try_edge - node id out of range");
      const_node_acc n;
      return n.try_edge((*data)[n1], n2, def);
   }

   bool edge_exists(int n1, int n2) const
   {
      INDEX_CHECK((n1<0 || n1>=nodes() || n2<0 || n2>=nodes()), "edge_exists - node id out of range");
      return (*data)[n1].out().exists(n2);
   }
   void create_edge(int n1, int n2, const EdgeAttr& d)
   {
      INDEX_CHECK((n1<0 || n1>=nodes() || n2<0 || n2>=nodes()), "create_edge - node id out of range");
      if (_dir==skew) {
	 node_acc n;
	 n.out_edge((*data)[n1], n2)=d;
      } else {
	 (*data)[n1].out().insert(n2,d);
      }
   }
   void delete_edge(int n1, int n2)
   {
      INDEX_CHECK((n1<0 || n1>=nodes() || n2<0 || n2>=nodes()), "delete_edge - node id out of range");
      (*data)[n1].out().erase(n2);
   }

   template <template <typename> class MasqueradeLine>
   typename edge_access<MasqueradeLine>::out::reference
   out_edges(int n)
   {
      INDEX_CHECK((n<0 || n>=nodes()), "out_edges - index out of range");
      return reinterpret_cast<typename edge_access<MasqueradeLine>::out::reference>((*data)[n].out());
   }
   template <template <typename> class MasqueradeLine>
   typename edge_access<MasqueradeLine>::out::const_reference
   out_edges(int n) const
   {
      INDEX_CHECK((n<0 || n>=nodes()), "out_edges - index out of range");
      return reinterpret_cast<typename edge_access<MasqueradeLine>::out::const_reference>((*data)[n].out());
   }

   out_edge_list_ref out_edges(int n)
   {
      return this->template out_edges<incident_edge_list>(n);
   }
   const_out_edge_list_ref out_edges(int n) const
   {
      return this->template out_edges<incident_edge_list>(n);
   }

   template <template <typename> class MasqueradeLine>
   typename edge_access<MasqueradeLine>::in::reference
   in_edges(int n)
   {
      INDEX_CHECK((n<0 || n>=nodes()), "in_edges - index out of range");
      return reinterpret_cast<typename edge_access<MasqueradeLine>::in::reference>((*data)[n].in());
   }
   template <template <typename> class MasqueradeLine>
   const typename edge_access<MasqueradeLine>::in::const_reference
   in_edges(int n) const
   {
      INDEX_CHECK((n<0 || n>=nodes()), "in_edges - index out of range");
      return reinterpret_cast<typename edge_access<MasqueradeLine>::in::const_reference>((*data)[n].in());
   }

   in_edge_list_ref in_edges(int n)
   {
      return this->template in_edges<incident_edge_list>(n);
   }
   const_in_edge_list_ref in_edges(int n) const
   {
      return this->template in_edges<incident_edge_list>(n);
   }

   out_neighbor_list_ref out_neighbors(int n)
   {
      return this->template out_edges<incidence_line>(n);
   }
   const_out_neighbor_list_ref out_neighbors(int n) const
   {
      return this->template out_edges<incidence_line>(n);
   }
   in_neighbor_list_ref in_neighbors(int n)
   {
      return this->template in_edges<incidence_line>(n);
   }
   const_in_neighbor_list_ref in_neighbors(int n) const
   {
      return this->template in_edges<incidence_line>(n);
   }
   neighbor_list_ref neighbors(int n)
   {
      typedef typename enable_if<neighbor_list, _dir!=directed>::type error_if_undefined;
      return this->template out_edges<incidence_line>(n);
   }
   const_neighbor_list_ref neighbors(int n) const
   {
      typedef typename enable_if<neighbor_list, _dir!=directed>::type error_if_undefined;
      return this->template out_edges<incidence_line>(n);
   }

protected:
   friend class alias_to_shared<Graph>;

   const shared_object<table_type>& data_member() const { return data; }

   table_type& get_table()
   {
      return const_cast<table_type&>(*(const_cast<const shared_object<table_type>&>(data)));
   }

   template <typename Iterator, typename _need_merge>
   void _copy(Iterator src, _need_merge)
   {
      for (typename Entire<out_edge_list_container>::iterator l=entire(out_edge_lists(*this));
	   !l.at_end(); ++l, ++src)
	 l->init(src->begin(), _need_merge());
   }

   template <typename Iterator, typename _need_merge>
   void _copy_conv(Iterator src, _need_merge)
   {
      for (typename Entire<out_edge_list_container>::iterator l=entire(out_edge_lists(*this));
	   !l.at_end(); ++l, ++src)
	 l->init(attach_converter<EdgeAttr>(*src).begin(), _need_merge());
   }

#ifdef POLY_DEBUG
public:
   void check(const char *prefix="") const { data->check(prefix); }
#endif
};

} // end namespace graph

template <typename NodeAttr, typename EdgeAttr, graph::kind dir>
void relocate(graph::Graph<NodeAttr,EdgeAttr,dir>* from,
	      graph::Graph<NodeAttr,EdgeAttr,dir>* to)
{
   relocate(&from->data, &to->data);
}

template <typename NodeAttr, typename EdgeAttr, graph::kind dir>
class alias_ptr< graph::Graph<NodeAttr,EdgeAttr,dir> >
   : public alias_to_shared< graph::Graph<NodeAttr,EdgeAttr,dir> > {
public:
   alias_ptr(const graph::Graph<NodeAttr,EdgeAttr,dir>* ptr_arg)
      : alias_to_shared< graph::Graph<NodeAttr,EdgeAttr,dir> >(ptr_arg) { }
};

} // end namespace pm

namespace polymake {
   using pm::graph::Graph;
}

namespace std {
   template <typename NodeAttr, typename EdgeAttr, pm::graph::kind dir> inline
   void swap(pm::graph::Graph<NodeAttr,EdgeAttr,dir>& G1, pm::graph::Graph<NodeAttr,EdgeAttr,dir>& G2)
   {
      G1.swap(G2);
   }
}

#endif // _POLYMAKE_GRAPH_H

// Local Variables:
// mode:C++
// End:
