/* Copyright (c) 1997-2004
   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,v 1.44 2004/09/20 14:25:55 gawrilow Exp $"

#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

namespace pm {

namespace graph {

enum kind { undirected, directed };

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=nothing, typename EdgeAttr=nothing, kind dir=undirected>
class Graph;
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==undirected> {
public:
   typedef sparse2d::it_traits<EdgeAttr,_out_edges,dir==undirected> traits_for_iterator;
   typedef typename traits_for_iterator::Node Node;
protected:
   mutable AVL::Ptr<Node> root_links[3];
public:
   typedef EdgeAttr data_type;

   static const bool symmetric=(dir==undirected), 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;

   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 /* =undirected */, 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 NodeAttr, typename EdgeAttr, kind _dir, restriction_kind restriction>
struct node_entry
   : public node_entry_trees<NodeAttr, EdgeAttr, _dir, restriction>,
     public node_entry_data<NodeAttr> {

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

   explicit node_entry(int index_arg)
      : node_entry_trees<node_attr, edge_attr, dir, restriction>(index_arg) { }

   template <typename Data>
   node_entry(int index_arg, const Data& node_arg)
      : node_entry_trees<node_attr, edge_attr, dir, restriction>(index_arg),
	node_entry_data<node_attr>(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::restriction_kind restriction> inline
void relocate(graph::node_entry_trees<NodeAttr,EdgeAttr,graph::undirected,restriction>* from,
	      graph::node_entry_trees<NodeAttr,EdgeAttr,graph::undirected,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==undirected);
   typedef bool2type<symmetric> sym_discr;

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

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

   template <class 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 <class 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 <class 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 <class NumberConsumer, class 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>*)0);
	       if (!symmetric) renumber_edges(t->in(), nnew, diff, (bool2type<symmetric>*)0);
	       relocate(t, t-diff);
	    }
	    ++nnew; *nc++=n;
	 } else {
	    t->~entry();
	 }
      }
      if (nnew < n) R=ruler::resize(R,nnew,false);
   }

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

   template <class 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 <class 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, true> {
   typedef unary_transform_iterator<Iterator, Accessor, true> _super;
   template <typename,typename> friend class incident_edge_iterator;
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() { }
   incident_edge_iterator(const Iterator& cur_arg, const Accessor& acc_arg=Accessor())
      : _super(cur_arg, acc_arg) { }
   incident_edge_iterator(typename alt_constructor<Iterator>::arg_type& cur_arg, const Accessor& acc_arg=Accessor())
      : _super(cur_arg, acc_arg) { }
   incident_edge_iterator(const _super& cur_arg)
      : _super(cur_arg) { }
   incident_edge_iterator(const iterator& it)
      : _super(static_cast<const typename iterator::_super&>(it)) { }

   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_modifier : unary_transform_modifier<> {
   template <typename Iterator, typename Accessor, typename ExpectedFeatures>
   struct defs
      : unary_transform_modifier<>::defs<Iterator, Accessor, ExpectedFeatures> {
      typedef incident_edge_iterator<Iterator, Accessor> iterator;
   };
};

template <typename ignored_attr>
struct edge_attr_accessor {
   typedef operations::composed11<BuildUnary<sparse2d::cell_accessor>, operations::masquerade2<ignore,ignored_attr> >
      type;
};

template <>
struct edge_attr_accessor<void> {
   typedef BuildUnary<sparse2d::cell_accessor> type;
};

template <typename Tree, typename ignored_attr=void>
class incident_edge_list
   : public modified_tree< incident_edge_list<Tree,ignored_attr>,
               cons< Hidden< Tree >,
               cons< Accessor< pair< typename edge_attr_accessor<ignored_attr>::type,
				     BuildUnaryIt<sparse2d::cell_index_accessor> > >,
		     Modifier< incident_edge_access_modifier > > >
            > {
   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*)
   {
      insert(dst,src.index());
   }

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

   template <typename Iterator>
   void _push_back(const Iterator& src, False*)
   {
      push_back(src.index());
   }

   template <typename Iterator>
   void _push_back(const Iterator& src, True*)
   {
      push_back(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, bool skip_lower>
   void init(Iterator src, bool2type<skip_lower>*)
   {
      const bool assign_data=identical<ignored_attr,void>::answer &&
	                     !identical<typename _super::iterator::value_type, nothing>::answer &&
	                     !identical<typename Iterator::value_type, nothing>::answer;
      if (skip_lower) {
	 int li=this->hidden().get_line_index();
	 for (; !src.at_end() && src.index()<li; ++src) ;
      }
      for (; !src.at_end(); ++src)
	 _push_back(src, (bool2type<assign_data>*)0);
   }

   template <typename Iterator>
   void copy(Iterator src)
   {
      const bool assign_data=identical<ignored_attr,void>::answer &&
	                     !identical<typename _super::iterator::value_type, nothing>::answer &&
	                     !identical<typename iterator_traits<Iterator>::value_type, nothing>::answer;
      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) erase(dst++);
	    else         break;
	    idiff=1;
	 }
	 if (idiff>0) _insert(dst, src, (bool2type<assign_data>*)0);
	 else         _assign(dst, src, (bool2type<assign_data>*)0);
      }
      while (!dst.at_end()) erase(dst++);
   }

   template <typename Iterator>
   void merge(Iterator src)
   {
      const bool assign_data=identical<ignored_attr,void>::answer &&
	                     !identical<typename _super::iterator::value_type, nothing>::answer &&
	                     !identical<typename iterator_traits<Iterator>::value_type, nothing>::answer;
      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, (bool2type<assign_data>*)0);
      }
   }

#if defined(__APPLE__)
   template <typename Iterator>
   void input(Iterator inp)
   {
      init(inp, (bool2type<Tree::symmetric>*)0);
   }
#endif
public:
   template <typename Input> friend
   Input& operator>> (GenericInput<Input>& is, incident_edge_list& l)
   {
#if defined(__APPLE__)
      l.input(is.top().create_sparse_input_iterator(&l));
#else
      l.init(is.top().create_sparse_input_iterator(&l), (bool2type<Tree::symmetric>*)0);
#endif
      return is.top();
   }

   int dim() const { return this->max_size(); }

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

   template <typename,typename,kind> friend class Graph;

   template <typename Output> friend
   Output& operator<< (GenericOutput<Output>& os, const incident_edge_list& l)
   {
      return os.top() << as_list(indexed_pairs(l));
   }
};

template <typename Tree>
class full_incident_edge_list : public incident_edge_list<Tree> { };

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>,
	       cons<Hidden< incident_edge_list<Tree> >,
	       cons<Modifier< input_truncator_modifier >,
		    Accessor< BuildUnaryIt<lower_edge_predicate> > > >
           > { };

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

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

   typedef typename deref<EntryRef>::type::out_tree_type out_tree_type;
   typedef typename deref<EntryRef>::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_neighbors_list;
   typedef incidence_line<in_tree_type> in_neighbors_list;
   typedef out_neighbors_list neighbors_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_neighbors_list, EntryRef>::type out_neighbors_list_ref;
   typedef typename inherit_ref<in_neighbors_list, EntryRef>::type in_neighbors_list_ref;
   typedef out_neighbors_list_ref neighbors_list_ref;
   typedef typename inherit_ref<typename deref<EntryRef>::type::edge_attr, EntryRef>::type edge_attr_ref;

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

   edge_attr_ref out_edge(argument_type t, int n2, True*) const
   {
      typename out_edge_list::const_iterator e=t.out().find(n2);
      if (e.at_end()) throw no_match("non-existing edge");
      return e->get_data();
   }
   edge_attr_ref in_edge(argument_type t, int n2, True*) const
   {
      typename in_edge_list::const_iterator e=t.in().find(n2);
      if (e.at_end()) throw no_match("non-existing edge");
      return e->get_data();
   }
   edge_attr_ref out_edge(argument_type t, int n2, False*) const
   {
      return t.out().insert(n2)->get_data();
   }
   edge_attr_ref in_edge(argument_type t, int n2, False*) const
   {
      return t.in().insert(n2)->get_data();
   }
   edge_attr_ref out_edge(argument_type t, int n2) const
   {
      return out_edge(t,n2,(bool2type<attrib<EntryRef>::is_const>*)0);
   }
   edge_attr_ref in_edge(argument_type t, int n2) const
   {
      return in_edge(t,n2,(bool2type<attrib<EntryRef>::is_const>*)0);
   }

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

   out_neighbors_list_ref out_neighbors(argument_type t) const
   {
      return reinterpret_cast<out_neighbors_list_ref>(t.out());
   }
   in_neighbors_list_ref in_neighbors(argument_type t) const
   {
      return reinterpret_cast<in_neighbors_list_ref>(t.in());
   }
   neighbors_list_ref neighbors(argument_type t) const
   {
      return reinterpret_cast<neighbors_list_ref>(t.out());
   }
};

template <typename Iterator, typename Accessor>
struct node_iterator : public unary_transform_iterator<Iterator, Accessor, true> {
   typedef unary_transform_iterator<Iterator, Accessor, true> _super;
   template <typename,typename> friend class node_iterator;
protected:
   typedef typename _super::helper::star star;
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() { }
   node_iterator(const Iterator& cur_arg, const Accessor& acc_arg=Accessor())
      : _super(cur_arg,acc_arg) { }
   node_iterator(typename alt_constructor<Iterator>::arg_type& cur_arg, const Accessor& acc_arg=Accessor())
      : _super(cur_arg,acc_arg) { }
   node_iterator(const _super& cur_arg)
      : _super(cur_arg) { }
   node_iterator(const iterator& it)
      : _super(static_cast<const typename iterator::_super&>(it)) { }

   typename _super::helper::operation::out_edge_list_ref out_edges() const
   {
      return this->op.out_edges(star::get(*this));
   }
   typename _super::helper::operation::in_edge_list_ref in_edges() const
   {
      return this->op.in_edges(star::get(*this));
   }

   typename _super::helper::operation::edge_attr_ref out_edge(int n2) const
   {
      return this->op.out_edge(star::get(*this), n2);
   }
   typename _super::helper::operation::edge_attr_ref in_edge(int n2) const
   {
      return this->op.in_edge(star::get(*this), n2);
   }
   typename _super::helper::operation::edge_attr_ref edge(int n2) const
   {
      return this->op.out_edge(star::get(*this), n2);
   }

   int out_degree() const
   {
      return this->op.out_degree(star::get(*this));
   }
   int in_degree() const
   {
      return this->op.in_degree(star::get(*this));
   }
   int degree() const
   {
      return this->op.degree(star::get(*this));
   }

   typename _super::helper::operation::out_neighbors_list_ref out_neighbors() const
   {
      return this->op.out_neighbors(star::get(*this));
   }
   typename _super::helper::operation::in_neighbors_list_ref in_neighbors() const
   {
      return this->op.in_neighbors(star::get(*this));
   }
   typename _super::helper::operation::neighbors_list_ref neighbors() const
   {
      return this->op.neighbors(star::get(*this));
   }
};

struct node_access_modifier : unary_transform_modifier<> {
   template <class Iterator, class Accessor, class ExpectedFeatures>
   struct defs : unary_transform_modifier<>::defs<Iterator,Accessor,ExpectedFeatures> {
      typedef node_iterator<Iterator,Accessor> iterator;
   };
};

template <class _Table>
class node_container
   : public modified_container_impl< node_container<_Table>,
               cons< Container< typename _Table::ruler >,
               cons< Accessor< pair< BuildUnary<node_accessor>, BuildUnary<sparse2d::line_index_accessor> > >,
	       cons< Modifier< node_access_modifier >,
		     Hidden< _Table > > > >
     > {
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(); }
};
} // 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, true>, Feature> { };

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

namespace graph {
template <typename EntryRef, bool _out_edges, template <typename> class MasqueradeLine>
class line_factory {
public:
   typedef typename attrib<EntryRef>::plus_ref argument_type;
   typedef typename if_else<_out_edges, typename deref<EntryRef>::type::out_tree_type,
			                typename deref<EntryRef>::type::in_tree_type>::result
      tree_type;
   typedef typename inherit_ref<MasqueradeLine<tree_type>, argument_type>::type result_type;

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

template <bool _out_edges, template <typename> class MasqueradeLine> struct BuildLine { };

} // end namespace graph

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

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>,
               cons< Container< typename _Table::ruler >,
	       cons< Accessor< pair< BuildLine<_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,full_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>,
	       cons< Hidden< typename edge_container_helper<_Table>::type >,
		     CascadeDepth< int2type<2> > >
            > {
protected:
   ~edge_container();
};

template <typename Entry, typename apparent_attrs>
struct composite_node_entry : public Entry {
protected:
   composite_node_entry();
   ~composite_node_entry();
};

template <typename Entry, typename NodeAttr, typename ExpectedNodeAttr, typename EdgeAttr>
struct composite_node_entry<Entry, cons<ignore<NodeAttr,ExpectedNodeAttr>, EdgeAttr> > : public Entry {
protected:
   composite_node_entry();
   ~composite_node_entry();
public:
   ignore<NodeAttr,ExpectedNodeAttr>& get_node_attr()
   {
      return reinterpret_cast<ignore<NodeAttr,ExpectedNodeAttr>&>(Entry::get_node_attr());
   }
   const ignore<NodeAttr,ExpectedNodeAttr>& get_node_attr() const
   {
      return reinterpret_cast<const ignore<NodeAttr,ExpectedNodeAttr>&>(Entry::get_node_attr());
   }
};

template <typename _Table, typename apparent_attrs>
class composite_container
   : public modified_container_impl< composite_container<_Table, apparent_attrs>,
               cons< Container< typename _Table::ruler >,
	       cons< Accessor< operations::masquerade2<composite_node_entry, apparent_attrs> >,
		     Hidden< _Table > > >
            > {
protected:
   ~composite_container();
public:
   typename composite_container::container& get_container() { return this->hidden().get_ruler(); }
   const typename composite_container::container& get_container() const { return this->hidden().get_ruler(); }

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

} // end namespace graph

template <typename Tree, typename ignored_attr>
struct spec_object_traits< graph::incident_edge_list<Tree, ignored_attr> >
   : spec_object_traits<is_container> {
   static const IO_separator_kind IO_separator=IO_sep_inherit;
};

template <typename Entry, typename NodeAttr, typename EdgeAttr>
struct spec_object_traits< graph::composite_node_entry<Entry, cons<NodeAttr, EdgeAttr> > >
   : spec_object_traits<is_composite> {
   typedef graph::incident_edge_list<typename Entry::out_tree_type, typename unveil_ignore<EdgeAttr>::expected_type> edge_list;
   typedef cons<NodeAttr, edge_list> elements;

   template <typename Me, typename Visitor>
   static void visit_elements(Me& t, Visitor& v)
   {
      v << t.get_node_attr()
	<< reinterpret_cast<typename inherit_const<edge_list, Me>::type&>(t.out());
   }
};

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); }

   template <typename Input> friend
   Input& operator>> (GenericInput<Input>& is, neighborhood& N)
   {
      return is.top() >> pm::rows(N);
   }
};
} // 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> inline
typename Graph<NodeAttr,EdgeAttr,dir>::node_container&
nodes(Graph<NodeAttr,EdgeAttr,dir>& G)
{
   return G.template pretend<typename Graph<NodeAttr,EdgeAttr,dir>::node_container>();
}

template <typename NodeAttr, typename EdgeAttr, kind dir> inline
const typename Graph<NodeAttr,EdgeAttr,dir>::node_container&
nodes(const Graph<NodeAttr,EdgeAttr,dir>& G)
{
   return G.template pretend<typename Graph<NodeAttr,EdgeAttr,dir>::node_container>();
}

template <typename NodeAttr, typename EdgeAttr, kind dir> inline
typename Graph<NodeAttr,EdgeAttr,dir>::edge_container&
edges(Graph<NodeAttr,EdgeAttr,dir>& G)
{
   return G.template pretend<typename Graph<NodeAttr,EdgeAttr,dir>::edge_container>();
}

template <typename NodeAttr, typename EdgeAttr, kind dir> inline
const typename Graph<NodeAttr,EdgeAttr,dir>::edge_container&
edges(const Graph<NodeAttr,EdgeAttr,dir>& G)
{
   return G.template pretend<typename Graph<NodeAttr,EdgeAttr,dir>::edge_container>();
}

template <template <typename> class MasqueradeLine, typename NodeAttr, typename EdgeAttr, kind dir> inline
typename Graph<NodeAttr,EdgeAttr,dir>::template edge_access<MasqueradeLine>::out_edge_list_container&
out_edge_lists(Graph<NodeAttr,EdgeAttr,dir>& G)
{
   return G.template pretend<typename Graph<NodeAttr,EdgeAttr,dir>::template edge_access<MasqueradeLine>::out_edge_list_container>();
}

template <template <typename> class MasqueradeLine, typename NodeAttr, typename EdgeAttr, kind dir> inline
const typename Graph<NodeAttr,EdgeAttr,dir>::template edge_access<MasqueradeLine>::out_edge_list_container&
out_edge_lists(const Graph<NodeAttr,EdgeAttr,dir>& G)
{
   return G.template pretend<typename Graph<NodeAttr,EdgeAttr,dir>::template edge_access<MasqueradeLine>::out_edge_list_container>();
}

template <template <typename> class MasqueradeLine, typename NodeAttr, typename EdgeAttr, kind dir> inline
typename Graph<NodeAttr,EdgeAttr,dir>::template edge_access<MasqueradeLine>::in_edge_list_container&
in_edge_lists(Graph<NodeAttr,EdgeAttr,dir>& G)
{
   return G.template pretend<typename Graph<NodeAttr,EdgeAttr,dir>::template edge_access<MasqueradeLine>::in_edge_list_container>();
}

template <template <typename> class MasqueradeLine, typename NodeAttr, typename EdgeAttr, kind dir> inline
const typename Graph<NodeAttr,EdgeAttr,dir>::template edge_access<MasqueradeLine>::in_edge_list_container&
in_edge_lists(const Graph<NodeAttr,EdgeAttr,dir>& G)
{
   return G.template pretend<typename Graph<NodeAttr,EdgeAttr,dir>::template edge_access<MasqueradeLine>::in_edge_list_container>();
}

template <typename NodeAttr, typename EdgeAttr, kind dir> inline
Graph< ignore<typename unveil_ignore<NodeAttr>::type>, EdgeAttr, dir>&
ignore_node_attrs(Graph<NodeAttr,EdgeAttr,dir>& G)
{
   return reinterpret_cast<Graph<ignore<typename unveil_ignore<NodeAttr>::type>, EdgeAttr, dir>&>(G);
}

template <typename NodeAttr, typename EdgeAttr, kind dir> inline
const Graph< ignore<typename unveil_ignore<NodeAttr>::type>, EdgeAttr, dir>&
ignore_node_attrs(const Graph<NodeAttr,EdgeAttr,dir>& G)
{
   return reinterpret_cast<const Graph<ignore<typename unveil_ignore<NodeAttr>::type>, EdgeAttr, dir>&>(G);
}

template <typename ExpectedNodeAttr, typename NodeAttr, typename EdgeAttr, kind dir> inline
Graph< ignore<typename unveil_ignore<NodeAttr>::type,ExpectedNodeAttr>, EdgeAttr, dir>&
ignore_node_attrs(Graph<NodeAttr,EdgeAttr,dir>& G)
{
   return reinterpret_cast<Graph<ignore<typename unveil_ignore<NodeAttr>::type,ExpectedNodeAttr>, EdgeAttr, dir>&>(G);
}

template <typename ExpectedNodeAttr, typename NodeAttr, typename EdgeAttr, kind dir> inline
const Graph<ignore<typename unveil_ignore<NodeAttr>::type,ExpectedNodeAttr>, EdgeAttr, dir>&
ignore_node_attrs(const Graph<NodeAttr,EdgeAttr,dir>& G)
{
   return reinterpret_cast<const Graph<ignore<typename unveil_ignore<NodeAttr>::type,ExpectedNodeAttr>, EdgeAttr, dir>&>(G);
}

template <typename NodeAttr, typename EdgeAttr, kind dir> inline
Graph<NodeAttr, ignore<typename unveil_ignore<EdgeAttr>::type>, dir>&
ignore_edge_attrs(Graph<NodeAttr,EdgeAttr,dir>& G)
{
   return reinterpret_cast<Graph<NodeAttr, ignore<typename unveil_ignore<EdgeAttr>::type>, dir>&>(G);
}

template <typename NodeAttr, typename EdgeAttr, kind dir> inline
const Graph<NodeAttr, ignore<typename unveil_ignore<EdgeAttr>::type>, dir>&
ignore_edge_attrs(const Graph<NodeAttr,EdgeAttr,dir>& G)
{
   return reinterpret_cast<const Graph<NodeAttr, ignore<typename unveil_ignore<EdgeAttr>::type>, dir>&>(G);
}

template <typename ExpectedEdgeAttr, typename NodeAttr, typename EdgeAttr, kind dir> inline
Graph<NodeAttr, ignore<typename unveil_ignore<EdgeAttr>::type,ExpectedEdgeAttr>, dir>&
ignore_edge_attrs(Graph<NodeAttr,EdgeAttr,dir>& G)
{
   return reinterpret_cast<Graph<NodeAttr, ignore<typename unveil_ignore<EdgeAttr>::type,ExpectedEdgeAttr>, dir>&>(G);
}

template <typename ExpectedEdgeAttr, typename NodeAttr, typename EdgeAttr, kind dir> inline
const Graph<NodeAttr, ignore<typename unveil_ignore<EdgeAttr>::type,ExpectedEdgeAttr>, dir>&
ignore_edge_attrs(const Graph<NodeAttr,EdgeAttr,dir>& G)
{
   return reinterpret_cast<const Graph<NodeAttr, ignore<typename unveil_ignore<EdgeAttr>::type,ExpectedEdgeAttr>, dir>&>(G);
}

template <typename NodeAttr, typename EdgeAttr, kind dir> inline
Graph<ignore<typename unveil_ignore<NodeAttr>::type>, ignore<typename unveil_ignore<EdgeAttr>::type>, dir>&
ignore_attrs(Graph<NodeAttr,EdgeAttr,dir>& G)
{
   return reinterpret_cast<Graph<ignore<typename unveil_ignore<NodeAttr>::type>, ignore<typename unveil_ignore<EdgeAttr>::type>, dir>&>(G);
}

template <typename NodeAttr, typename EdgeAttr, kind dir> inline
const Graph<ignore<typename unveil_ignore<NodeAttr>::type>, ignore<typename unveil_ignore<EdgeAttr>::type>, dir>&
ignore_attrs(const Graph<NodeAttr,EdgeAttr,dir>& G)
{
   return reinterpret_cast<const Graph<ignore<typename unveil_ignore<NodeAttr>::type>, ignore<typename unveil_ignore<EdgeAttr>::type>, dir>&>(G);
}

template <typename ExpectedNodeAttr, typename ExpectedEdgeAttr, typename NodeAttr, typename EdgeAttr, kind dir> inline
Graph<ignore<typename unveil_ignore<NodeAttr>::type,ExpectedNodeAttr>, ignore<typename unveil_ignore<EdgeAttr>::type,ExpectedEdgeAttr>, dir>&
ignore_attrs(Graph<NodeAttr,EdgeAttr,dir>& G)
{
   return reinterpret_cast<Graph<ignore<typename unveil_ignore<NodeAttr>::type,ExpectedNodeAttr>, ignore<typename unveil_ignore<EdgeAttr>::type,ExpectedEdgeAttr>, dir>&>(G);
}

template <typename ExpectedNodeAttr, typename ExpectedEdgeAttr, typename NodeAttr, typename EdgeAttr, kind dir> inline
const Graph<ignore<typename unveil_ignore<NodeAttr>::type,ExpectedNodeAttr>, ignore<typename unveil_ignore<EdgeAttr>::type,ExpectedEdgeAttr>, dir>&
ignore_attrs(const Graph<NodeAttr,EdgeAttr,dir>& G)
{
   return reinterpret_cast<const Graph<ignore<typename unveil_ignore<NodeAttr>::type,ExpectedNodeAttr>, ignore<typename unveil_ignore<EdgeAttr>::type,ExpectedEdgeAttr>, dir>&>(G);
}

template <typename NodeAttr, typename EdgeAttr, kind dir>
class Graph {
public:
   typedef typename unveil_ignore<NodeAttr>::type node_attr;
   typedef typename unveil_ignore<EdgeAttr>::type edge_attr;
protected:
   typedef Table<node_attr, edge_attr, dir> table_type;
   shared_object<table_type> data;

public:
   typedef typename table_type::sym_discr sym_discr;
   typedef graph::node_container<table_type> node_container;
   typedef graph::edge_container<table_type> edge_container;
   typedef graph::composite_container<table_type, cons<NodeAttr, EdgeAttr> > composite_container;
   typedef typename composite_container::value_type value_type;
   typedef graph::neighborhood<table_type> neighborhood;

   template <template <typename> class MasqueradeLine>
   struct edge_access {
      typedef line_container<table_type, true, MasqueradeLine> out_edge_list_container;
      typedef line_container<table_type, false, MasqueradeLine> in_edge_list_container;
      typedef typename out_edge_list_container::value_type out_edge_list;
      typedef typename in_edge_list_container::value_type in_edge_list;
   };

   typedef edge_access<full_incident_edge_list> default_edge_access;
   typedef typename default_edge_access::out_edge_list_container out_edge_list_container;
   typedef typename default_edge_access::in_edge_list_container in_edge_list_container;
   typedef typename default_edge_access::out_edge_list out_edge_list;
   typedef typename default_edge_access::in_edge_list in_edge_list;
   typedef typename edge_access<incidence_line>::out_edge_list out_neighbors_list;
   typedef typename edge_access<incidence_line>::in_edge_list in_neighbors_list;
   typedef out_neighbors_list neighbors_list;

   Graph() { }

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

   template <typename NodeAttr2, typename EdgeAttr2, kind dir2>
   explicit Graph(const Graph<NodeAttr2,EdgeAttr2,dir2>& G2)
      : data( make_constructor(G2.nodes(), attach_converter<NodeAttr>(graph::nodes(G2)).begin(), (table_type*)0) )
   {
      _copy(G2, (sym_discr*)0);
   }

   template <typename NodeAttr2, typename EdgeAttr2, kind dir2>
   Graph& operator= (const Graph<NodeAttr2,EdgeAttr2,dir2>& G2)
   {
      data=make_constructor(G2.nodes(), attach_converter<NodeAttr>(graph::nodes(G2)).begin(), (table_type*)0);
      _copy(G2, (sym_discr*)0);
      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);
   }

   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*)0);
   }

   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*)0);
   }

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

   friend
   out_edge_list_container& out_edge_lists(Graph& G)
   {
      return out_edge_lists<full_incident_edge_list>(G);
   }
   friend
   const out_edge_list_container& out_edge_lists(const Graph& G)
   {
      return out_edge_lists<full_incident_edge_list>(G);
   }

   friend
   in_edge_list_container& in_edge_lists(Graph& G)
   {
      return in_edge_lists<full_incident_edge_list>(G);
   }
   friend
   const in_edge_list_container& in_edge_lists(const Graph& G)
   {
      return in_edge_lists<full_incident_edge_list>(G);
   }

   friend
   composite_container& composite(Graph& G)
   {
      return reinterpret_cast<composite_container&>(*G.data);
   }
   friend
   const composite_container& composite(const Graph& G)
   {
      return reinterpret_cast<const composite_container&>(*G.data);
   }

   friend
   neighborhood& neighborhood_matrix(Graph& G)
   {
      return reinterpret_cast<neighborhood&>(*G.data);
   }
   friend
   const neighborhood& neighborhood_matrix(const Graph& G)
   {
      return reinterpret_cast<const neighborhood&>(*G.data);
   }

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

   edge_attr& edge(int n1, int n2)
   {
      INDEX_CHECK((n1<0 || n1>=nodes() || n2<0 || n2>=nodes()), "edge - node id out of range");
      return (*data)[n1].out().insert(n2)->get_data();
   }
   const edge_attr& edge(int n1, int n2) const
   {
      INDEX_CHECK((n1<0 || n1>=nodes() || n2<0 || n2>=nodes()), "edge - node id out of range");
      typename out_edge_list::const_iterator e=(*data)[n1].out().find(n2);
      if (e.at_end()) throw no_match("non-existing edge");
      return e->get_data();
   }
   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 edge_attr& d)
   {
      INDEX_CHECK((n1<0 || n1>=nodes() || n2<0 || n2>=nodes()), "create_edge - node id out of range");
      (*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_edge_list&
   out_edges(int n)
   {
      INDEX_CHECK((n<0 || n>=nodes()), "out_edges - index out of range");
      return reinterpret_cast<typename edge_access<MasqueradeLine>::out_edge_list&>((*data)[n].out());
   }
   template <template <typename> class MasqueradeLine>
   const typename edge_access<MasqueradeLine>::out_edge_list&
   out_edges(int n) const
   {
      INDEX_CHECK((n<0 || n>=nodes()), "out_edges - index out of range");
      return reinterpret_cast<const typename edge_access<MasqueradeLine>::out_edge_list&>((*data)[n].out());
   }
   out_edge_list& out_edges(int n)
   {
      return this->template out_edges<full_incident_edge_list>(n);
   }
   const out_edge_list& out_edges(int n) const
   {
      return this->template out_edges<full_incident_edge_list>(n);
   }

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

   out_neighbors_list& out_neighbors(int n)
   {
      return this->template out_edges<incidence_line>(n);
   }
   const out_neighbors_list& out_neighbors(int n) const
   {
      return this->template out_edges<incidence_line>(n);
   }
   in_neighbors_list& in_neighbors(int n)
   {
      return this->template in_edges<incidence_line>(n);
   }
   const in_neighbors_list& in_neighbors(int n) const
   {
      return this->template in_edges<incidence_line>(n);
   }
   neighbors_list& neighbors(int n)
   {
      return this->template out_edges<incidence_line>(n);
   }
   const neighbors_list& neighbors(int n) const
   {
      return this->template out_edges<incidence_line>(n);
   }

protected:
   // any -> directed
   template <typename NodeAttr2, typename EdgeAttr2, kind dir2>
   void _copy(const Graph<NodeAttr2,EdgeAttr2,dir2>& G2, False*)
   {
      typename Graph<NodeAttr2,EdgeAttr2,dir2>::out_edge_list_container::const_iterator l2=out_edge_lists(G2).begin();
      for (typename Entire<out_edge_list_container>::iterator l=entire(out_edge_lists(*this));
	   !l.at_end(); ++l, ++l2)
	 l->init(l2->begin(), (False*)0);
   }

   // undirected -> undirected
   template <typename NodeAttr2, typename EdgeAttr2>
   void _copy(const Graph<NodeAttr2,EdgeAttr2,undirected>& G2, True*)
   {
      typename Graph<NodeAttr2,EdgeAttr2,undirected>::out_edge_list_container::const_iterator l2=out_edge_lists(G2).begin();
      for (typename Entire<out_edge_list_container>::iterator l=entire(out_edge_lists(*this));
	   !l.at_end(); ++l, ++l2)
	 l->init(l2->find_nearest(l2.index(), polymake::operations::ge()), (False*)0);
   }

   // directed -> undirected
   template <typename NodeAttr2, typename EdgeAttr2>
   void _copy(const Graph<NodeAttr2,EdgeAttr2,directed>& G2, True*)
   {
      typename Graph<NodeAttr2,EdgeAttr2,directed>::out_edge_list_container::const_iterator l2=out_edge_lists(G2).begin();
      for (typename Entire<out_edge_list_container>::iterator l=entire(out_edge_lists(*this));
	   !l.at_end(); ++l, ++l2)
	 l->merge(l2->begin());
   }

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)));
   }

public:
   template <typename Input> friend
   Input& operator>> (GenericInput<Input>& is, Graph& G)
   {
      return is.top() >> composite(G);
   }

   /// In the undirected case each non-loop edge occurs twice.
   template <typename Output> friend
   Output& operator<< (GenericOutput<Output>& os, const Graph& G)
   {
      return os.top() << composite(G);
   }

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

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

#ifdef POLY_DEBUG
   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) { }
};

template <typename NodeAttr, typename EdgeAttr, graph::kind dir>
struct spec_object_traits< graph::Graph<NodeAttr,EdgeAttr,dir> >
   : spec_object_traits< typename graph::Graph<NodeAttr,EdgeAttr,dir>::composite_container > { };

template <typename _Graph>
class Nodes : public _Graph::node_container {
protected:
   Nodes();
   ~Nodes();
};

template <typename _Graph>
class Edges : public _Graph::edge_container {
protected:
   Edges();
   ~Edges();
};

template <typename _Graph>
class NodeNeighborhood : public _Graph::neighborhood {
protected:
   NodeNeighborhood();
   ~NodeNeighborhood();
};

} // end namespace pm

namespace polymake {
   using pm::graph::Graph;
   using pm::graph::directed;
   using pm::graph::undirected;
   using pm::Nodes;
   using pm::Edges;
   using pm::NodeNeighborhood;
   using pm::graph::ignore_attrs;
   using pm::graph::ignore_node_attrs;
   using pm::graph::ignore_edge_attrs;
}

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:
