/* 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_INDEXED_SUBGRAPH_H
#define _POLYMAKE_INDEXED_SUBGRAPH_H "$Project: polymake $$Id: IndexedSubgraph.h,v 1.6 2006/03/09 16:21:35 gawrilow Exp $"

#ifndef _POLYMAKE_INDEXED_SUBSET_H
#  include <IndexedSubset.h>
#endif
#ifndef _POLYMAKE_GENERIC_SET_H
#  include <GenericSubset.h>
#endif
#ifndef _POLYMAKE_GENERIC_GRAPH_H
#  include <GenericGraph.h>
#endif
#ifndef _POLYMAKE_GENERIC_GRAPH_H
#  include <GenericIncidenceMatrix.h>
#endif
#ifndef _POLYMAKE_MATRIX_METHODS_H
#  include <matrix_methods.h>
#endif

namespace pm {

template <typename IteratorPair, typename Operation>
class subgraph_node_iterator : public IteratorPair {
   typedef IteratorPair _super;
public:
   typedef subgraph_node_iterator<typename iterator_traits<IteratorPair>::iterator, Operation>
      iterator;
   typedef subgraph_node_iterator<typename iterator_traits<IteratorPair>::const_iterator, Operation>
      const_iterator;

   typedef binary_helper<IteratorPair,Operation> helper;
   typedef typename helper::operation operation;
protected:
   operation op;
public:
   subgraph_node_iterator() { }

   template <typename Operation2>
   subgraph_node_iterator(const subgraph_node_iterator<typename iterator_traits<IteratorPair>::iterator, Operation2>& it)
      : _super(it), op(helper::create(it.op)) { }

   subgraph_node_iterator(const IteratorPair& it_arg, const Operation& op_arg=Operation())
      : _super(it_arg), op(helper::create(op_arg)) { }

   subgraph_node_iterator(const typename IteratorPair::first_type& first_arg,
			  const typename IteratorPair::second_type& second_arg,
			  const Operation& op_arg=Operation())
      : _super(first_arg,second_arg), op(helper::create(op_arg)) { }
   subgraph_node_iterator(const typename IteratorPair::first_type& first_arg,
			  typename alt_constructor<typename IteratorPair::second_type>::arg_type& second_arg,
			  const Operation& op_arg=Operation())
      : _super(first_arg,second_arg), op(helper::create(op_arg)) { }
   subgraph_node_iterator(typename alt_constructor<typename IteratorPair::first_type>::arg_type& first_arg,
			  const typename IteratorPair::second_type& second_arg,
			  const Operation& op_arg=Operation())
      : _super(first_arg,second_arg), op(helper::create(op_arg)) { }
   subgraph_node_iterator(typename alt_constructor<typename IteratorPair::first_type>::arg_type& first_arg,
			  typename alt_constructor<typename IteratorPair::second_type>::arg_type& second_arg,
			  const Operation& op_arg=Operation())
      : _super(first_arg,second_arg), op(helper::create(op_arg)) { }

   typedef typename operation::out_edge_list out_edge_list_ref;
   typedef typename operation::in_edge_list in_edge_list_ref;
   typedef typename operation::out_neighbor_list out_neighbor_list_ref;
   typedef typename operation::in_neighbor_list in_neighbor_list_ref;

   out_edge_list_ref out_edges() const
   {
      return op.out_edges(*this, *helper::get2(this->second));
   }
   in_edge_list_ref in_edges() const
   {
      return op.in_edges(*this, *helper::get2(this->second));
   }

   int out_degree() const
   {
      return op.out_degree(*this, *helper::get2(this->second));
   }
   int in_degree() const
   {
      return op.in_degree(*this, *helper::get2(this->second));
   }

   out_neighbor_list_ref out_neighbors() const
   {
      return op.out_neighbors(*this, *helper::get2(this->second));
   }
   in_neighbor_list_ref in_neighbors() const
   {
      return op.in_neighbors(*this, *helper::get2(this->second));
   }
};

struct subgraph_node_access_modifier : binary_transform_modifier<> {
   template <typename IteratorPair, typename Operation, typename ExpectedFeatures>
   struct defs : binary_transform_modifier<>::defs<IteratorPair,Operation,ExpectedFeatures> {
      typedef subgraph_node_iterator<IteratorPair,Operation> iterator;
   };
};

template <typename GraphRef, typename SetRef, typename Traits>
class NeighborhoodSubset;

template <typename GraphRef, typename SetRef, typename Traits>
class IndexedSubgraph_base
   : public container_pair_base<GraphRef, typename prevent_lazy<SetRef>::type> {
   typedef container_pair_base<GraphRef, typename prevent_lazy<SetRef>::type> _base;
public:
   typedef typename deref<GraphRef>::type graph_type;
   typedef typename deref<SetRef>::type node_set_type;
protected:
   static const bool renumber_nodes=extract_bool_param<Traits,Renumber>::result;

   typename inherit_const<graph_type, GraphRef>::type& get_graph() { return _base::get_container1(); }
   const graph_type& get_graph() const { return _base::get_container1(); }
   typename attrib<typename prevent_lazy<SetRef>::type>::plus_const_ref get_node_set() const { return _base::get_container2(); }

   IndexedSubgraph_base(typename _base::first_arg_type graph_arg, typename alias<SetRef>::arg_type node_set_arg)
      : _base(graph_arg, prevent_lazy<SetRef>::get(node_set_arg)) { }

   typedef typename concat_list< Hidden<IndexedSubgraph_base>,
				 typename extract_type_param<Traits,Renumber>::result >::result
      node_selector_traits;

   template <typename Source>
   class node_selector
      : public indexed_subset_impl< node_selector<Source>,
				    cons< Container1< Source >,
				    cons< Container2< SetRef >,
					  node_selector_traits > >
               > {
      typedef indexed_subset_impl<node_selector> _super;
   public:
      typename _super::container1& get_container1()
      {
	 return this->hidden().get_graph().template pretend<typename _super::container1&>();
      }
      const typename _super::container1& get_container1() const
      {
	 return this->hidden().get_graph().template pretend<const typename _super::container1&>();
      }
      const node_set_type& get_container2() const
      {
	 return this->hidden().get_node_set();
      }
   };

   template <typename Source, typename AddTraits>
   class masquerade_container
      : public modified_container_pair_impl< masquerade_container<Source,AddTraits>,
		  cons< Container1< node_selector<Source> >,
		  cons< Container2< unlimited_constant_container<typename attrib<SetRef>::plus_const_ref> >,
		  cons< Hidden< IndexedSubgraph_base >,
			AddTraits > > >
               > {
      typedef modified_container_pair_impl<masquerade_container> _super;
   public:
      const typename _super::container2& get_container2() const
      {
	 return constant(this->hidden().get_node_set());
      }
   };

   typedef typename if_else<renumber_nodes,
			    operations::construct_binary<IndexedSlice>,
			    operations::construct_binary<IndexedSubset> >::result
      edge_list_operation;
   typedef typename if_else<renumber_nodes,
			    operations::construct_binary<IndexedSlice>,
			    operations::construct_binary2<LazySet2, set_intersection_zipper> >::result
      neighbor_list_operation;

   template <typename Iterator>
   struct node_accessor {
      typedef Iterator first_argument_type;
      typedef SetRef second_argument_type;
      typedef typename function_argument<SetRef>::const_type second_arg_type;
      typedef typename iterator_traits<Iterator>::reference result_type;

      typedef typename binary_op_builder<edge_list_operation, void, void,
					 typename Iterator::out_edge_list_ref, SetRef>::operation::result_type
         out_edge_list;
      typedef typename binary_op_builder<edge_list_operation, void, void,
					 typename Iterator::in_edge_list_ref, SetRef>::operation::result_type
         in_edge_list;

      typedef typename binary_op_builder<neighbor_list_operation, void, void,
					 typename Iterator::out_neighbor_list_ref, SetRef>::operation::result_type
         out_neighbor_list;
      typedef typename binary_op_builder<neighbor_list_operation, void, void,
					 typename Iterator::in_neighbor_list_ref, SetRef>::operation::result_type
         in_neighbor_list;

      out_edge_list out_edges(const Iterator& it, second_arg_type set) const
      {
	 return out_edge_list(it.out_edges(),set);
      }
      in_edge_list in_edges(const Iterator& it, second_arg_type set) const
      {
	 return in_edge_list(it.in_edges(),set);
      }
      out_neighbor_list out_neighbors(const Iterator& it, second_arg_type set) const
      {
	 return out_neighbor_list(it.out_neighbors(),set);
      }
      in_neighbor_list in_neighbors(const Iterator& it, second_arg_type set) const
      {
	 return in_neighbor_list(it.in_neighbors(),set);
      }
      int out_degree(const Iterator& it, second_arg_type set) const
      {
	 return out_edges(it,set).size();
      }
      int in_degree(const Iterator& it, second_arg_type set) const
      {
	 return in_edges(it,set).size();
      }
   };

   template <typename Source>
   class masquerade_node_container
      : public masquerade_container<Source,
		  cons< Accessor< node_accessor<typename container_traits<Source>::iterator> >,
			Modifier< subgraph_node_access_modifier > >
               > { };
public:
   typedef masquerade_node_container<typename if_else<attrib<GraphRef>::is_const,
						      typename graph_type::const_node_container_ref,
						      typename graph_type::node_container_ref>::result>
      node_container;
   typedef masquerade_node_container<typename graph_type::const_node_container_ref>
      const_node_container;
   typedef typename inherit_const<node_container, GraphRef>::type& node_container_ref;
   typedef const const_node_container& const_node_container_ref;

   typedef masquerade_container<typename if_else<attrib<GraphRef>::is_const,
						 typename graph_type::const_out_edge_list_container_ref,
						 typename graph_type::out_edge_list_container_ref>::result,
				Accessor< edge_list_operation > >
      out_edge_list_container;
   typedef masquerade_container<typename graph_type::const_out_edge_list_container_ref,
				Accessor< edge_list_operation > >
      const_out_edge_list_container;
   typedef typename inherit_const<out_edge_list_container, GraphRef>::type& out_edge_list_container_ref;
   typedef const const_out_edge_list_container& const_out_edge_list_container_ref;

   typedef masquerade_container<typename if_else<attrib<GraphRef>::is_const,
						 typename graph_type::const_in_edge_list_container_ref,
						 typename graph_type::in_edge_list_container_ref>::result,
				Accessor< edge_list_operation > >
      in_edge_list_container;
   typedef masquerade_container<typename graph_type::const_in_edge_list_container_ref,
				Accessor< edge_list_operation > >
      const_in_edge_list_container;
   typedef typename inherit_const<in_edge_list_container, GraphRef>::type& in_edge_list_container_ref;
   typedef const const_in_edge_list_container& const_in_edge_list_container_ref;

   typedef typename out_edge_list_container::value_type out_edge_list;
   typedef typename in_edge_list_container::value_type in_edge_list;
   typedef typename const_out_edge_list_container::value_type const_out_edge_list;
   typedef typename const_in_edge_list_container::value_type const_in_edge_list;
   typedef out_edge_list out_edge_list_ref;
   typedef const_out_edge_list const_out_edge_list_ref;
   typedef in_edge_list in_edge_list_ref;
   typedef const_in_edge_list const_in_edge_list_ref;

   typedef masquerade_container<masquerade<Rows, typename graph_type::const_neighborhood_matrix_ref>,
				Accessor< neighbor_list_operation > >
      out_neighbor_list_container;

   typedef masquerade_container<masquerade<Cols, typename graph_type::const_neighborhood_matrix_ref>,
				Accessor< neighbor_list_operation > >
      in_neighbor_list_container;

   typedef typename out_neighbor_list_container::value_type out_neighbor_list;
   typedef typename in_neighbor_list_container::value_type in_neighbor_list;
   typedef out_neighbor_list out_neighbor_list_ref;
   typedef out_neighbor_list const_out_neighbor_list_ref;
   typedef in_neighbor_list in_neighbor_list_ref;
   typedef in_neighbor_list const_in_neighbor_list_ref;
   typedef NeighborhoodSubset<GraphRef, SetRef, Traits> neighborhood_matrix;
   typedef const neighborhood_matrix& neighborhood_matrix_ref;
   typedef neighborhood_matrix_ref const_neighborhood_matrix_ref;
};

template <typename GraphRef, typename SetRef, typename Traits=void>
struct subgraph_random_access {
   static const bool answer=container_traits<typename deref<GraphRef>::type::node_container_ref>::is_random &&
                            (!extract_bool_param<Traits,Renumber>::result || container_traits<SetRef>::is_random);
};

template <typename GraphRef, typename SetRef, typename Traits,
	  bool _has_random=subgraph_random_access<GraphRef,SetRef,Traits>::answer>
class IndexedSubgraph_random_access_methods { };

template <typename GraphRef, typename SetRef, typename Traits=void>
class IndexedSubgraph
   : public IndexedSubgraph_base<GraphRef, SetRef, Traits>,
     public IndexedSubgraph_random_access_methods<GraphRef,SetRef,Traits>,
     public GenericGraph< IndexedSubgraph<GraphRef,SetRef,Traits>,
			  typename deref<GraphRef>::type::node_attr,
			  typename deref<GraphRef>::type::edge_attr,
			  graph::kind_helper<GraphRef>::dir > {
   typedef IndexedSubgraph_base<GraphRef, SetRef, Traits> _base;
   friend class IndexedSubgraph_random_access_methods<GraphRef,SetRef,Traits>;

public:
   IndexedSubgraph(typename _base::first_arg_type graph_arg, typename alias<SetRef>::arg_type node_set_arg)
      : _base(graph_arg, node_set_arg) { }

   int nodes() const { return this->get_node_set().size(); }

   template <typename MasqueradeRef>
   MasqueradeRef pretend()
   {
      // icc refuses to accept the simple expression: reinterpret_cast<MasqueradeRef>(*this)
      return reinterpret_cast<typename attrib<MasqueradeRef>::type&>(*this);
   }
   template <typename MasqueradeRef>
   typename attrib<MasqueradeRef>::plus_const pretend() const
   {
      return reinterpret_cast<const typename attrib<MasqueradeRef>::type&>(*this);
   }
};

template <typename GraphRef, typename SetRef, typename Traits>
class IndexedSubgraph_random_access_methods<GraphRef, SetRef, Traits, true> {
   typedef IndexedSubgraph<GraphRef, SetRef, Traits> master;
   typedef IndexedSubgraph_base<GraphRef, SetRef, Traits> base;

   master& me() { return static_cast<master&>(*this); }
   const master& me() const { return static_cast<const master&>(*this); }

   int _node_index(int n, False*) const
   {
      INDEX_CHECK((!me().get_node_set().contains(n)), "IndexedSubgraph - accessing unselected node");
      return n;
   }
   int _node_index(int n, True*) const
   {
      return me().get_node_set()[n];
   }
   int _node_index(int n) const
   {
      return _node_index(n, (typename extract_type_param<Traits,Renumber,False>::result*)0);
   }
public:
   typename deref<GraphRef>::type::node_attr& node(int n)
   {
      return me().get_graph().node(_node_index(n));
   }
   const typename deref<GraphRef>::type::node_attr& node(int n) const
   {
      return me().get_graph().node(_node_index(n));
   }

   typename base::out_edge_list out_edges(int n)
   {
      return typename base::out_edge_list(me().get_graph().out_edges(_node_index(n)), me().get_node_set());
   }
   typename base::const_out_edge_list out_edges(int n) const
   {
      return typename base::const_out_edge_list(me().get_graph().out_edges(_node_index(n)), me().get_node_set());
   }
   typename base::in_edge_list in_edges(int n)
   {
      return typename base::in_edge_list(me().get_graph().in_edges(_node_index(n)), me().get_node_set());
   }
   typename base::const_in_edge_list in_edges(int n) const
   {
      return typename base::const_in_edge_list(me().get_graph().in_edges(_node_index(n)), me().get_node_set());
   }

   int out_degree(int n) const
   {
      return out_edges(n).size();
   }
   int in_degree(int n) const
   {
      return in_edges(n).size();
   }
   int degree (int n) const
   {
      int d=out_degree(n);
      if (graph::kind_helper<GraphRef>::dir==graph::directed) d+=in_degree(n);
      return d;
   }

   typename base::out_neighbor_list out_neighbors(int n) const
   {
      return typename base::out_neighbor_list(me().get_graph().out_neighbors(_node_index(n)), me().get_node_set());
   }
   typename base::in_neighbor_list in_neighbors(int n) const
   {
      return typename base::in_neighbor_list(me().get_graph().in_neighbors(_node_index(n)), me().get_node_set());
   }

   typename deref<GraphRef>::type::edge_attr& edge(int n1, int n2)
   {
      return me().get_graph().edge(_node_index(n1),_node_index(n2));
   }
   const typename deref<GraphRef>::type::edge_attr& edge(int n1, int n2) const
   {
      return me().get_graph().edge(_node_index(n1),_node_index(n2));
   }

   bool edge_exists(int n1, int n2) const
   {
      return me().get_graph().edge_exists(_node_index(n1),_node_index(n2));
   }
   void create_edge(int n1, int n2, const typename deref<GraphRef>::type::edge_attr& d)
   {
      me().get_graph().create_edge(_node_index(n1),_node_index(n2),d);
   }
   void delete_edge(int n1, int n2)
   {
      me().get_graph().delete_edge(_node_index(n1),_node_index(n2));
   }
};

template <typename GraphRef, typename SetRef, typename Traits>
struct spec_object_traits< IndexedSubgraph<GraphRef,SetRef,Traits> >
   : spec_object_traits<is_scalar> {
   static const bool is_temporary=true, is_always_const=effectively_const<GraphRef>::answer;
};

template <typename GraphRef, typename SetRef, typename Traits>
class NeighborhoodSubset
   : public GenericIncidenceMatrix< NeighborhoodSubset<GraphRef,SetRef,Traits>,
				    bool2type< graph::kind_helper<GraphRef>::dir==graph::undirected > > {
protected:
   ~NeighborhoodSubset();

   IndexedSubgraph<GraphRef,SetRef,Traits>& hidden()
   {
      return reinterpret_cast<IndexedSubgraph<GraphRef,SetRef,Traits>&>(*this);
   }
   const IndexedSubgraph<GraphRef,SetRef,Traits>& hidden() const
   {
      return reinterpret_cast<const IndexedSubgraph<GraphRef,SetRef,Traits>&>(*this);
   }

   friend class Rows<NeighborhoodSubset>;
   friend class Cols<NeighborhoodSubset>;
   friend class matrix_random_access_methods<NeighborhoodSubset>;
};

template <typename GraphRef, typename SetRef, typename Traits>
class matrix_random_access_methods< NeighborhoodSubset<GraphRef,SetRef,Traits> > {
   typedef NeighborhoodSubset<GraphRef, SetRef, Traits> master;
public:
   bool operator() (int n1, int n2) const
   {
      const master& me=static_cast<const master&>(*this);
      return me.hidden().edge_exists(n1,n2);
   }
};

template <typename GraphRef, typename SetRef, typename Traits>
class Rows< NeighborhoodSubset<GraphRef,SetRef,Traits> >
   : public IndexedSubgraph<GraphRef, SetRef, Traits>::out_neighbor_list_container {
protected:
   ~Rows();
};

template <typename GraphRef, typename SetRef, typename Traits>
class Cols< NeighborhoodSubset<GraphRef,SetRef,Traits> >
   : public IndexedSubgraph<GraphRef, SetRef, Traits>::in_neighbor_list_container {
protected:
   ~Cols();
};

template <typename Graph, typename Set> inline
IndexedSubgraph<Graph&, const typename Concrete<Set>::type&>
select_subgraph(GenericGraph<Graph>& G, const Set& nodes)
{
   INDEX_CHECK(!complement_helper<const typename Concrete<Set>::type&>::
	        dimension_check(Concrete<Set>::get(nodes), G.top().nodes()),
	       "select_subgraph - node indices out of range");
   return IndexedSubgraph<Graph&, const typename Concrete<Set>::type&>(G.top(), Concrete<Set>::get(nodes));
}

template <typename Graph, typename Set> inline
IndexedSubgraph<const Graph&, const typename Concrete<Set>::type&>
select_subgraph(const GenericGraph<Graph>& G, const Set& nodes)
{
   INDEX_CHECK(!complement_helper<const typename Concrete<Set>::type&>::
	        dimension_check(Concrete<Set>::get(nodes), G.top().nodes()),
	       "select_subgraph - node indices out of range");
   return IndexedSubgraph<const Graph&, const typename Concrete<Set>::type&>(G.top(), Concrete<Set>::get(nodes));
}

template <typename Graph, typename Set> inline
IndexedSubgraph<Graph&, const typename Concrete<Set>::type&, Renumber<True> >
induced_subgraph(GenericGraph<Graph>& G, const Set& nodes)
{
   INDEX_CHECK(!complement_helper<const typename Concrete<Set>::type&>::
	        dimension_check(Concrete<Set>::get(nodes), G.top().nodes()),
	       "induced_subgraph - node indices out of range");
   return IndexedSubgraph<Graph&, const typename Concrete<Set>::type&, Renumber<True> >(G.top(), Concrete<Set>::get(nodes));
}

template <typename Graph, typename Set> inline
IndexedSubgraph<const Graph&, const typename Concrete<Set>::type&, Renumber<True> >
induced_subgraph(const GenericGraph<Graph>& G, const Set& nodes)
{
   INDEX_CHECK(!complement_helper<const typename Concrete<Set>::type&>::
	        dimension_check(Concrete<Set>::get(nodes), G.top().nodes()),
	       "induced_subgraph - node indices out of range");
   return IndexedSubgraph<const Graph&, const typename Concrete<Set>::type&, Renumber<True> >(G.top(), Concrete<Set>::get(nodes));
}

} // end namespace pm

#endif // _POLYMAKE_INDEXED_GRAPH_H

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