source: NonGTP/Boost/boost/graph/edge_list.hpp @ 857

Revision 857, 9.9 KB checked in by igarcia, 19 years ago (diff)
Line 
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
21namespace 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    {
57      edge_descriptor() { }
58      edge_descriptor(EdgeIter p, edge_id id) : _ptr(p), _id(id) { }
59      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;
73      edge_iterator() { }
74      edge_iterator(EdgeIter iter) : _iter(iter), _i(0) { }
75      E operator*() { return E(_iter, _i); }
76      self& operator++() { ++_iter; ++_i; return *this; }
77      self operator++(int) { self t = *this; ++(*this); return t; }
78      bool operator==(const self& x) { return _iter == x._iter; }
79      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>
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
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
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
119    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
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
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>
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
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
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
208    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
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
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;
277    edge_list(EdgeIter first, EdgeIter last) : _first(first), _last(last) {
278      m_num_edges = std::distance(first, last);
279    }
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>
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>
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 */
Note: See TracBrowser for help on using the repository browser.