boost/graph/edge_list.hpp

//=======================================================================
// 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/mpl/if.hpp>
#include <boost/mpl/bool.hpp>
#include <boost/range/irange.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 mpl::false_ type;
  };
  template <>
  struct is_random<std::random_access_iterator_tag> {
    enum { RET = true }; typedef mpl::true_ 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 mpl::if_< 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 */