| //======================================================================= |
| // 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 */ |