williamr@2: //=======================================================================
williamr@2: // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
williamr@2: // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
williamr@2: //
williamr@2: // Distributed under the Boost Software License, Version 1.0. (See
williamr@2: // accompanying file LICENSE_1_0.txt or copy at
williamr@2: // http://www.boost.org/LICENSE_1_0.txt)
williamr@2: //=======================================================================
williamr@2: //
williamr@2: 
williamr@2: #ifndef BOOST_GRAPH_EDGE_LIST_HPP
williamr@2: #define BOOST_GRAPH_EDGE_LIST_HPP
williamr@2: 
williamr@2: #include <iterator>
williamr@2: #include <boost/config.hpp>
williamr@2: #include <boost/pending/ct_if.hpp>
williamr@2: #include <boost/pending/integer_range.hpp>
williamr@2: #include <boost/graph/graph_traits.hpp>
williamr@2: #include <boost/graph/properties.hpp>
williamr@2: 
williamr@2: namespace boost {
williamr@2: 
williamr@2:   //
williamr@2:   // The edge_list class is an EdgeListGraph module that is constructed
williamr@2:   // from a pair of iterators whose value type is a pair of vertex
williamr@2:   // descriptors.
williamr@2:   //
williamr@2:   // For example:
williamr@2:   //
williamr@2:   //  typedef std::pair<int,int> E;
williamr@2:   //  list<E> elist;
williamr@2:   //  ...
williamr@2:   //  typedef edge_list<list<E>::iterator> Graph;
williamr@2:   //  Graph g(elist.begin(), elist.end());
williamr@2:   //
williamr@2:   // If the iterators are random access, then Graph::edge_descriptor
williamr@2:   // is of Integral type, otherwise it is a struct, though it is
williamr@2:   // convertible to an Integral type.
williamr@2:   // 
williamr@2: 
williamr@2:   struct edge_list_tag { };
williamr@2: 
williamr@2:   // The implementation class for edge_list.
williamr@2:   template <class G, class EdgeIter, class T, class D>
williamr@2:   class edge_list_impl
williamr@2:   {
williamr@2:   public:
williamr@2:     typedef D edge_id;
williamr@2:     typedef T Vpair;
williamr@2:     typedef typename Vpair::first_type V;
williamr@2:     typedef V vertex_descriptor;
williamr@2:     typedef edge_list_tag graph_tag;
williamr@2:     typedef void edge_property_type;
williamr@2: 
williamr@2:     struct edge_descriptor
williamr@2:     {
williamr@2:       edge_descriptor() { }
williamr@2:       edge_descriptor(EdgeIter p, edge_id id) : _ptr(p), _id(id) { }
williamr@2:       operator edge_id() { return _id; }
williamr@2:       EdgeIter _ptr;
williamr@2:       edge_id _id;
williamr@2:     };
williamr@2:     typedef edge_descriptor E;
williamr@2: 
williamr@2:     struct edge_iterator
williamr@2:     {
williamr@2:       typedef edge_iterator self;
williamr@2:       typedef E value_type;
williamr@2:       typedef E& reference;
williamr@2:       typedef E* pointer;
williamr@2:       typedef std::ptrdiff_t difference_type;
williamr@2:       typedef std::input_iterator_tag iterator_category;
williamr@2:       edge_iterator() { }
williamr@2:       edge_iterator(EdgeIter iter) : _iter(iter), _i(0) { }
williamr@2:       E operator*() { return E(_iter, _i); }
williamr@2:       self& operator++() { ++_iter; ++_i; return *this; }
williamr@2:       self operator++(int) { self t = *this; ++(*this); return t; }
williamr@2:       bool operator==(const self& x) { return _iter == x._iter; }
williamr@2:       bool operator!=(const self& x) { return _iter != x._iter; }
williamr@2:       EdgeIter _iter;
williamr@2:       edge_id _i;
williamr@2:     };
williamr@2:     typedef void out_edge_iterator;
williamr@2:     typedef void in_edge_iterator;
williamr@2:     typedef void adjacency_iterator;
williamr@2:     typedef void vertex_iterator;
williamr@2:   };
williamr@2: 
williamr@2:   template <class G, class EI, class T, class D>
williamr@2:   std::pair<typename edge_list_impl<G,EI,T,D>::edge_iterator,
williamr@2:             typename edge_list_impl<G,EI,T,D>::edge_iterator>
williamr@2:   edges(const edge_list_impl<G,EI,T,D>& g_) {
williamr@2:     const G& g = static_cast<const G&>(g_);
williamr@2:     typedef typename edge_list_impl<G,EI,T,D>::edge_iterator edge_iterator;
williamr@2:     return std::make_pair(edge_iterator(g._first), edge_iterator(g._last));
williamr@2:   }
williamr@2:   template <class G, class EI, class T, class D>
williamr@2:   typename edge_list_impl<G,EI,T,D>::vertex_descriptor
williamr@2:   source(typename edge_list_impl<G,EI,T,D>::edge_descriptor e,
williamr@2:          const edge_list_impl<G,EI,T,D>&) {
williamr@2:     return (*e._ptr).first;
williamr@2:   }
williamr@2:   template <class G, class EI, class T, class D>
williamr@2:   typename edge_list_impl<G,EI,T,D>::vertex_descriptor
williamr@2:   target(typename edge_list_impl<G,EI,T,D>::edge_descriptor e,
williamr@2:            const edge_list_impl<G,EI,T,D>&) {
williamr@2:     return (*e._ptr).second;
williamr@2:   }
williamr@2: 
williamr@2:   template <class D, class E>
williamr@2:   class el_edge_property_map
williamr@2:     : public put_get_helper<D, el_edge_property_map<D,E> >{
williamr@2:   public:
williamr@2:     typedef E key_type;
williamr@2:     typedef D value_type;
williamr@2:     typedef D reference;
williamr@2:     typedef readable_property_map_tag category;
williamr@2: 
williamr@2:     value_type operator[](key_type e) const {
williamr@2:       return e._i;
williamr@2:     }
williamr@2:   };
williamr@2:   struct edge_list_edge_property_selector {
williamr@2:     template <class Graph, class Property, class Tag>
williamr@2:     struct bind_ {
williamr@2:       typedef el_edge_property_map<typename Graph::edge_id,
williamr@2:           typename Graph::edge_descriptor> type;
williamr@2:       typedef type const_type;
williamr@2:     };
williamr@2:   };
williamr@2:   template <>  
williamr@2:   struct edge_property_selector<edge_list_tag> {
williamr@2:     typedef edge_list_edge_property_selector type;
williamr@2:   };
williamr@2: 
williamr@2:   template <class G, class EI, class T, class D>
williamr@2:   typename property_map< edge_list_impl<G,EI,T,D>, edge_index_t>::type
williamr@2:   get(edge_index_t, const edge_list_impl<G,EI,T,D>&) {
williamr@2:     typedef typename property_map< edge_list_impl<G,EI,T,D>, 
williamr@2:       edge_index_t>::type EdgeIndexMap;
williamr@2:     return EdgeIndexMap();
williamr@2:   }
williamr@2: 
williamr@2:   template <class G, class EI, class T, class D>
williamr@2:   inline D
williamr@2:   get(edge_index_t, const edge_list_impl<G,EI,T,D>&,
williamr@2:       typename edge_list_impl<G,EI,T,D>::edge_descriptor e) {
williamr@2:     return e._i;
williamr@2:   }
williamr@2: 
williamr@2:   // A specialized implementation for when the iterators are random access.
williamr@2: 
williamr@2:   struct edge_list_ra_tag { };
williamr@2: 
williamr@2:   template <class G, class EdgeIter, class T, class D>
williamr@2:   class edge_list_impl_ra
williamr@2:   {
williamr@2:   public:
williamr@2:     typedef D edge_id;
williamr@2:     typedef T Vpair;
williamr@2:     typedef typename Vpair::first_type V;
williamr@2:     typedef edge_list_ra_tag graph_tag;
williamr@2:     typedef void edge_property_type;
williamr@2: 
williamr@2:     typedef edge_id edge_descriptor;
williamr@2:     typedef V vertex_descriptor;
williamr@2:     typedef typename boost::integer_range<edge_id>::iterator edge_iterator;
williamr@2:     typedef void out_edge_iterator;
williamr@2:     typedef void in_edge_iterator;
williamr@2:     typedef void adjacency_iterator;
williamr@2:     typedef void vertex_iterator;
williamr@2:   };
williamr@2: 
williamr@2:   template <class G, class EI, class T, class D>
williamr@2:   std::pair<typename edge_list_impl_ra<G,EI,T,D>::edge_iterator,
williamr@2:             typename edge_list_impl_ra<G,EI,T,D>::edge_iterator>
williamr@2:   edges(const edge_list_impl_ra<G,EI,T,D>& g_)
williamr@2:   {
williamr@2:     const G& g = static_cast<const G&>(g_);
williamr@2:     typedef typename edge_list_impl_ra<G,EI,T,D>::edge_iterator edge_iterator;
williamr@2:     return std::make_pair(edge_iterator(0), edge_iterator(g._last - g._first));
williamr@2:   }    
williamr@2:   template <class G, class EI, class T, class D>
williamr@2:   typename edge_list_impl_ra<G,EI,T,D>::vertex_descriptor
williamr@2:   source(typename edge_list_impl_ra<G,EI,T,D>::edge_descriptor e,
williamr@2:          const edge_list_impl_ra<G,EI,T,D>& g_)
williamr@2:   {
williamr@2:     const G& g = static_cast<const G&>(g_);
williamr@2:     return g._first[e].first;
williamr@2:   }
williamr@2:   template <class G, class EI, class T, class D>
williamr@2:   typename edge_list_impl_ra<G,EI,T,D>::vertex_descriptor
williamr@2:   target(typename edge_list_impl_ra<G,EI,T,D>::edge_descriptor  e,
williamr@2:          const edge_list_impl_ra<G,EI,T,D>& g_)
williamr@2:   {
williamr@2:     const G& g = static_cast<const G&>(g_);
williamr@2:     return g._first[e].second;
williamr@2:   }
williamr@2:   template <class E>
williamr@2:   class el_ra_edge_property_map
williamr@2:     : public put_get_helper<E, el_ra_edge_property_map<E> >{
williamr@2:   public:
williamr@2:     typedef E key_type;
williamr@2:     typedef E value_type;
williamr@2:     typedef E reference;
williamr@2:     typedef readable_property_map_tag category;
williamr@2: 
williamr@2:     value_type operator[](key_type e) const {
williamr@2:       return e;
williamr@2:     }
williamr@2:   };
williamr@2:   struct edge_list_ra_edge_property_selector {
williamr@2:     template <class Graph, class Property, class Tag>
williamr@2:     struct bind_ {
williamr@2:       typedef el_ra_edge_property_map<typename Graph::edge_descriptor> type;
williamr@2:       typedef type const_type;
williamr@2:     };
williamr@2:   };
williamr@2:   template <>  
williamr@2:   struct edge_property_selector<edge_list_ra_tag> {
williamr@2:     typedef edge_list_ra_edge_property_selector type;
williamr@2:   };
williamr@2:   template <class G, class EI, class T, class D>
williamr@2:   inline 
williamr@2:   typename property_map< edge_list_impl_ra<G,EI,T,D>, edge_index_t>::type
williamr@2:   get(edge_index_t, const edge_list_impl_ra<G,EI,T,D>&) {
williamr@2:     typedef typename property_map< edge_list_impl_ra<G,EI,T,D>, 
williamr@2:       edge_index_t>::type EdgeIndexMap;
williamr@2:     return EdgeIndexMap();
williamr@2:   }
williamr@2: 
williamr@2:   template <class G, class EI, class T, class D>
williamr@2:   inline D
williamr@2:   get(edge_index_t, const edge_list_impl_ra<G,EI,T,D>&, 
williamr@2:       typename edge_list_impl_ra<G,EI,T,D>::edge_descriptor e) {
williamr@2:     return e;
williamr@2:   }
williamr@2: 
williamr@2: 
williamr@2:   // Some helper classes for determining if the iterators are random access
williamr@2:   template <class Cat>
williamr@2:   struct is_random {
williamr@2:     enum { RET = false }; 
williamr@2:     typedef false_type type; 
williamr@2:   };
williamr@2:   template <>
williamr@2:   struct is_random<std::random_access_iterator_tag> { 
williamr@2:     enum { RET = true }; typedef true_type type; 
williamr@2:   };
williamr@2: 
williamr@2:   // The edge_list class conditionally inherits from one of the
williamr@2:   // above two classes.
williamr@2: 
williamr@2:   template <class EdgeIter, 
williamr@2: #if !defined BOOST_NO_STD_ITERATOR_TRAITS
williamr@2:             class T = typename std::iterator_traits<EdgeIter>::value_type,
williamr@2:             class D = typename std::iterator_traits<EdgeIter>::difference_type,
williamr@2:             class Cat = typename std::iterator_traits<EdgeIter>::iterator_category>
williamr@2: #else
williamr@2:             class T,
williamr@2:             class D, 
williamr@2:             class Cat>
williamr@2: #endif
williamr@2:   class edge_list
williamr@2:     : public ct_if_t< typename is_random<Cat>::type,
williamr@2:                     edge_list_impl_ra< edge_list<EdgeIter,T,D,Cat>, EdgeIter,T,D>,
williamr@2:                     edge_list_impl< edge_list<EdgeIter,T,D,Cat>, EdgeIter,T,D> 
williamr@2:              >::type
williamr@2:   {
williamr@2:   public:
williamr@2:     typedef directed_tag directed_category;
williamr@2:     typedef allow_parallel_edge_tag edge_parallel_category;
williamr@2:     typedef edge_list_graph_tag traversal_category;
williamr@2:     typedef std::size_t edges_size_type;
williamr@2:     typedef std::size_t vertices_size_type;
williamr@2:     typedef std::size_t degree_size_type;
williamr@2:     edge_list(EdgeIter first, EdgeIter last) : _first(first), _last(last) { 
williamr@2:       m_num_edges = std::distance(first, last);
williamr@2:     }
williamr@2:     edge_list(EdgeIter first, EdgeIter last, edges_size_type E)
williamr@2:       : _first(first), _last(last), m_num_edges(E) { }  
williamr@2:     
williamr@2:     EdgeIter _first, _last;
williamr@2:     edges_size_type m_num_edges;
williamr@2:   };
williamr@2: 
williamr@2:   template <class EdgeIter, class T, class D, class Cat>
williamr@2:   std::size_t num_edges(const edge_list<EdgeIter, T, D, Cat>& el) {
williamr@2:     return el.m_num_edges;
williamr@2:   }
williamr@2: 
williamr@2: #ifndef BOOST_NO_STD_ITERATOR_TRAITS
williamr@2:   template <class EdgeIter>
williamr@2:   inline edge_list<EdgeIter>
williamr@2:   make_edge_list(EdgeIter first, EdgeIter last)
williamr@2:   {
williamr@2:     return edge_list<EdgeIter>(first, last);
williamr@2:   }
williamr@2: #endif
williamr@2:   
williamr@2: } /* namespace boost */
williamr@2: 
williamr@2: #endif /* BOOST_GRAPH_EDGE_LIST_HPP */