1 //=======================================================================
2 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
3 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
4 //
5 // Distributed under the Boost Software License, Version 1.0. (See
6 // accompanying file LICENSE_1_0.txt or copy at
7 // http://www.boost.org/LICENSE_1_0.txt)
8 //=======================================================================
9 //
10 
11 #ifndef BOOST_GRAPH_EDGE_LIST_HPP
12 #define BOOST_GRAPH_EDGE_LIST_HPP
13 
14 #include <iterator>
15 #include <boost/config.hpp>
16 #include <boost/pending/ct_if.hpp>
17 #include <boost/pending/integer_range.hpp>
18 #include <boost/graph/graph_traits.hpp>
19 #include <boost/graph/properties.hpp>
20 
21 namespace boost {
22 
23   //
24   // The edge_list class is an EdgeListGraph module that is constructed
25   // from a pair of iterators whose value type is a pair of vertex
26   // descriptors.
27   //
28   // For example:
29   //
30   //  typedef std::pair<int,int> E;
31   //  list<E> elist;
32   //  ...
33   //  typedef edge_list<list<E>::iterator> Graph;
34   //  Graph g(elist.begin(), elist.end());
35   //
36   // If the iterators are random access, then Graph::edge_descriptor
37   // is of Integral type, otherwise it is a struct, though it is
38   // convertible to an Integral type.
39   //
40 
41   struct edge_list_tag { };
42 
43   // The implementation class for edge_list.
44   template <class G, class EdgeIter, class T, class D>
45   class edge_list_impl
46   {
47   public:
48     typedef D edge_id;
49     typedef T Vpair;
50     typedef typename Vpair::first_type V;
51     typedef V vertex_descriptor;
52     typedef edge_list_tag graph_tag;
53     typedef void edge_property_type;
54 
55     struct edge_descriptor
56     {
edge_descriptorboost::edge_list_impl::edge_descriptor57       edge_descriptor() { }
edge_descriptorboost::edge_list_impl::edge_descriptor58       edge_descriptor(EdgeIter p, edge_id id) : _ptr(p), _id(id) { }
operator edge_idboost::edge_list_impl::edge_descriptor59       operator edge_id() { return _id; }
60       EdgeIter _ptr;
61       edge_id _id;
62     };
63     typedef edge_descriptor E;
64 
65     struct edge_iterator
66     {
67       typedef edge_iterator self;
68       typedef E value_type;
69       typedef E& reference;
70       typedef E* pointer;
71       typedef std::ptrdiff_t difference_type;
72       typedef std::input_iterator_tag iterator_category;
edge_iteratorboost::edge_list_impl::edge_iterator73       edge_iterator() { }
edge_iteratorboost::edge_list_impl::edge_iterator74       edge_iterator(EdgeIter iter) : _iter(iter), _i(0) { }
operator *boost::edge_list_impl::edge_iterator75       E operator*() { return E(_iter, _i); }
operator ++boost::edge_list_impl::edge_iterator76       self& operator++() { ++_iter; ++_i; return *this; }
operator ++boost::edge_list_impl::edge_iterator77       self operator++(int) { self t = *this; ++(*this); return t; }
operator ==boost::edge_list_impl::edge_iterator78       bool operator==(const self& x) { return _iter == x._iter; }
operator !=boost::edge_list_impl::edge_iterator79       bool operator!=(const self& x) { return _iter != x._iter; }
80       EdgeIter _iter;
81       edge_id _i;
82     };
83     typedef void out_edge_iterator;
84     typedef void in_edge_iterator;
85     typedef void adjacency_iterator;
86     typedef void vertex_iterator;
87   };
88 
89   template <class G, class EI, class T, class D>
90   std::pair<typename edge_list_impl<G,EI,T,D>::edge_iterator,
91             typename edge_list_impl<G,EI,T,D>::edge_iterator>
edges(const edge_list_impl<G,EI,T,D> & g_)92   edges(const edge_list_impl<G,EI,T,D>& g_) {
93     const G& g = static_cast<const G&>(g_);
94     typedef typename edge_list_impl<G,EI,T,D>::edge_iterator edge_iterator;
95     return std::make_pair(edge_iterator(g._first), edge_iterator(g._last));
96   }
97   template <class G, class EI, class T, class D>
98   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> &)99   source(typename edge_list_impl<G,EI,T,D>::edge_descriptor e,
100          const edge_list_impl<G,EI,T,D>&) {
101     return (*e._ptr).first;
102   }
103   template <class G, class EI, class T, class D>
104   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> &)105   target(typename edge_list_impl<G,EI,T,D>::edge_descriptor e,
106            const edge_list_impl<G,EI,T,D>&) {
107     return (*e._ptr).second;
108   }
109 
110   template <class D, class E>
111   class el_edge_property_map
112     : public put_get_helper<D, el_edge_property_map<D,E> >{
113   public:
114     typedef E key_type;
115     typedef D value_type;
116     typedef D reference;
117     typedef readable_property_map_tag category;
118 
operator [](key_type e) const119     value_type operator[](key_type e) const {
120       return e._i;
121     }
122   };
123   struct edge_list_edge_property_selector {
124     template <class Graph, class Property, class Tag>
125     struct bind_ {
126       typedef el_edge_property_map<typename Graph::edge_id,
127           typename Graph::edge_descriptor> type;
128       typedef type const_type;
129     };
130   };
131   template <>
132   struct edge_property_selector<edge_list_tag> {
133     typedef edge_list_edge_property_selector type;
134   };
135 
136   template <class G, class EI, class T, class D>
137   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> &)138   get(edge_index_t, const edge_list_impl<G,EI,T,D>&) {
139     typedef typename property_map< edge_list_impl<G,EI,T,D>,
140       edge_index_t>::type EdgeIndexMap;
141     return EdgeIndexMap();
142   }
143 
144   template <class G, class EI, class T, class D>
145   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)146   get(edge_index_t, const edge_list_impl<G,EI,T,D>&,
147       typename edge_list_impl<G,EI,T,D>::edge_descriptor e) {
148     return e._i;
149   }
150 
151   // A specialized implementation for when the iterators are random access.
152 
153   struct edge_list_ra_tag { };
154 
155   template <class G, class EdgeIter, class T, class D>
156   class edge_list_impl_ra
157   {
158   public:
159     typedef D edge_id;
160     typedef T Vpair;
161     typedef typename Vpair::first_type V;
162     typedef edge_list_ra_tag graph_tag;
163     typedef void edge_property_type;
164 
165     typedef edge_id edge_descriptor;
166     typedef V vertex_descriptor;
167     typedef typename boost::integer_range<edge_id>::iterator edge_iterator;
168     typedef void out_edge_iterator;
169     typedef void in_edge_iterator;
170     typedef void adjacency_iterator;
171     typedef void vertex_iterator;
172   };
173 
174   template <class G, class EI, class T, class D>
175   std::pair<typename edge_list_impl_ra<G,EI,T,D>::edge_iterator,
176             typename edge_list_impl_ra<G,EI,T,D>::edge_iterator>
edges(const edge_list_impl_ra<G,EI,T,D> & g_)177   edges(const edge_list_impl_ra<G,EI,T,D>& g_)
178   {
179     const G& g = static_cast<const G&>(g_);
180     typedef typename edge_list_impl_ra<G,EI,T,D>::edge_iterator edge_iterator;
181     return std::make_pair(edge_iterator(0), edge_iterator(g._last - g._first));
182   }
183   template <class G, class EI, class T, class D>
184   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_)185   source(typename edge_list_impl_ra<G,EI,T,D>::edge_descriptor e,
186          const edge_list_impl_ra<G,EI,T,D>& g_)
187   {
188     const G& g = static_cast<const G&>(g_);
189     return g._first[e].first;
190   }
191   template <class G, class EI, class T, class D>
192   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_)193   target(typename edge_list_impl_ra<G,EI,T,D>::edge_descriptor  e,
194          const edge_list_impl_ra<G,EI,T,D>& g_)
195   {
196     const G& g = static_cast<const G&>(g_);
197     return g._first[e].second;
198   }
199   template <class E>
200   class el_ra_edge_property_map
201     : public put_get_helper<E, el_ra_edge_property_map<E> >{
202   public:
203     typedef E key_type;
204     typedef E value_type;
205     typedef E reference;
206     typedef readable_property_map_tag category;
207 
operator [](key_type e) const208     value_type operator[](key_type e) const {
209       return e;
210     }
211   };
212   struct edge_list_ra_edge_property_selector {
213     template <class Graph, class Property, class Tag>
214     struct bind_ {
215       typedef el_ra_edge_property_map<typename Graph::edge_descriptor> type;
216       typedef type const_type;
217     };
218   };
219   template <>
220   struct edge_property_selector<edge_list_ra_tag> {
221     typedef edge_list_ra_edge_property_selector type;
222   };
223   template <class G, class EI, class T, class D>
224   inline
225   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> &)226   get(edge_index_t, const edge_list_impl_ra<G,EI,T,D>&) {
227     typedef typename property_map< edge_list_impl_ra<G,EI,T,D>,
228       edge_index_t>::type EdgeIndexMap;
229     return EdgeIndexMap();
230   }
231 
232   template <class G, class EI, class T, class D>
233   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)234   get(edge_index_t, const edge_list_impl_ra<G,EI,T,D>&,
235       typename edge_list_impl_ra<G,EI,T,D>::edge_descriptor e) {
236     return e;
237   }
238 
239 
240   // Some helper classes for determining if the iterators are random access
241   template <class Cat>
242   struct is_random {
243     enum { RET = false };
244     typedef false_type type;
245   };
246   template <>
247   struct is_random<std::random_access_iterator_tag> {
248     enum { RET = true }; typedef true_type type;
249   };
250 
251   // The edge_list class conditionally inherits from one of the
252   // above two classes.
253 
254   template <class EdgeIter,
255 #if !defined BOOST_NO_STD_ITERATOR_TRAITS
256             class T = typename std::iterator_traits<EdgeIter>::value_type,
257             class D = typename std::iterator_traits<EdgeIter>::difference_type,
258             class Cat = typename std::iterator_traits<EdgeIter>::iterator_category>
259 #else
260             class T,
261             class D,
262             class Cat>
263 #endif
264   class edge_list
265     : public ct_if_t< typename is_random<Cat>::type,
266                     edge_list_impl_ra< edge_list<EdgeIter,T,D,Cat>, EdgeIter,T,D>,
267                     edge_list_impl< edge_list<EdgeIter,T,D,Cat>, EdgeIter,T,D>
268              >::type
269   {
270   public:
271     typedef directed_tag directed_category;
272     typedef allow_parallel_edge_tag edge_parallel_category;
273     typedef edge_list_graph_tag traversal_category;
274     typedef std::size_t edges_size_type;
275     typedef std::size_t vertices_size_type;
276     typedef std::size_t degree_size_type;
edge_list(EdgeIter first,EdgeIter last)277     edge_list(EdgeIter first, EdgeIter last) : _first(first), _last(last) {
278       m_num_edges = std::distance(first, last);
279     }
edge_list(EdgeIter first,EdgeIter last,edges_size_type E)280     edge_list(EdgeIter first, EdgeIter last, edges_size_type E)
281       : _first(first), _last(last), m_num_edges(E) { }
282 
283     EdgeIter _first, _last;
284     edges_size_type m_num_edges;
285   };
286 
287   template <class EdgeIter, class T, class D, class Cat>
num_edges(const edge_list<EdgeIter,T,D,Cat> & el)288   std::size_t num_edges(const edge_list<EdgeIter, T, D, Cat>& el) {
289     return el.m_num_edges;
290   }
291 
292 #ifndef BOOST_NO_STD_ITERATOR_TRAITS
293   template <class EdgeIter>
294   inline edge_list<EdgeIter>
make_edge_list(EdgeIter first,EdgeIter last)295   make_edge_list(EdgeIter first, EdgeIter last)
296   {
297     return edge_list<EdgeIter>(first, last);
298   }
299 #endif
300 
301 } /* namespace boost */
302 
303 #endif /* BOOST_GRAPH_EDGE_LIST_HPP */
304