//=======================================================================

 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.

 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek

 //

 // Distributed under the Boost Software License, Version 1.0. (See

 // accompanying file LICENSE_1_0.txt or copy at

 // http://www.boost.org/LICENSE_1_0.txt)

 //=======================================================================

 //

 #ifndef BOOST_GRAPH_EDGE_LIST_HPP

 #define BOOST_GRAPH_EDGE_LIST_HPP

 #include <iterator>

 #include <boost/config.hpp>

 #include <boost/pending/ct_if.hpp>

 #include <boost/pending/integer_range.hpp>

 #include <boost/graph/graph_traits.hpp>

 #include <boost/graph/properties.hpp>

 namespace boost {

   //

   // The edge_list class is an EdgeListGraph module that is constructed

   // from a pair of iterators whose value type is a pair of vertex

   // descriptors.

   //

   // For example:

   //

   //  typedef std::pair<int,int> E;

   //  list<E> elist;

   //  ...

   //  typedef edge_list<list<E>::iterator> Graph;

   //  Graph g(elist.begin(), elist.end());

   //

   // If the iterators are random access, then Graph::edge_descriptor

   // is of Integral type, otherwise it is a struct, though it is

   // convertible to an Integral type.

   // 

   struct edge_list_tag { };

   // The implementation class for edge_list.

   template <class G, class EdgeIter, class T, class D>

   class edge_list_impl

   {

   public:

     typedef D edge_id;

     typedef T Vpair;

     typedef typename Vpair::first_type V;

     typedef V vertex_descriptor;

     typedef edge_list_tag graph_tag;

     typedef void edge_property_type;

     struct edge_descriptor

     {

       edge_descriptor() { }

       edge_descriptor(EdgeIter p, edge_id id) : _ptr(p), _id(id) { }

       operator edge_id() { return _id; }

       EdgeIter _ptr;

       edge_id _id;

     };

     typedef edge_descriptor E;

     struct edge_iterator

     {

       typedef edge_iterator self;

       typedef E value_type;

       typedef E& reference;

       typedef E* pointer;

       typedef std::ptrdiff_t difference_type;

       typedef std::input_iterator_tag iterator_category;

       edge_iterator() { }

       edge_iterator(EdgeIter iter) : _iter(iter), _i(0) { }

       E operator*() { return E(_iter, _i); }

       self& operator++() { ++_iter; ++_i; return *this; }

       self operator++(int) { self t = *this; ++(*this); return t; }

       bool operator==(const self& x) { return _iter == x._iter; }

       bool operator!=(const self& x) { return _iter != x._iter; }

       EdgeIter _iter;

       edge_id _i;

     };

     typedef void out_edge_iterator;

     typedef void in_edge_iterator;

     typedef void adjacency_iterator;

     typedef void vertex_iterator;

   };

   template <class G, class EI, class T, class D>

   std::pair<typename edge_list_impl<G,EI,T,D>::edge_iterator,

             typename edge_list_impl<G,EI,T,D>::edge_iterator>

   edges(const edge_list_impl<G,EI,T,D>& g_) {

     const G& g = static_cast<const G&>(g_);

     typedef typename edge_list_impl<G,EI,T,D>::edge_iterator edge_iterator;

     return std::make_pair(edge_iterator(g._first), edge_iterator(g._last));

   }

   template <class G, class EI, class T, class D>

   typename edge_list_impl<G,EI,T,D>::vertex_descriptor

   source(typename edge_list_impl<G,EI,T,D>::edge_descriptor e,

          const edge_list_impl<G,EI,T,D>&) {

     return (*e._ptr).first;

   }

   template <class G, class EI, class T, class D>

   typename edge_list_impl<G,EI,T,D>::vertex_descriptor

   target(typename edge_list_impl<G,EI,T,D>::edge_descriptor e,

            const edge_list_impl<G,EI,T,D>&) {

     return (*e._ptr).second;

   }

   template <class D, class E>

   class el_edge_property_map

     : public put_get_helper<D, el_edge_property_map<D,E> >{

   public:

     typedef E key_type;

     typedef D value_type;

     typedef D reference;

     typedef readable_property_map_tag category;

     value_type operator[](key_type e) const {

       return e._i;

     }

   };

   struct edge_list_edge_property_selector {

     template <class Graph, class Property, class Tag>

     struct bind_ {

       typedef el_edge_property_map<typename Graph::edge_id,

           typename Graph::edge_descriptor> type;

       typedef type const_type;

     };

   };

   template <>  

   struct edge_property_selector<edge_list_tag> {

     typedef edge_list_edge_property_selector type;

   };

   template <class G, class EI, class T, class D>

   typename property_map< edge_list_impl<G,EI,T,D>, edge_index_t>::type

   get(edge_index_t, const edge_list_impl<G,EI,T,D>&) {

     typedef typename property_map< edge_list_impl<G,EI,T,D>, 

       edge_index_t>::type EdgeIndexMap;

     return EdgeIndexMap();

   }

   template <class G, class EI, class T, class D>

   inline D

   get(edge_index_t, const edge_list_impl<G,EI,T,D>&,

       typename edge_list_impl<G,EI,T,D>::edge_descriptor e) {

     return e._i;

   }

   // A specialized implementation for when the iterators are random access.

   struct edge_list_ra_tag { };

   template <class G, class EdgeIter, class T, class D>

   class edge_list_impl_ra

   {

   public:

     typedef D edge_id;

     typedef T Vpair;

     typedef typename Vpair::first_type V;

     typedef edge_list_ra_tag graph_tag;

     typedef void edge_property_type;

     typedef edge_id edge_descriptor;

     typedef V vertex_descriptor;

     typedef typename boost::integer_range<edge_id>::iterator edge_iterator;

     typedef void out_edge_iterator;

     typedef void in_edge_iterator;

     typedef void adjacency_iterator;

     typedef void vertex_iterator;

   };

   template <class G, class EI, class T, class D>

   std::pair<typename edge_list_impl_ra<G,EI,T,D>::edge_iterator,

             typename edge_list_impl_ra<G,EI,T,D>::edge_iterator>

   edges(const edge_list_impl_ra<G,EI,T,D>& g_)

   {

     const G& g = static_cast<const G&>(g_);

     typedef typename edge_list_impl_ra<G,EI,T,D>::edge_iterator edge_iterator;

     return std::make_pair(edge_iterator(0), edge_iterator(g._last - g._first));

   }    

   template <class G, class EI, class T, class D>

   typename edge_list_impl_ra<G,EI,T,D>::vertex_descriptor

   source(typename edge_list_impl_ra<G,EI,T,D>::edge_descriptor e,

          const edge_list_impl_ra<G,EI,T,D>& g_)

   {

     const G& g = static_cast<const G&>(g_);

     return g._first[e].first;

   }

   template <class G, class EI, class T, class D>

   typename edge_list_impl_ra<G,EI,T,D>::vertex_descriptor

   target(typename edge_list_impl_ra<G,EI,T,D>::edge_descriptor  e,

          const edge_list_impl_ra<G,EI,T,D>& g_)

   {

     const G& g = static_cast<const G&>(g_);

     return g._first[e].second;

   }

   template <class E>

   class el_ra_edge_property_map

     : public put_get_helper<E, el_ra_edge_property_map<E> >{

   public:

     typedef E key_type;

     typedef E value_type;

     typedef E reference;

     typedef readable_property_map_tag category;

     value_type operator[](key_type e) const {

       return e;

     }

   };

   struct edge_list_ra_edge_property_selector {

     template <class Graph, class Property, class Tag>

     struct bind_ {

       typedef el_ra_edge_property_map<typename Graph::edge_descriptor> type;

       typedef type const_type;

     };

   };

   template <>  

   struct edge_property_selector<edge_list_ra_tag> {

     typedef edge_list_ra_edge_property_selector type;

   };

   template <class G, class EI, class T, class D>

   inline 

   typename property_map< edge_list_impl_ra<G,EI,T,D>, edge_index_t>::type

   get(edge_index_t, const edge_list_impl_ra<G,EI,T,D>&) {

     typedef typename property_map< edge_list_impl_ra<G,EI,T,D>, 

       edge_index_t>::type EdgeIndexMap;

     return EdgeIndexMap();

   }

   template <class G, class EI, class T, class D>

   inline D

   get(edge_index_t, const edge_list_impl_ra<G,EI,T,D>&, 

       typename edge_list_impl_ra<G,EI,T,D>::edge_descriptor e) {

     return e;

   }

   // Some helper classes for determining if the iterators are random access

   template <class Cat>

   struct is_random {

     enum { RET = false }; 

     typedef false_type type; 

   };

   template <>

   struct is_random<std::random_access_iterator_tag> { 

     enum { RET = true }; typedef true_type type; 

   };

   // The edge_list class conditionally inherits from one of the

   // above two classes.

   template <class EdgeIter, 

 #if !defined BOOST_NO_STD_ITERATOR_TRAITS

             class T = typename std::iterator_traits<EdgeIter>::value_type,

             class D = typename std::iterator_traits<EdgeIter>::difference_type,

             class Cat = typename std::iterator_traits<EdgeIter>::iterator_category>

 #else

             class T,

             class D, 

             class Cat>

 #endif

   class edge_list

     : public ct_if_t< typename is_random<Cat>::type,

                     edge_list_impl_ra< edge_list<EdgeIter,T,D,Cat>, EdgeIter,T,D>,

                     edge_list_impl< edge_list<EdgeIter,T,D,Cat>, EdgeIter,T,D> 

              >::type

   {

   public:

     typedef directed_tag directed_category;

     typedef allow_parallel_edge_tag edge_parallel_category;

     typedef edge_list_graph_tag traversal_category;

     typedef std::size_t edges_size_type;

     typedef std::size_t vertices_size_type;

     typedef std::size_t degree_size_type;

     edge_list(EdgeIter first, EdgeIter last) : _first(first), _last(last) { 

       m_num_edges = std::distance(first, last);

     }

     edge_list(EdgeIter first, EdgeIter last, edges_size_type E)

       : _first(first), _last(last), m_num_edges(E) { }  

     EdgeIter _first, _last;

     edges_size_type m_num_edges;

   };

   template <class EdgeIter, class T, class D, class Cat>

   std::size_t num_edges(const edge_list<EdgeIter, T, D, Cat>& el) {

     return el.m_num_edges;

   }

 #ifndef BOOST_NO_STD_ITERATOR_TRAITS

   template <class EdgeIter>

   inline edge_list<EdgeIter>

   make_edge_list(EdgeIter first, EdgeIter last)

   {

     return edge_list<EdgeIter>(first, last);

   }

 #endif

 } /* namespace boost */

 #endif /* BOOST_GRAPH_EDGE_LIST_HPP */