/* 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_ADAPTER_H
#define _POLYMAKE_GRAPH_ADAPTER_H "$Project: polymake $$Id: GraphAdapter.h 7406 2006-08-02 17:26:57Z gawrilow $"

#include <Graph.h>
#include <Heap.h>
#include <vector>
#include <ext/hash_map>

namespace pm {
namespace graph {

template <typename IteratorRef>
struct edge_id_accessor {
   typedef IteratorRef argument_type;
   typedef typename deref<IteratorRef>::type iterator;
   typedef pair<int, const typename iterator_traits<iterator>::value_type*> result_type;

private:
   static int from_node(argument_type it, True)
   {
      return it.get_line_index();
   }
   static int from_node(argument_type it, False)
   {
      return it->key - it.get_line_index();
   }

public:
   result_type operator() (argument_type it) const
   {
      return result_type(from_node(it, bool2type<iterator::symmetric || iterator::row_oriented>()),
			 it.operator->());
   }
};

template <typename Tree>
class edge_id_list
   : public modified_tree< edge_id_list<Tree>,
			   list( Hidden< Tree >,
				 Operation< BuildUnaryIt<edge_id_accessor> > ) > {
   protected:
      ~edge_id_list();
   };

} } // end namespace pm::graph

/* The next two specializations should solve the problem of ambiguous edge_ids in undirected graphs,
   by constraining the comparison on the second component (pointer to the cell), which is indeed unique.
*/

namespace std {
   template <typename Value> inline
   bool operator== (const pair<int, const pm::sparse2d::cell<Value>*>& p1,
		    const pair<int, const pm::sparse2d::cell<Value>*>& p2)
   {
      return p1.second==p2.second;
   }

   template <typename Value> inline
   bool operator< (const pair<int, const pm::sparse2d::cell<Value>*>& p1,
		   const pair<int, const pm::sparse2d::cell<Value>*>& p2)
   {
      return p1.second<p2.second;
   }
}

namespace std_ext {
   template <typename Value>
   struct hash< std::pair<int, const pm::sparse2d::cell<Value>*> > {
   protected:
      hash<const pm::sparse2d::cell<Value>*> h_second;
   public:
      size_t operator() (const std::pair<int, const pm::sparse2d::cell<Value>*>& p) const
      {
	 return h_second(p.second);
      }
   };
}

namespace polymake { namespace graph {

template <typename NodeAttr, typename EdgeAttr, pm::graph::kind dir>
class GraphAdapter : public pm::hash_map_adapter {
public:
   typedef Graph<NodeAttr, EdgeAttr, dir> basic_graph_type;
   const basic_graph_type& get_basic_graph() const { return G; }

   static const pm::graph::kind is_directed=dir;

   GraphAdapter(const basic_graph_type& G_arg) : G(G_arg) { }

   typedef typename basic_graph_type::const_node_container_ref Nodes;
   typedef typename basic_graph_type::const_edge_container_ref Edges;

   Nodes nodes() const { return pm::nodes(G); }
   Edges edges() const { return pm::edges(G); }

   typedef int node_id;
   typedef std::pair<int, const pm::sparse2d::cell<EdgeAttr>*> edge_id;

   static node_id void_node_id() { return -1; }
   static edge_id void_edge_id() { return edge_id(-1,0); }

   typedef typename basic_graph_type::template edge_access<pm::graph::edge_id_list>::out::const_reference OutEdges;
   typedef typename basic_graph_type::template edge_access<pm::graph::edge_id_list>::in::const_reference InEdges;

   OutEdges out_edges(node_id n) const
   {
      return G.template out_edges<pm::graph::edge_id_list>(n);
   }
   InEdges in_edges(node_id n) const
   {
      return G.template in_edges<pm::graph::edge_id_list>(n);
   }

   static node_id to_node(const edge_id& e)
   {
      return e.second->key-e.first;
   }
   static node_id from_node(const edge_id& e)
   {
      return e.first;
   }

   template <typename Value>
   struct node_property_map {
      typedef pm::vector_as_property_map<Value> type;
   };

   template <typename Value> static
   typename node_property_map<Value>::type create_property_map(node_id*, Value*)
   {
      return typename node_property_map<Value>::type();
   }

   template <typename Value>
   void clear(pm::vector_as_property_map<Value>& map) const
   {
      map.clear();
      map.get_container().reserve(G.nodes());
   }

   template <typename Value>
   void clear(pm::vector_as_property_map<Value>& map, const Value& v) const
   {
      clear(map);
      map.set_default_value(v);
   }

   template <typename Value>
   void init(pm::vector_as_property_map<Value>& map) const
   {
      map.clear();
      map.get_container().resize(G.nodes());
   }

   template <typename Value>
   void init(pm::vector_as_property_map<Value>& map, const Value& v) const
   {
      init(map);
      std::fill(pm::entire(map), v);
   }

   template <typename Value>
   struct edge_property_map : hash_map_adapter::template property_map<edge_id, Value> { };

   using hash_map_adapter::create_property_map;
   using hash_map_adapter::init;
   using hash_map_adapter::clear;

   template <typename Key, typename Value>
   struct property_map;

   template <typename Value>
   struct property_map<node_id, Value> : node_property_map<Value> { };

   template <typename Value>
   struct property_map<edge_id, Value> : edge_property_map<Value> { };
protected:
   const basic_graph_type& G;
};

// This is an example - only one of possible adaptors for the dijkstra algorithm.
// It assumes that EdgeAttr represents the edge length, which is of one of usual arithmetic types.

template <typename NodeAttr, typename EdgeAttr, pm::graph::kind dir>
class ShortestPathAdapter : public GraphAdapter<NodeAttr,EdgeAttr,dir> {
   typedef GraphAdapter<NodeAttr,EdgeAttr,dir> _super;
public:
   ShortestPathAdapter(const typename _super::basic_graph_type& G) : _super(G) { }
   ShortestPathAdapter(const _super& arg) : _super(arg) { }

   typedef EdgeAttr weight_type;
   typedef EdgeAttr distance_type;
   typedef operations::cmp distance_comparator_type;

   static distance_comparator_type get_distance_comparator() { return distance_comparator_type(); }
   static const weight_type& get_edge_weight(typename _super::edge_id e) { return e.second->data; }
};

} }

#endif // _POLYMAKE_GRAPH_ADAPTER_H

// Local Variables:
// mode:C++
// c-basic-offset:3
// End: